magnify

Didesnis – gudresnis?

Pradinių duomenų failas:
drambliai.in  
Rezultatų failas:
drambliai.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Kai kurie žmonės mano, kad kuo dramblys didesnis, tuo jis ir protingesnis. Norėdami tai paneigti, Jūs ėmėte nagrinėti tam tikrą dramblių aibę ir norite sustatyti į eilę kuo daugiau dramblių taip, kad jų svoriai didėtų, o intelekto koeficientai mažėtų.

Parašykite programą, sprendžiančią šį uždavinį.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas dramblių skaičius N (1 <= N <= 1000). Drambliai yra sunumeruoti nuo 1 iki N.

Sekančios N eilučių aprašo dramblius. Kiekvienoje eilutėje įrašyta po du sveikuosius skaičius: (i+1)-oje eilutėje pirmasis skaičius žymi i-ojo dramblio svorį kilogramais, o antrasis – jo intelekto koeficientą. Abu dramblį aprašantys skaičiai yra iš intervalo [1, 10000].

Du drambliai gali būti vienodo svorio, vienodo intelekto, arba net vienodo svorio ir vienodo intelekto.

Rezultatai

Pirmoje rezultatų failo eilutėje turi būti įrašytas vienintelis skaičius: didžiausias skaičius dramblių, kuriuos galima sustatyti į vieną eilę taip, kad jų svoriai sudarytų griežtai didėjančią progresiją, o intelekto koeficientai – griežtai mažėjančią.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas
9
6008 1300 
6000 2100 
500 2000 
1000 4000 
1100 3000 
6000 2000 
8000 1400 
6000 1200 
2000 1900
4
Į vieną eilę galima sustatyti (iš eilės) ketvirtą, penktą, devintą ir septintą dramblius.
© Bronė Narkevičienė