Algoritmicky problem

Ahojte,

prosim Vas, vedeli ste mi poradit, ako vyriesit tento problem? Staci mi iba slovna idea, nemusite mi napisat kod. Treba si totizto uvedomit, ze simulovanim to nepojde, pretoze to musi byt naprogramovane co najefektivnejsie, teda aby sa vykonalo maximalne okolo miliardy operacii.

Uloha:
-------------------------------------------------
Na oblohe je v tejto chvíli n oblakov, každý z nich je nejako veľký. Každú minútu sa každý oblak zväčší. A po niekoľkých minútach sa zrazu stane, že sa z oblaku spustí dážď. Takýto oblak sa okamžite prudko vyprší a zmizne. No a keď oblak zmizne, Rainbow Dash ho už nemá ako rozbiť.

Presnejšie, pre každý oblak je daný jeho aktuálny objem vi, jeho konštantný prírastok objemu za každú minútu pi a počet minút mi po koľkých sa okamžite vyprší.

Nájdite kladné celé číslo m také, že ak Rainbow Dash počká m minút a potom rozbije všetky oblaky, bude celkový objem rozbitých oblakov najväčší možný. Môžete predpokladať, že počas jej čakania žiadne nové oblaky nevznikajú.

Input specification
V prvom riadku vstupu je aktuálny počet oblakov n.
Nasleduje pre každý oblak jeden riadok a v ňom jeho hodnoty vi, pi a mi.

Môžete predpokladať nasledujúce obmedzenia:
1 <= n <= 1 000 000
1 <= Vi, Pi, Mi <= 100 000

POZOR. Vstupné dáta sú veľké, radšej nepoužívajte pomalé skriptovacie jazyky.

Output specification
Vypíšte jeden riadok a v ňom jedno celé číslo m: počet minút odteraz, po ktorom keď Rainbow Dash rozbije oblaky, tak budú mať najväčší možný celkový objem. Ak existuje viac správnych odpovedí, vypíšte najmenšiu z nich.
Examples

input
3
1 1 2
5 5 3
7 2 4

output
2

Na začiatku máme tri oblaky, ich objemy sú (1,5,7). Po prvej minúte máme objemy (2,10,9). Po druhej minúte sa prvý oblak vyprší a ostatné narastú, nové objemy teda budú (0,15,11). Po tretej minúte sa vyprší druhý oblak, a teda na oblohe ostane už len jeden: (0,0,13). Po štvrtej minúte zmizne aj ten a ďalej už bude jasno. Najlepšie riešenie je teda počkať dve minúty a potom rozbiť oblaky s celkovým objemom 15 + 11 = 26.
-------------------------------------------------


Vopred dakujem za akekolvek rady.

juriad:
„úloha je rychlostně omezená rychlostí třízení (použiješ ho pro vytvoření kalendáře): O(n*log n)“
hugo123:

ahoj, super, diky moc... necakal som, ze sa tu najdu takyto mudri a sikovni ludia ;-)))
uloha do skoly to nie je, je to algoritmicky problem zo sady uloh, ktore si dobrovolne riesim.

vsetko chapem, len nechapem poslednej tvojej vete. Aky kalendar? ake triedenie?

Rozmyslam... v podstate viem v O(1) zistit pred kazdym novym prsanim novy objem ze?
a potom proste od toho *(1+2+3) vzdy odratam ten oblak, ktory vyprsal. Dobre rozmyslam?
A vlastne ak novy celkovy objem bude mensi ako ten predchadzajuci, tak uz koncim.

Vopred vdaka.

Dakujem moc, uz mi je teraz vsetko jasne ;-)))

Velmi si mi pomohool, dakujem!


P.S. Nemas nahodou nejake ICQ/skype/ pripadne e-mail, ze by som ti niekedy napisal, ak by som mal opat nejaky problem? velmi by som si to vazil a cenil. Vopred velka vdaka! ;-))

juriad:
Dakujem za tipy.

Trapim sa tu este s jednym prikladom, ak by si vedel poradit, bol by som ti velmi vdacny:

Aj teraz má Pinkie Pie v batôžku jednu tabuľku čokolády, ktorú by chcela zjesť. Teda rozdeliť sa s kamarátkami a spoločne ju zjesť. Lenže kopýtkom sa taká čokoláda láme ťažko. Najjednoduchšie je najskôr po nej trochu podupať, nech sa zlomí pozdĺž niekoľkých riadkov a stĺpcov, a potom ju rozbaliť, kúsky čokolády rozdať a zjesť.

Task
Na vstupe sú rozmery čokolády (počet riadkov r a počet stĺpcov s) a počet kamarátok n, s ktorými sa Pinkie Pie ide rozdeliť. Nájdite najspravodlivejší spôsob nalámania čokolády. Čokoládu musí nalámať na presne n + 1 neprázdnych kúskov, pričom rozdiel medzi najväčším a najmenším kúskom musí byť čo najmenší.

Input specification
V prvom riadku sú dve kladné celé čísla r a s. Ich súčin je nanajvýš 2^30. V druhom riadku je kladné celé číslo n, z rozsahu od 0 po 5.

Output specification
Vypíšte jeden riadok a v ňom jedno celé číslo: najmenší dosiahnuteľný rozdiel medzi obsahom najväčšieho a najmenšieho kúsku čokolády pri jej optimálnom rozlámaní. Ak sa čokoládu nedá rozlámať na presne n + 1 neprázdnych kúskov, vypíšte namiesto toho číslo -1.

Examples

input
3 2
5

output
0

Čokoládu rozlomíme medzi každými dvoma riadkami aj stĺpcami. Dostaneme šesť kúskov, každý tvorený jedinou kockou. Takéto delenie je úplne spravodlivé.

input
1 1
3

output
-1

Rozdeliť jednu kocku čokolády medzi štyri poniky nejde.

input
1 9
3

output
1

Pri optimálnom delení dostaneme jeden kúsok tvorený tromi a tri kúsky tvorené dvomi kockami čokolády.

input
4 7
0

output
0

Keď je Pinkie Pie sama, spravodlivo rozdeliť čokoládu je ľahké.