V2 - Vysielače 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 ] ÚlohaVysielače vysielajú na frekvenciách f1,f2,...,fN, kde N označuje počet vysielacích zariadení. Vašou úlohou je zrušiť vysielanie presne K vysielačov tak, aby vzdialenosť medzi dvoma najbližšími frekvenciami bola čo najväčšia. Napríklad, ak vysielame na frekvenciách s hodnotami 100, 130, 180 a 250 MHz, vzdialenosť medzi dvoma najbližšími stanicami je 30 MHz. V prípade, že môžeme zrušiť vysielanie jednej stanice, najvýhodnejšou možnosťou je zrušiť vysielanie na frekvencii 130 MHz. VstupPrvý riadok vstupu obsahuje kladné celé číslo N, určujúce počet frekvencií. Druhý riadok vstupu obsahuje N kladných celých čísel f1,f2,...,fN, určujúcich rádiové frekvencie. Môžete predpokladať, že čísla na vstupe budú zotriedené v rastúcom poradí a každé z nich je menšie ako 2.109. Tretí riadok vstupu obsahuje kladné celé číslo Q, určujúce počet otázok. Každý z posledných Q riadkov vstupu obsahuje jedno kladné celé číslo K, určujúce počet frekvencií, ktoré by sme chceli zrušiť. (1≤Q≤20),(1≤K≤N-2).VýstupPre každú sadu zo vstupu vypíšte (najväčšiu možnú) vzdialenosť dvoch najbližších frekvencií, ktorú vieme získať po odstránení vysielania K frekvencií.V13 ≤ N ≤ 1.000V23 ≤ N ≤ 1.000.000PríkladVstup:6 1 4 5 8 9 10 3 1 2 3 Výstup:1 2 4Komentár k príkladu vstupu: Ak môžeme odstrániť vysielanie jedinej stanice, vzialenoť dvoch najbližších frekvencií ostane 1. Ak môžeme odstrániť dve frekvencie, odstránením hodnôt 4 a 9 vieme získať vzdialenosť 2. Pri odstránení troch staníc je najvýhodnejšie riešenie odstrániť hodnoty 4, 8 a 9. |