Zadanie

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\) KSP-ákov 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á KSP miestnosť 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 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, dve široké zástrčky vieme zastrčiť 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á, no 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 umiestníme čo najviac na jeden kraj predlžovačky, čo najbližšie k sebe. Každá zaberie dve zásuvky a preto nám zostane \(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 \(k \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 \(2m-1\) zásuviek. Takéto riešenie nám už dá na testovači plný počet bodov.

#include <iostream>
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. Všimli sme si, že je výhodné dať jednu širokú zástrčku na kraj predlžovačky. Pažravo sme ale usúdili, že je výhodné dať všetky široké zástrčky k sebe 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é ľubovoľné platné rozmiestnenie zástrčiek do predlžovačky. 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.

Prvé, čo spravíme s ľubovoľným platným rozmiestnením, bude, ž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 toto rozmiestnenie ešte 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ť ako "souuoso". Nič však nepokazíme, ak tieto zástrčky prepojíme do tvaru "sosouuo". 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ť.