Zadanie

Táto úloha sa dá nahradiť riešením sady loops_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Mišovi “Žabovi” Anderlemu na

V T21 sa počas dňa vyskytuje veľa programátorov a tí chcú, samozrejme, používať svoje notebooky. Notebooky musia byť zapojené do elektriny, keďže baterka sa im minula pri používaní počas prednášok. V T2 je našťastie obrovská predlžovačka s \(n\) zásuvkami.

Problém však nastal, keď si \(m\) vedúcich kúpilo nové Macbooky, ktoré majú najmodernejšie, revolučné a absolútne nepraktické zástrčky.2 Sú o niečo širšie ako tie klasické a aj keď sa dajú strčit do slovenskej zásuvky, na každej strane z nej trochu prečnievajú. Keď ich teda zastrčíte do predlžovačky, obe susedné zásuvky na predlžovačke sú blokované a nedá sa do nich vložiť žiadna iná zástrčka. To ale výrazne obmedzuje efektivitu spomínanej predlžovačky a KSP-ákov trápi, či si vôbec vedia všetci nabíjať svoje notebooky súčasne.

Úloha

Máme predlžovačku s \(n\) zásuvkami, \(m\) počítačov so širokými macovskými zástrčkami a \(k\) počítačov s normálnymi (úzkymi) zástrčkami. Zistite, či sa všetkých \(m+k\) zástrčiek dá povkladať do predlžovačky. Normálna zástrčka zaberie práve jednu zásuvku a macovská zástrčka zaberie jednu zásuvku a zablokuje obe susedné zásuvky. Medzi dvoma macovskými zástrčkami však stačí mať jednu voľnú zásuvku.

Formát vstupu

Na prvom riadku dostanete \(n\) (\(1 \leq n \leq 10^9\)) – počet zásuviek v predlžovačke. Na druhom riadku budú čísla \(m\) a \(k\) (\(0 \leq m, k \leq 10^9\)) – počet macovských a počet normálnych zástrčiek.

Formát výstupu

Vypíšte ano ak sa notebooky zapojiť dajú a nie, ak to žiadnym spôsobom nejde.

Príklad

Input:

7
3 1

Output:

ano

Rozložiť sa dajú napríklad takto: momonom (macovské – m, normálne – n, prázdna zásuvka – o). Všimnite si, že širokým koncovkám stačí medzi sebou iba jedna medzera.

Input:

5
1 2

Output:

ano

Napríklad rozloženie nomon.

Input:

2
1 2

Output:

nie

Žiadnym spôsobom sa nepomestia, nemáme totiž ani dostatok zásuviek.

Input:

4
2 1

Output:

nie

  1. Tajná miestnosť KSP a Prask vedúcich na Matfyze.↩

  2. Ak si ešte stále nie ste istí pri používaní slov zástrčka a zásuvka, tento článok: http://slovensky.diskusneforum.sk/clanky/zastrcka-nie-je-zasuvka/ vám určite pomôže.↩

Máme predlžovačku s \(n\) zásuvkami, do ktorej chceme vsunúť \(k\) normálnych úzkych zástrčiek a \(m\) širokých zástrčiek, ktoré po zasunutí zaberú miesto aj v susedných zásuvkách. Ako sa však dalo všimnúť v ukážkovom príklade, tak vieme zastrčiť dve široké zástrčky tak, že je medzi nimi len jedna voľná zásuvka.

Je jasné, že hlavný problém je ako pozastrkávať široké zástrčky tak, aby zabrali čo najmenej miesta. Zdá sa, že vhodné miesto pre širokú zástrčku je na kraji predlžovačky. Ak ju totiž dáme na kraj, zaberie iba dve zásuvky, z jednej strany totiž prečnieva ponad koniec predlžovačky. Jediná susedná zásuvka krajnej zásuvky bude určite zablokovaná, do tretej zásuvky v poradí však môžeme dať aj úzku aj širokú zástrčku. Zbavili sme sa teda jednej širokej zástrčky a našu predlžovačku sme si skrátili na \(n-2\) zásuviek.

Túto myšlienku sa nám však oplatí zopakovať opäť, až kým nevyčerpáme všetky široké zástrčky. Tie sme teda nastrkali čo najviac na jeden kraj predlžovačky čo najbližšie k sebe, každá zabrala dve zásuvky, preto nám zostalo \(n-2m\) zásuviek, do ktorých chceme vložiť \(k\) úzkych zástrčiek. Je jasné, že to sa bude dať spraviť iba ak je \(u \leq n-2m\).

Takéto riešenie nie je problém naprogramovať, stačí predsa v čase \(O(1)\) overiť túto jedinú podmienku. Teda takmer. Špeciálny prípad nastane, ak bude \(k=0\), teda máme iba široké zástrčky. Vtedy nám postačuje iba \(2m-1\) zásuviek. Takéto riešenie nám už dá na testovači plný počet bodov.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main () {
  long long n, m, k;
  cin >> n >> m >> k;
  n -= 2*m;
  if (k == 0) {
    n++;
  }
  if (n < k) {
    cout << "nie\n";
  } else {
    cout << "ano\n";
  }
}

Riešenie, ktoré sme vymysleli nazývame pažravé1. Používame tam totiž tvrdenie: Určite bude najlepšie, ak všetky široké zástrčky dáme vedľa seba na kraj predlžovačky. Platí to však vždy? To musíme dokázať v popise.

Najlepšie sa takéto tvrdenie dokazuje nasledovne. Zoberieme si nejaké rozmiestnenie zástrčiek do predlžovačky. Ľubovoľné také rozmiestnenie. No a potom ukážeme, že takéto rozmiestnenie vieme upraviť na naše rozmiestnenie, ktoré má široké zástrčky vedľa seba na (ľavom) kraji predlžovačky.

Zoberme si ľubovoľné rozmiestnenie zástrčiek. Prvé čo spravíme je, že posunieme všetky zástrčky čo najviac doľava, aby sme odstránili zbytočné medzery (samozrejme, nejaké zásuvky zostanú voľné lebo budú zakryté širokými zástrčkami). Následne, ak to nevyzerá ako naše riešenie, tak niektoré dve široké zástrčky nie sú pri sebe. Medzi nimi je teda jedna, alebo viac úzkych zástrčiek.

Ak "o" označuje prázdnu zásuvku, "u" zásuvku s úzkou zástrčkou a "s" zásuvku so širokou zástrčkou, tak kus predlžovačky, kde niečo takéto vznikne môže vyzerať "osouuoso". Nič však nepokazíme, ak tieto zástrčky prepojíme do tvaru "ososouuo". Akurát sme odstránili problém širokých zástrčiek, ktoré neboli vedľa seba. Opakovaním tohto postupu naozaj vytvoríme rovnaké riešenie ako náš program – široké zástrčky na kraji predlžovačky.

Vidíme teda, že ľubovoľné riešenie vieme prerobiť na nami navrhnuté riešenie, preto je takéto riešenie určite správne.

  1. Po anglicky greedy.↩

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ť.