D2 - DezinfekciaČ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 ] ÚlohaObchodné centrá o chvíľu otvoria svoje brány, ale všetky obchody musia zabezečiť ochranné prostriedky nielen pre zamestnancov, ale aj pre zákazníkov. Každý obchod musí ponúkať svojim zákazníkom dezinfekciu na ruky. V aktuálnom čase krízy sú ale balenia dezinfekcie predražené, preto sa v jednom obchodnom centre obchody spojili a rozhodli sa vybudovať dezinfekciovod (vodovod, v ktorom prúdi dezinfekcia) v celej uličke s možnosťou dávkovania pred každým obchodom (čo im ušetrí na nákladoch za dezinfekcie - veľkokapacitné balenia sú stále výhodnejšie ako maloobchodné a zároveň sa nemusia obávať, že istí občania dezinfekčné prostriedky ukradnú...). Snaha je minimalizovať náklady na vybudovanie centrálneho dezinfekciovodu, t.j. z jedného miesta sa naplní a distribuuje do obchodov v jednej dlhej uličke. Náklady na potrubie dezinfekciovodu závisia od dĺžky a potrebného prietoku podľa vzorca dlzka × √prietok. Prietok je samozrejme vypočítaný podľa očakávanmej spotreby v jednotlivých obchodoch. Pomôžte určiť, na ktorom mieste je najvýhodnejšie vybudovať plnenie dezinfekciovodu.VstupPrvý riadok obsahuje počet obchodov N. Druhý riadok obsahuje N nezáporných celých čísel Vi určujúcich vzdialenosti obchodov od vstupu obchodného centra (v rastúcom poradí). Tretí riadok obsahuje N kladných celých čísel Si reprezentujúcich spotrebu v danom obchode (tá je určená podľa počtu zákazníkov v danom obchode), obchody sú uvedené v rovnakom poradí ako v druhom riadku.VýstupVýstupom je poradové číslo obchodu (číslované od 1 od vstupu do obchodného centra), kde je najvýhodnejšie vybudovať dezinfekciovod. V prípade, že by takých obchodov bolo viacero, tak uveďte najmenšie poradové číslo.ObmedzeniaD11 ≤ N ≤ 1000 ≤ Vi ≤ 10.000 1 ≤ Si ≤ 40.000 D21 ≤ 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 umiestniť dávkovanie do 2. obchodu, celková cena vtedy bude približne 388,167 . |