Se consideră un triunghi alcătuit din numere naturale scrise pe n linii ca în figura alăturată. Liniile triunghiului sunt numerotate de la 1 la n, începând cu linia de la baza triunghiului (linia de jos), iar poziţiile pe linie sunt numerotate începând cu 1 de la stânga la dreapta.

Exemplu

triunghi3.in

5
4 4
2 5
3 13
2 25
1 45

triunghi3.out

1 2 3 4 2

Explicație

Triunghiul este:

      45
    20  25
   8  12 13
  3  5  7  6
 1  2  3  4  2

#include <bits/stdc++.h>
using namespace std;
ifstream cin("triunghi3.in");
ofstream cout("triunghi3.out");
long long a[1001][1001], n, pz;
struct st
{
    long long nr, poz;
} x[1001];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i].poz >> x[i].nr;
        a[n-i+1][x[i].poz] = x[i].nr;
    }
    for (int i =2; i<=n; i++)
    {
        pz = x[n-i+1].poz-1;
        while (pz >= 1)
        {
            a[i][pz] = a[i-1][pz]-a[i][pz+1];
            pz--;
        }
        pz = x[n-i+1].poz+1;
        while (pz <= i)
        {
            a[i][pz] = a[i-1][pz-1]-a[i][pz-1];
            pz++;
        }
    }
    for(int i =1; i<=n; i++)
        cout << a[n][i] << ' ';
    return 0;
}