B2 - BalónyČasový limit: 30s, 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 ] Na programátorských súťažiach sa zaužívalo pre zvýšenie atraktivity počas riešenia praktických úloh označenie vyriešenia úlohy prilepením balónu (každá úloha má svoju vlastnú farbu). Takže pozorovatelia v miestnosti vidia, kto má najviac balónov (a teda najviac vyriešených úloh). Organizátori celoštátneho kola Olympiády v informatike (ktoré sa tohto roku konalo v Košiciach) sa zamýšľali nad podobným spestrením riešenia praktického dňa. Systém hodnotenia je v tejto súťaži odlišný - hodnotí sa až posledné riešenie a je možné za neho dostať niekoľko bodov (podľa toho, koľko testovacích vstupov vyrieši správne). Čím je algoritmus efektívnejší, tým získa viac bodov. Rozhodli sa teda, že budú balóny nafúkavať za každé poslané riešenie. Umiestňovať ich budú zaradom na vopred určené pozície (na jednu dlhú poličku). Každý balón (v tvare gule) nafúknu do polomeru určeného počtom bodov, pričom ale nafukovanie prerušia hneď, ako sa balón dotkne niektorého z už nafúknutých balónov. Pomôžte im určiť ako silno musia nafúknuť každý balón, pričom ich budú nafukovať v poradí zľava doprava. ÚlohaDaný je zoznam umiestnenia balónov spolu s prislúchajúcimi počtami bodov (maximálne polomery balónov), ktoré chce komisia umiestniť. Pre každý balón vypočítajte, ako ho možno čo najviac nafúknuť tak, aby ho bolo možné umiestniť k už doteraz položeným balónom.VstupPrvý riadok vstupu obsahuje jedno kladné celé číslo N, počet balónov. Nasledujúcich N riadkov obsahuje po dve celé čísla pre každý balón - pozíciu Xi (0 ≤ Xi ≤ 109) a požadovaný polomer Ri (0 ≤ Ri ≤ 109). Môžete predpokladať, že balóny sú zadané zľava doprava, teda podľa rastúcej súradnice (X).B11 ≤ N ≤ 2 000B21 ≤ N ≤ 200 000VýstupVýstupom je N riadkov vypisujúcich polomery maximálne nafúkaných balónov s presnosťou na (aspoň) 3 desatinné miesta (akceptované sú riešenia, ktoré sa líšia najviac o 0.001).PríkladVstup:3 0 15 10 1 17 10 Výstup:15.000 1.000 4.817 Upozornenie
Nezabudnite na rozsahy hodnôt, teda používajte dostatočné veľké a presné číselné typy - (Pascal: Longint / Extended, C++ a Java: long / double).
Na výpis hodnôt môžete použiť: |