Zadanie

Po ukrutnej zime strávenej s nádchou si Zuzka uvedomila, že jej ohnutá nosná prepážka je už na nevydržanie a dá si ju operovať. Najprv však musí podstúpiť predoperačné vyšetrenie, čo znamená, že musí navštíviť doktora a stráviť tri temné doby v čakárni, kým na ňu príde rad. Čakáreň v nemocnici je v skutočnosti len dlhočizná chodba s jedným dlhým radom sedadiel, ktoré sú buď voľné, obsadené zdravým človekom alebo nejakým úbožiakom s kalným pohľadom a osoplenou vreckovkou. Keďže má Zuzka ešte stále trocha podlomenú imunitu, posledné, čo by chcela, je zase ochorieť. Preto si v čakárni chce sadnúť čo najďalej od všetkých posmrkávajúcich a odŕhajúcich ľudí. Zároveň ju však už bolia nohy z postávania v preplnenej 39-tke1 a tento strategický výber sedadla chce spraviť čo najrýchlejšie. Pomôžete jej?

Úloha

Dostanete popis radu sedadiel v čakárni. Každé sedadlo je buď voľné, obsadené zdravým človekom, alebo obsadené chorým človekom. Vašou úlohou je nájsť to voľné sedadlo, pre ktoré je vzdialenosť od najbližšieho chorého človeka maximálna.

Formát vstupu

Sedadlá v čakárni sú zaradom očíslované kladnými celými číslami.

Na prvom riadku vstupu dostanete dve kladné celé čísla \(v, c\) označujúce počet voľných sedadiel a počet sedadiel, na ktorých sedí niekto chorý. Na druhom riadku nasleduje \(v\) čísel označujúcich pozície voľných sedadiel. Na treťom riadku je \(c\) čísel označujúcich pozície sedadiel obsadených chorými ľudmi. Na pozíciach nešpecifikovaných v predošlých dvoch riadkoch sa nachádzajú sedadlá obsadené zdravými ľuďmi.

Pre jednotlivé testovacie sady platia nasledujúce obmedzenia:

číslo sady \(1\) \(2\) \(3\) \(4\)
\(v + c \leq\) \(1\,000\) \(5\,000\) \(100\,000\) \(100\,000\)
počet všetkých sedadiel \(\leq\) \(10\,000\) \(1\,000\,000\) \(100\,000\,000\) \(100\,000\,000\)

Formát výstupu

Vypíšte jediné číslo - pozíciu voľného sedadla, ktoré je najďalej od najbližšieho chorého človeka. Ak je takých sedadiel viac, vypíšte to s najnižším číslom, nech sa Zuzka toľko nenachodí.

Input:

5 4
1 11 7 6 13
3 10 4 12

Output:

7

Situáciu si môžeme zakresliť takto: -OXXO--OOX-X-O, pričom O je zdravá osoba a X chorá. Sedadlo \(1\) je od najbližšej chorej osoby (ktorá sedí na sedadle \(3\)) vzdialené \(2\), sedadlo \(6\) tiež \(2\) (v tomto prípade ide o človeka na sedadle \(4\)), sedadlo \(7\) má vzdialenosť od najbližšieho chorého človeka \(3\) (ľudia na sedadlách \(4\) a \(10\)) a sedadlá \(11\) a \(13\) majú najbližšieho chorého hneď vedľa seba.

Input:

3 3
4 7 3
5 9 1

Output:

3

Tu je situácia takáto: XO--XO-OXO. Optimálne sedadlá sú na pozíciach \(3\) a \(7\) s najbližším chorým človekom vzdialeným \(2\), no keďže sedadlo \(3\) má menšie číslo, vyberieme ho.

Input:

1 1
1
2

Output:

1

Zuzka si tu nenavyberá, musí si sadnúť hneď vedľa maróda.

  1. Táto autobusová linka je živou ilustráciou matematickej indukcie: ak sa zmestí \(n\) ľudí, zmestí sa aj \(n + 1\).↩

Aby sme našli sedadlo pre Zuzku, pre každé voľné sedadlo zistíme vzdialenosť od najbližšieho chorého. Z týchto vzdialeností potom vyberieme tú najlepšiu.

Prvé riešenie

Najjednoduchší spôsob na zisťovanie vzdialeností je, keď pre každé voľné sedadlo prejdeme zoznam všetkých chorých a určíme, ktorý z nich je najbližšie.

Toto riešenie má časovú zložitosť \(O(v \cdot c)\). Pamäťová zložitosť bude \(O(v + c)\).

Lepšie riešenie

Pri spracovaní jedného voľného sedadla nás ale väčšina chorých nezaujíma. Dôležití sú len tí, ktorí sú najbližsie napravo a naľavo od daného voľného sedadla. Čakáreň si vieme predstaviť ako úseky voľných sedadiel (a sedadiel obsadených zdravými ľuďmi), ktoré sú oddelené chorými. Každý takýto úsek má spoločných najbližších chorých.

Na hľadanie najbližších chorých sa nám oplatí si dáta usporiadať. Vieme potom použiť princíp dvoch bežcov, kedy si v zozname chorých aj v zozname voľných miest pamätáme index sedadla, s ktorým práve pracujeme. V zozname voľných sedadiel si budeme pamätať index práve spracúvaného sedadla a v zozname chorých index najbližšieho chorého napravo od tohto sedadla (rovnako dobre by fungovalo pamätať si index najbližšieho chorého naľavo). Keď v zozname voľných sedadiel presiahneme pozíciu aktuálneho chorého, posunieme sa na ďalší úsek – medzi ďalších dvoch chorých.

V rámci jedného úseku budeme určovať vzdialenosť najbližšieho chorého ako menšiu zo vzdialeností k jednému z chorých na kraji úseku.

Takéto riešenie bude mať časovú zložitosť \(O(v \log v + c \log c)\), pretože zoznamy chorých a voľných sedadiel si potrebujeme usporiadať. Prechádzanie týchto zoznamov a určovanie vzdialeností spravíme raz – časová zložitosť je \(O(v + c)\) a toto nám celkovú časovú zložitosť nezhorší.

Pamäťová zložitosť bude \(O(v + c)\), pretože si potrebujeme pamätať oba zoznamy.

#nacitanie vstupu
v, c = [int(x) for x in input().split()]
volne = [int(x) for x in input().split()]
chore = [int(x) for x in input().split()]

#pridame si choreho do nekonecna na zaciatok a na koniec
chore.append(-100000000)
chore.append(100000000)

#usporiadanie poli
volne = sorted(volne)
chore = sorted(chore)

maximalna_vzdialenost = 0
sucasna_vzdialenos_lava = 0
sucasna_vzdialenos_prava = 0
sucasny_volny_index = 0
#toto bude lavy chory
sucasny_chory_index = 0
vysledne_sedadlo = 0

while (sucasny_chory_index < len(chore) - 1 and sucasny_volny_index < len(volne)):
	if (volne[sucasny_volny_index] > chore[sucasny_chory_index + 1]):
		sucasny_chory_index += 1
	else:
		sucasna_vzdialenost_lava = volne[sucasny_volny_index] - chore[sucasny_chory_index]
		sucasna_vzdialenost_prava = chore[sucasny_chory_index + 1] - volne[sucasny_volny_index]
		if maximalna_vzdialenost < min(sucasna_vzdialenost_lava, sucasna_vzdialenost_prava):
			vysledne_sedadlo = volne[sucasny_volny_index]
			maximalna_vzdialenost = min(sucasna_vzdialenost_lava, sucasna_vzdialenost_prava)
		sucasny_volny_index += 1

print(vysledne_sedadlo)

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.