A2 - Corona 2Časový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] ÚlohaV údolí rieky Corona žiaľ vyschol prameň, preto sa jeho obyvatelia rozhodli postaviť vodojem v jednom z miest údolia a naťahať potrubia do ostatných miest. Mestá sa v údolí nachádzajú postupne za sebou v rôznych vzdialenostiach. Pri budovaní potrubí je samozrejme dôležitá jeho cena, ktorá musí byť čo najnižšia, aby ho mestá v súčasnej situácii dokázali zafinancovať. Cena potrubia je určená ako dlzkax√prietok. Pretože majú mestá rôznu spotrebu vody, musí prietok príslušného potrubia zohľadňovať ich potrebu. V ktorom meste majú umiestniť vodojem, aby ich stál čo najmenej?VstupPrvý riadok obsahuje počet miest N. Druhý riadok obsahuje N nezáporných celých čísel Vi určujúcich vzdialenosti miest od začiatku údolia (v rastúcom poradí). Tretí riadok obsahuje N kladných celých čísel Si reprezentujúcich spotrebu v meste. Mestá sú v provnakom poradí ako v druhom riadku.VýstupVýstupom je poradové číslo mesta (číslované od 1 od začiatku údolia), kde je najvýhodnejšie vybudovať vodojem. V prípade, že by takých miest bolo viacero, tak uveďte najmenšie poradové číslo.ObmedzeniaC11 ≤ N ≤ 1000 ≤ Vi ≤ 10.000 1 ≤ Si ≤ 40.000 C21 ≤ N ≤ 100.0000 ≤ Vi ≤ 231-1 1 ≤ Si ≤ 40.000 PríkladVstup:4 0 10 20 40 100 64 36 81 Výstup:2Najvýhodnejšie je postaviť vodojem do 2. mesta, celková cena vtedy bude približne 388,167 . |