2. naloga
Ne odlašaj na jutri, kar lahko storiš pojutrišnjem
Učenci v šoli imajo n obveznosti, ki jih morajo izpolniti. Pri tem jim i-ta obveznost vzame di dni in jo morajo opraviti najkasneje na dan ki (mislimo si, da so dnevi oštevilčeni z naravnimi števili od začetka šolskega leta). V posameznem dnevu se lahko ukvarjajo samo z eno obveznostjo, lahko pa počivajo in se ne ukvarjajo z nobeno. Ko se enkrat lotijo neke obveznosti, jo morajo potem opraviti v neprekinjenem sklopu di zaporednih dni (torej jim ta obveznost vzame dan, ko so začeli z njo, in še naslednjih di − 1 dni). Če je na primer di = 3, to pomeni, da se morajo začeti z i-to obveznostjo ukvarjati najkasneje na dan ki − 2.
Kot tipični učenci si seveda želijo vse te obveznosti opraviti čim kasneje. Torej, če lahko nek dan počivajo in se obveznosti lotijo jutri in še zmeraj opravijo vse obveznosti pravočasno, potem danes seveda raje počivajo.
Natančneje povedano, dva možna razporeda tega, kdaj opravijo kakšno obveznost, primerjamo takole: poiščemo najzgodnejši dan, na katerega pri enem razporedu počivajo, pri drugem pa delajo; če takega dne ni, štejemo razporeda za enakovredna in sta nam oba enako dobra; sicer pa nam je boljši tisti razpored, pri katerem na tisti dan počivajo.
Napiši program ali podprogram (funkcijo), ki kot vhodne podatke dobi podatke o obveznostih (števila n, k1, d1, k2, d2, ... , kn, dn) in izračuna najboljši možni razpored (za vsako obveznost i naj torej ugotovi, na kateri dan zi se morajo začeti ukvarjati z njo), ali pa ugotovi, da za te vhodne podatke sploh ni nobenega veljavnega razporeda. Če je možnih več enako dobrih razporedov, je vseeno, katerega poiščeš. Podrobnosti glede oblike vhodnih in izhodnih podatkov si izberi sam in jih tudi opiši. Tvoja rešitev naj bo čim učinkovitejša, tako da bo uporabna tudi za večje vhodne primere (recimo, da gre lahko n do 106, datum ki pa do 109).