Autor Zpráva
hugo123
Profil *
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
Profil
předpokládám, že toto je domácí úloha, proto ti neporadím; jen trochu zamlžím

určitě nechceš simulovat každou minutu, stačí ti znát celkový objem vždy těsně před tím, než začne pršet
například:
3
1 1 10
1 2 5
1 3 3
tady ti stačí vypočítat objem v 0., 2., 4. a 9. minutě

určitě také nechceš počítat objem mraků každou minutu znova, vždyť jich prší zároveň jen velice málo a stačí zjistit, jak se objem změní oproti předchozímu:
t=0: v_0=3
t=2: v_2=v_0+(2-0)*(1+2+3)
t=4: v_4=v_2+(4-2)*(1+2+3)-3*4
t=9: v_9=v_4+(9-4)*(1+2)-2*9

doplněno: při vypršení mraku ho musíš celý odečíst, ne jen jeho přírustek

stačí ti, pamatovat si aktuální maximální celkový objem

úloha je rychlostně omezená rychlostí třízení (použiješ ho pro vytvoření kalendáře): O(n*log n)
hugo123
Profil *
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.
juriad
Profil
hugo123:
A vlastne ak novy celkovy objem bude mensi ako ten predchadzajuci, tak uz koncim.
není pravda, při vypršení mraku se ti může objem hodně snížit, ale časem ho může překonat pomalu rostoucí mrak, který vyprší za hoodně dlouho
příklad:
3
1 20 2
1 3 3
1 1 100
t=0: v=3
t=1: v=27
t=2: v=10
t=99: v=99

vsetko chapem, len nechapem poslednej tvojej vete. Aky kalendar? ake triedenie?
musíš uvažovat pršení mraků v určitém pořadí, jak to pořadí získáš?
hledat najbližší pršku projitím všech mraků je neefektivní (budeš prohledávat n-krát n mraků), proto si je setřídíš podle Mi

v podstate viem v O(1) zistit pred kazdym novym prsanim novy objem ze?
ano

Tento typ úloh se nazývá diskrétní simulace:
chceš simulovat události, které nastávají v určité časy; události máš uložené v nějaké struktuře, od ní chceš obvykle dvě operace:
1/ vrať mi nejbližší následující událost
2/ naplánuj novou událost
to jak bude tato struktura realizována závisí na konkrétní úloze; může to být obyčejná fronta, pole nebo nějaký obecný kalendář

v tvém případě asi budeš mít události v poli setříděné je podle času; pak operace 1/ bude jen posunutí doprava v poli; operaci 2/ nepotřebuješ (mraky ti nevznikají)
hugo123
Profil *
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! ;-))
nemeja
Profil
hugo123:
uloha do skoly to nie je, je to algoritmicky problem zo sady uloh, ktore si dobrovolne riesim.
Můžu se zeptat, kde ty úlohy bereš? ;) Neposlal by jsi mi prosím na ně odkaz, kde koupit knížku, nebo jestli jsou ne internetu, tak by to bylo super ;) dík
juriad
Profil
hugo123, nemeja:
Pokud jste ještě žáci střední školy, můžete začít řešit nějaké semináře z programování; například KSP (web si určitě projděte).
Tam také najdete velké množství úloh (několik ročníků) i studijních materiálů (kuchařek); řešení obvykle nevyžaduje napsání konkrétního kusu kódu, ale detailní popis a rozmyšlení algoritmu.
Další velkým zdrojem může být Archiv MO-P

hugo123:
Kontakt ti asi nechci dávat, jsem obvykle docela zaneprázdněný; ale určitě můžeš napsat sem na diskusi (pokud to nebude úplně často: zaměřujeme se zde spíše na web) nebo zkus přímo fórum KSPčka
hugo123
Profil *
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é.

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: