Fişierul intrare/ieşire:pitricele.in, pitricele.outSursăLot Seniori Alexandria, 2017, baraj 5
AutorIonel-Vasile Pit-RadaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test0.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pitricele

Bolovani şi pitricele, să spargă blatul cu ele.

Cei doi prieteni, Ţip şi Adar se joacă, folosind nişte pietre speciale, în felul următor: Ţip deţine N pitricele, fiecare având câte o greutate şi o rezistenţă şi le aşează în ordine una peste alta, formând un turn vertical. Peste o pitricică având rezistenţa R se pot aşeza alte pitricele doar dacă suma greutăţilor acestora este strict mai mică decât R; în caz contrar, pitricica se va sparge. Dacă la un moment dat ar exista mai multe pitricele care s-ar putea sparge atunci toate se vor sparge în acelaşi timp.
Se dau N triplete de forma (G, R, X), cu următoarea semnificaţie: o pitricică având greutatea G şi rezistenţa R se adaugă în turnul deja existent, garantându-se că nu se va sparge nicio piatră din cele puse anterior. Adar trebuie să-i spună lui Ţip care este greutatea minimă pe care ar trebui să o aibă o nouă pitricică astfel încât, dacă aceasta ar fi pusă în vârful turnului, ea ar sparge cel puţin X pitricele.

Date de intrare

Fişierul pitricele.in va conţine pe prima linie un număr natural N. Pe următoarele N linii vor fi codificate cele N triplete (Gi, Ri, Xi). Astfel tripletul (Gi, Ri, Xi) va fi codificat pe linia i + 1 ca (Gi xor Vi-1, Ri xor Vi-1, Xi xor Vi-1) unde cu Vi s-a notat răspunsul lui Adar pentru Ţip după ce acesta a aşezat a i-a pitricică.

Date de ieşire

Fişierul pitricele.out va avea N linii, conţinând, răspunsurile lui Adar, în ordine cronologică, câte unul pe o linie.

Restricţii şi precizări

  • 1 ≤ N ≤ 100 000
  • 1 ≤ Gi, Ri ≤ 1 000 000 000
  • 1 ≤ Xi ≤ i

Exemplu

pitricele.inpitricele.out
3
3 4 1
6 12 5
3 5 3
4
2
1

Explicaţie

Tripletele originale sunt:
(3 4 1)
(2 8 1)
(1 7 1)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?