Prihlásenie Registrácia  

S2 - ŠtuRKo 2

Časový limit: 15s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Študentské rádio ŠtuRKo prevádzkuje rozhlasový vysielač, ktorý svojím vysielaním pokrýva úplne celú obývanú plochu školského kampusu. ŠTURKO výhodnou cenovou politikou odrovnal konkurenčné vysielače a dnes ich vysielač prevádzkuje vysielanie takmer všetkých tamojších rozhlasových aj televíznych staníc. Po pridaní aj všetkých 2019 televíznych staníc konzorcia PALMA, sa vo vysielaní mnohých staníc začali objavovať rušivé zvuky.. Ako sa neskôr ukázalo, toto rušenie je spôsobené vysielaním staníc na blízkej frekvencii, následkom čoho dochádza k interferenciám. Aby sa zlepšila kvalita vysielania, je nutné zrušiť vysielanie niekoľkých staníc.

Úloha

Vysielač Š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.

Vstup

Prvý 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≤KN-2).

Výstup

Pre 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í.

Š1

3 ≤ N ≤ 1.000

Š2

3 ≤ N ≤ 1.000.000

Príklad

Vstup:

6
2 5 6 9 10 11
3
1
2
3

Výstup:

1
2
4
Komentá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.