- 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 |