Zadanie
Pozemšťanské Národné Múzeum v Sekulách vystavuje skutočný skvost: Najvzácnejšiu hlásku galaxie1. Táto hláska je lokálny endemit – nevyskytuje sa vo fonológií jazyka žiadnej inej planéty, a preto má obrovskú hodnotu. A práve preto bola v piatok cez obedovú prestávku ukradnutá rafinovaným páchateľom. Nie je ním nik iný, ako interstelárny kriminálnik Okáň Hruškový, prezývaný “Bzučiak”. Samotná krádež bola pre neho hračkou, skutočná skúška jeho schopností nastáva až teraz: s ukradnutou hláskou sa musí dostať na najbližšiu matriku, kde si zmení meno na Okäň, čím zmätie agentov zákona, zahladí všetky stopy po svojej kriminálnej histórií a šťastný odíde do dôchodku. Samozrejme, poletí lietajúcim tanierom2.
Má to však háčik: Medzi Pozemšťanským Národným Múzeom v Sekulách a Sekulským Matričným Úradom nejde žiaden priamy let, preto musí Bzučiak prestúpiť na Hlavnej Tanierovej Stanici Sagittarius A.
Okrem toho je problémom, že galaktická polícia má agentov zákona všade. Normálne síce pre Bzučiaka žiaden problém nepredstavujú3, pokiaľ ale poletí rovnakým letom ako jeden z nich, môže sa s novým menom rozlúčiť.
Ako nový zamestnanec IT oddelenia galaktickej polície ste dostali časy odletov všetkých liniek, spolu s pridelenými financiami, za ktoré môžete nakúpiť niekoľkým policajtom letenky, aby ste Bzučiakovi znemožnili využitie týchto letov. Vašou úlohou je Bzučiakovi cestu čo najviac znepríjemniť, pokiaľ možno úplne znemožniť.
Úloha
Máte dané časy odchodov všetkých \(n\) letov z Národného Múzea do Tanierovej Stanice, ako aj ich dĺžku \(d_a\), ktorá je, samozrejme, pre všetky rovnaká. Rovnako máte dané aj odchody všetkých \(n\) letov z Tanierovej Stanice na Matričný Úrad, a ich dĺžku \(d_b\). Máte peniaze na zablokovanie \(k\) letov – určte, v akom najneskoršom čase môžeme Bzučiaka prinútiť dostať sa na Matričný Úrad, respektíve či vieme Bzučiakovi v jeho dosiahnutí úplne zabrániť.
Bzučiak môže prestúpiť medzi dvoma letmi, pokiaľ čas príchodu prvého nie je vyšší ako čas odchodu druhého, pričom dĺžka letu je definovaná ako rozdiel v časoch jeho príchodu a odchodu.
Formát vstupu
Na prvom riadku vstupu sa nachádzajú 4 celé čísla \(n, d_a, d_b, k\) - počet letov na každej linke, dĺžky letov prvej a druhej linky, a počet lístkov, ktorý si môžeme dovoliť kúpiť, pričom vždy platí \(1 \leq d_a,d_b\) a \(1 \leq k \leq 2n\).
Nasledujú dva riadky. Na prvom z nich je \(n\) rôznych celých čísel \(a_0\) až \(a_{n-1}\), ktoré označujú časy odchodov letov prvej linky. Na druhom z nich je \(n\) rôznych celých čísel \(b_0\) až \(b_{n-1}\), ktoré označujú časy odchodov letov druhej linky. Platí, že oba riadky sú zoradené vo vzostupnom poradí, a okrem toho všetky časy odletov \(x\) spadajú do nasledovného rozmedzia: \(1 \leq x \leq 10^{9}\).
Formát výstupu
Na jediný riadok výstupu vypíšte jediné číslo – najneskorší čas, v akom môžeme Bzučiaka donútiť doraziť do cieľovej zastávky. Pokiaľ je možné Bzučiakovi zabrániť v dosiahnutí cieľa úplne, vypíšte číslo \(-1\). Nezabudnite na konci vypísať symbol konca riadku.
Hodnotenie
Sú 4 sady vstupov:
- V prvej sade platí, že \(1 \leq n \leq 100\), \(d_a = d_b = 1\) a obe linky majú rovnaké časy odletov, teda \(a_i = b_i\) pre všetky \(0 \leq i \leq n-1\).
- V druhej sade platí, že \(1 \leq n \leq 10\,000\).
- V tretej sade platí, že \(1 \leq n \leq 100\,000\).
- V štvrtej sade platí, že \(1 \leq n \leq 1\,000\,000\).
Príklad
Input:
4 3 5 3
1 2 3 6
6 7 8 9
Output:
14
Zablokujeme napríklad prvé tri lety z Národného Múzea. Bzučiak nebude mať inú možnosť, ako využiť ten posledný, s odchodom v čase 6. V Tanierovej Stanici bude v čase 9, stihne rýchlo nastúpiť na posledný let na Matričný Úrad, ktorý k nemu dorazí v čase 14. Alternatívne sme mohli zablokovať prvé tri lety druhej linky a dosiahnuť rovnaký výsledok.
Input:
6 2 1 4
1 3 5 7 9 11
3 4 5 6 10 13
Output:
-1
V tomto prípade vieme Bzučiaka od Matričného Úradu úplne odrezať, napríklad zablokovaním prvých dvoch letov z Národného Múzea a posledných dvoch letov z Tanierovej Stanice. Bzučiak odletí najskorším letom s odchodom v čase 5, v Tanierovej Stanici bude v čase 7, a nestíha už žiaden nezablokovaný let ďalej.
Zamyslime sa, ktorými letmi sa Bzučiakovi oplatí letieť. Z Národného Múzea do Hlavnej Stanice sa mu určite oplatí letieť prvým neblokovaným letom. Teda pre nás nemá zmysel blokovať tieto lety, pokiaľ je nejaký skorší aj tak nezablokovaný. Takže jednoducho budeme blokovať niekoľko prvých letov prvej linky.
V prípade druhej linky to je podobne: Bzučiak určite nepoletí z Hlavnej Stanice na Matričný Úrad žiadnym letom po prvom neblokovanom. Zároveň ale, na rozdiel od prvej situácie, platí, že určite nepoletí takým letom, ktorý odlieta pred tým, ako priletí Bzučiakov prvý let (nie preto, že by sa to neoplatilo, ale preto, že je to jednoducho nemožné).
Teda všetky možné blokovania letov, aké sa nám teoreticky môžu oplatiť (majú potenciál viesť ku hľadanému optimálnemu výsledku), vyzerajú nasledovne: Zablokujeme \(x\) prvých letov prvej linky, pričom \(0 \leq x \leq k\) . Bzučiak poletí prvým neblokovaným letom, teda do Hlavnej Stanice doletí v čase \(a_x + d_a\), respektíve ak \(n \leq x\), tak nepoletí vôbec, keďže sme zablokovali všetky lety na prvej linke. Ostáva nám \(k-x\) letov, ktoré môžeme blokovať. Nemá zmysel blokovať lety druhej linky, ktoré odlietajú pred Bzučiakovym časom príchodu do hlavnej stanice. Zablokujeme teda prvých \(k-x\) letov, ktoré z Hlavnej Stanice odlietajú v Bzučiakovom čase príchodu alebo neskôr. Opäť môže nastať možnosť, že \(k-x\) je dosť na zablokovanie všetkých letov až po posledný. Ak nenastane, Bzučiak poletí letom číslo \(y\), a do cieľa sa dostane v čase \(b_y + d_b\).
Pre všetky možné hodnoty \(x\) musíme nájsť najvyššie dosiahnuteľné \(b_y + d_b\), prípadne či pre nejaké \(x\) vieme dosiahnuť kompletné zablokovanie.
Pomalé riešenie
Najzjavnejšie riešenie, ktoré nám môže napadnúť je postupne vyskúšať všetky možné počty zablokovaných letov prvej linky \(x\), a pre každý nájsť riešenie. Jednoducho pre každý čas príchodu \(a_x + d_a\) nájdeme v časoch odchodu druhej linky prvý let, ktorý neodlieta pred ním, posunieme sa o \(k-x\) letov neskôr na nejaký let \(b_y\), a pamätáme si výsledok \(b_y + d_b\). Na konci vypíšeme z týchto výsledkov ten najvyšší, respektíve ak niekedy dosiahneme kompletné zablokovanie, tak môžeme hľadanie ihneď prerušiť a vypísať \(-1\).
Časová zložitosť tohto riešenia môže byť \(O(n^2)\), pokiaľ prvý let druhej linky, ktorý Bzučiak stíha, hľadáme lineárne, teda postupne od začiatku. Môžeme si trošku prilepšiť použitím binárneho vyhľadávania, čím zlepšíme zložitosť na \(O(n \cdot log(n))\). V oboch prípadoch pre každú možnú hodnotu \(x\), ktorých určite nie je viac ako \(2n\), hľadáme bod v usporiadanom poli, teda zložitosť je lineárna, vynásobená zložitosťou našeho hľadania. Posunúť sa po nájdení tohto letu o \(k-x\) ďalej nám zaberie konštantný čas, keďže výstupom z hľadania je index nájdeného prvku, a k nemu jednoducho pripočítame \(k-x\). Pamäťová zložitosť programu bude každopádne \(O(n)\), keďže nám stačí pamätať si vstup a konštantné množstvo celočíselných premenných.
Vzorové riešenie
Hľadanie, ktoré sme v pomalších riešeniach vylepšovali, môžeme zlepšiť ešte viac. Uvedomme si, že keď \(x\) sa zvýši o \(1\), tak čas príletu do Hlavnej Stanice sa určite nezníži. Teda nemusíme zakaždým prehľadávať celé pole odletov, ale stačí nám pokračovať tam, kde sme prestali (pretože vieme, že letíme neskorším letom, ako predtým, teda lety, ktoré sme nestihli predtým, určite nestihneme ani teraz). Postačí nám teda hľadať lineárne, no pamätať si vždy bod, kde sme naposledy prestali, a nabudúce pokračovať v hľadaní odtiaľ.
Toto nové hľadanie prejde najviac všetkými \(n\) prvkami počas celého behu programu. Programu teda hľadanie celkovo zaberie najviac \(n\) času, teda časová zložitosť bude \(O(n+n) = O(n)\). Pamäťová zložitosť je rovnaká, ako v pomalších riešeniach - \(O(n)\).
#include <iostream>
using namespace std;
int main()
{
int n, da, db, k;
std::cin >> n >> da >> db >> k;
int atob [n] = {};
for(int i=0; i<n; i++)
{
std::cin >> atob[i];
}
int btoc [n] = {};
for(int i=0; i<n; i++)
{
std::cin >> btoc[i];
}
//najneskorsi let do ciela, ktorym sa nám Bzuciaka podarilo prinutit ist
int best = 0;
//prvy let do ciela, ktoreho odlet Bzuciak teoreticky stiha
int b_dep_index = 0;
//vyskusame zablokovat vsetky mozne pocty letov prvej linky
for(int offset=0; offset<=k; offset++)
{
//pokial sa nam podari zablokovat vsetky, Bzuciak sa do ciela nevie dostat a hladat dalej nie je potrebne
if(offset >= n)
{
std::cout << -1 << std::endl;
return 0;
}
//cas, v ktorom Bzuciak dorazi do prestupnej stanice
int b_arrival = atob[offset] + da;
//najdeme prvy let dalej, ktory Bzuciak teoreticky stiha
while(btoc[b_dep_index] < b_arrival)
{
++;
b_dep_index }
//Bzuciak neodide tymto letom, ale az o tolko letov neskor, kolko ich este mozeme zablokovat
int b_departure = b_dep_index + k - offset;
//pokial zablokujeme vsetky zvysne lety, do ciela sa nedostane
if(b_departure >= n)
{
std::cout << -1 << std::endl;
return 0;
}
//pokial sme dosiahli zatial najlepsi vysledok, zapamatame si ho
if((btoc[b_departure] + db) > best)
{
= (btoc[b_departure] + db);
best }
}
//vypiseme najneskorsi prichod, aky sme dosiahli
std::cout << best << std::endl;
return 0;
}
= [int(i) for i in input().split()]
n,da,db,k = input().split()
a = input().split()
b for i in range(n):
= int(a[i])
a[i] = int(b[i])
b[i]
#index letu prvej linky, ktorym Bzuciak poleti (rovny poctu zablokovanych letov prvej linky)
= 0
prvy #index letu druhej linky, ktory Bzuciak teoreticky stiha (neratame s blokovanim letov druhej linky)
= 0
druhy #odpoved - index letu druhej linky, ktorym Bzuciak pri vhodnom zablokovani poleti najneskor (rovne -1, pokial sa da Bzuciaka zablokovat uplne)
= -1
o
#vyskusame vsetky mozne pocty zablokovanych letov prvej linky
while prvy <= k:
#pokial na niektorej linke zablokujeme dost letov, aby Bzuciak musel ist indexom letu, ktory uz neexistuje, tak sme ho od ciela odrezali a dalej hladat nemusime
if prvy >= n:
= -1
o break
if druhy >= n:
= -1
o break
#pokial Bzuciak nestiha let ulozeny v premennej druhy, tak ho posunieme, kym ho nebude stihat
if b[druhy] < a[prvy]+da:
+= 1
druhy continue
#pocet letov, ktore este mozeme zablokovat na druhej linke
= k-prvy
ostava #index letu druhej linky, ktorym Bzuciak naozaj poleti
= druhy+ostava
x #pokial uz nestiha ziaden let, je od ciela odrezany
if x >= n:
= -1
o break
#pokial sme dosiahli zatial najlepsi vysledok, zapamatame si ho
if x > o:
= x
o #pokial sme sa dostali az sem, ideme vyskusat dalsi pocet zablokovani na prvej linke
+= 1
prvy
#vypiseme vysledok
if o == -1:
print(-1)
else:
print(b[o]+db)
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ť.