magnify

Batsiuvio uždavinys

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

Užduotis

Batsiuvys turi N užsakymų, kuriuos jam reikia įgyvendinti. Kiekvieną dieną jis gali dirbti tik ties vienu iš užsakymų, o visiškas užsakymo išpildymas paprastai užtrunka keletą dienų. Tiesą sakant, žinoma, kad i-tajam užsakymui išpildyti reikia lygiai \(T_{i}\) dienų (1 <= \(T_{i}\) <= 1000).

Tačiau populiarumas turi savo kainą. Už kiekvieną sugaištą dieną prieš pradedant dirbti ties i-tuoju užsakymu batsiuvys yra sutikęs sumokėti \(S_{i}\) centų baudą (1 <= \(S_{i}\) <= 10000). Net batsiuviui aišku, kad skirtinga tvarka atlikdamas užsakymus, jis sumokės skirtingas baudas. Tačiau kaip rasti optimalią užsakymų atlikimo tvarką? Padėkite batsiuviui – parašykite programą, kuri rastų tokią užsakymų atlikimo tvarką, kad bendra bauda būtų mažiausia iš galimų.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas darbų skaičius N (1 <= N <= 100000). Sekančiose N eilučių įrašytos kiekvieno užsakymo trukmės \(T_{i}\) ir baudos \(S_{i}\) poros. Šie skaičiai tenkina aukščiau apibrėžtus reikalavimus.

Rezultatai

Į pirmą rezultatų failo eilutę programa turi įrašyti skaičių nuo 1 iki N, atskirtų tarpais, seką, žyminčią tokią užsakymų atlikimo tvarką, kad bendra bauda būtų minimali. Užsakymai žymimi skaičiais nuo 1 iki N, jų pasirodymo pradiniuose duomenyse tvarka. Jei yra keli sprendiniai, programa turi išvesti bet kurį iš jų.

Pavyzdžiai

Pradiniai duomenys Rezultatai
4
3 4
1 1000
2 2
5 5
2 1 3 4
© Bronė Narkevičienė