S2 - ŠtuRKo 2Časový limit: 15s, 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č ŠtuRKa dnes vysiela na frekvenciách f1,f2,...,fN, kde N označuje počet všetkých staníc, ktorých vysielanie prevádzkuje ŠtuRKo. Vašou úlohou je zrušiť vysielanie presne K staníc 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í.Š13 ≤ N ≤ 1.000Š23 ≤ N ≤ 1.000.000PríkladVstup:6 2 5 6 9 10 11 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 5 a 10 vieme získať vzdialenosť 2. Pri odstránení troch staníc je najvýhodnejšie riešenie odstrániť hodnoty 5, 9 a 10. |