Zadanie
Ako sa sa dni krátili a noci predlžovali, Naďka prehľadávala celú T2 v nádeji, že nájde čokoládu, ktorú plánuje doniesť na kapustnicu Trojstenu ako zákusok. “Aha, tak tu si!” zvolala, keď ju konečne našla v Krtkovom zakladači. Naďkina čokoláda však nebola len tak obyčajná. Mala rozmery \(1 \times k\) a každá tablička bola buď mliečna, alebo horká. Dokonca sa Naďka rozhodla, že túto čokoládu nerozdá len tak náhodným spôsobom – každému Trojstenákovi na kapustnici dá jeden súvislý kus čokolády, ktorý je dlhý najmenej \(l\) a najviac \(r\) a obsahuje práve jednu horkú tabličku. Dokáže Naďka takúto čokoládu rozdeliť medzi Trojstenákov na kapustnici bez toho, aby jej nejaká zvýšila?
Úloha
Na kapustnicu príde \(n\) Trojstenákov medzi ktorých chce Naďka rozdeliť svoju čokoládu s rozmermi \(1 \times k\). Platia nasledujúce pravidlá:
- každá tablička čokolády je buď mliečna, alebo horká,
- každý Trojstenák dostane práve jeden súvislý kus čokolády, ktorého najmenšia dĺžka môže byť \(l\) a najväčšia \(r\),
- každý Trojstenák dostane práve jednu horkú tabličku.
Vašou úlohou je povedať, či Naďka dokáže čokoládu rozdeliť bez toho, aby jej nejaký kúsok ostal.
Formát vstupu
V prvom riadku vstupu dostanete štyri celé čísla oddelené medzerami:
- počet Trojstenákov na kapustnici \(n\),
- počet tabličiek čokolády \(k\),
- najkratší možný kus čokolády \(l\),
- najdlhší možný kus čokolády \(r\).
Na nasledujúcom riadku dostanete popis čokolády, ktorý obsahuje zasebou idúce 0
a 1
, pričom 0
je mliečna tablička a 1
je horká tablička.
Formát výstupu
Vypíšte jeden riadok obsahujúci odpoveď ano
, ak sa čokoláda dá rozdeliť bez toho, aby nejaká zvýšila alebo nie
, ak sa to nedá.
Obmedzenia
Sú \(4\) sady vstupov po \(2\) body. Platia v nich nasledovné obmedzenia:
Sada | \(1\) | \(2\) | \(3\) | \(4\) |
---|---|---|---|---|
\(1 \leq n \leq\) | \(10\) | \(100\) | \(1\,000\) | \(2\,000\) |
\(1 \leq k \leq\) | \(200\) | \(10\,000\) | \(500\,000\) | \(1\,000\,000\) |
\(1 \leq l \leq\) | \(10\) | \(50\) | \(500\) | \(500\) |
\(l \leq r \leq\) | \(20\) | \(100\) | \(750\) | \(750\) |
Príklad
Input:
3 11 2 4
01000010001
Output:
ano
Naďka môže čokoládu rozdeliť napríklad takto: 0100 0010 001
Input:
3 11 2 4
01000000101
Output:
nie
Naďka nevie rozdeliť čokoládu tak, aby splnila všetky podmienky a aby jej žiadna tablička nezvýšila.
Prvá vec, ktorú si treba uvedomiť pri riešení tejto úlohy je, že ak má čokoláda viac alebo menej horkých tabličiek ako je počet Trojstenákov, tak odpoveď je automaticky nie
, pretože nevieme splniť všetky podmienky.
Pomalé riešenie
Asi najviac priamočiare riešenie je vyskúšať postupne všetky možné rozdelenia čokolády a skontrolovať, či v každom súvislom kúsku je práve jedna horká tablička. Takéto niečo vieme urobiť jednoduchou rekurziou. Začneme pri tom, že naša rekurzia odkrojí z čokolády súvislý kus, ktorý má \(l\) tabličiek. Akonáhle sme čokoládu rozdelili na \(n\) kusov – aby každý Trojstenák dostal jeden kus – skontrolujeme, či sú všetky podmienky splnené a či nám žiadna čokoláda nezvýši. Ak je všetko v poriadku, môžeme vypísať ano
. Ak niektorá z podmienok splnená nie je, pokračujeme ďalej v rekurzii. Rekurzia bude rozdelovať čokoládu na kúsky s \(l\) až \(r\) tabličkami. Akonáhle sme prešli všetky možnosti ako sa dá čokoláda rozdeliť a ani raz sme nenašli riešenie, ktoré spĺňa všetky podmienky, vypíšeme nie
.
Vzorové riešenie
Na vyriešenie tejto úlohy však nepotrebujeme zbytočne skúšať všetky existujúce možnosti. Pre každú horkú tabličku nás zaujíma, na akom indexe sa nachádza, aby sme vedeli odvodiť intervaly, v ktorých môžeme rozdeliť čokoládu, aby sme určite mali v každom kúsku práve jednu horkú tabličku. Preto si prejdeme celú čokoládu a zapíšeme si indexy horkých tabličiek do poľa \(h\). Na čokoládu pozeráme zľava doprava a počiatočný interval je \((0, 0)\), čo je na začiatku čokolády. Čísla v intervaloch ukazujú na miesta medzi dvoma tabličkami. Ak máme napríklad interval \((2, 5)\), tak čokoládu môžeme rozdeliť pred tabličkou na druhom indexe až za tabličkou na štvrtom indexe.
Vytvoríme si funkciu, ktorá pre každú horkú tabličku vypočíta interval, v ktorom sa môže rozdeliť čokoláda za danou tabličkou. Začiatok intervalu musí byť vždy aspoň o \(l\) väčší ako predchádzajúci začiatok intervalu, pretože najmenej \(l\) tabličiek môžeme oddeliť od zvyšku čokolády. Avšak, môže sa nám stať, že aj keby oddelíme kus čokolády s \(l\) tabličkami, tak medzi nimi nebude horká tablička. Takýmto možnostiam sa chceme vyhnúť, pretože hneď vieme, že nespĺňajú všetky podmienky a nemá zmysel s nimi ďalej pokračovať. V takomto prípade musí byť začiatok intervalu za horkou tabličkou. Takže začiatok intervalu sa dá napísať ako \(\max(\mathrm{zaciatok\_predchadzajuceho\_intervalu} + l, h[i] + 1)\).
Koniec intervalu musí byť vždy maximálne o \(r\) väčší ako koniec predchádzajúceho intervalu, pretože môžeme od čokolády oddeliť kus s maximálne \(r\) tabličkami. Môže však nastať situácia, kedy v týchto \(r\) tabličkách už bude aj druhá horká tablička, čo nechceme, pretože by sme nesplnili podmienky. Takže chceme čokoládu rozdeliť najviac pred nasledujúcou horkou tabličkou. Koniec intervalu preto vieme zapísať ako \(\min(\mathrm{koniec\_predchadzajuceho\_intervalu} + r, h[i + 1])\).
Aby kód fungoval poriadne, musíme si na koniec poľa \(h\) pridať aj index \(k\), čo je koniec čokolády, pretože to je najďalej, kde vieme rozdeliť čokoládu. Chceme sa vyhnúť tomu, že by sme chceli rozdeliť čokoládu za jej koncom, pretože toľko čokolády na rozdávanie nemáme.
Vždy, keď si vypočítame interval pre danú horkú tabličku, skontrolujeme či začiatok je menší alebo rovný koncu intervalu. Ak by bol začiatok väčší, tak môžeme rovno vypísať nie
, pretože neexistuje miesto, kde by sme dokázali čokoládu rozdeliť, aby sme splnili všetky podmienky.
Úplne na koniec nás zaujíma posledný interval. Ak koniec tohoto intervalu je menší ako celková dĺžka čokolády \(k\), tak Naďka nevie rozdať celú čokoládu a vypíšeme nie
. Ak však prešlo hladko a nestretli sme sa so žiadnym problémom, môžeme vypísať ano
, pretože sme splnili všetky podmienky a každý Trojstenák dostal svoj kus čokolády, bez toho, aby Naďke nejaká zvýšila.
Časová a pamäťová zložitosť
Na začiatku sme prešli celú čokoládu, aby sme zistili, na akých indexoch sú horké tabličky – \(O(k)\). Potom sme \(n\)-krát vypočítali interval rezu – \(O(n)\). Dokopy je teda časová zložitosť \(O(k + n)\).
Pamätáme si čokoládu a nejaké konštantne veľké premenné k tomu, takže pamäťová zložitosť je \(O(k)\).
import sys
= map(int, input().split())
n, k, l, r = input()
cokolada
= list()
horke = 0
pocet_horkych = (0, 0)
interval
def rez(interval, i):
return (max(horke[i] + 1, interval[0] + l), min(horke[i + 1], interval[1] + r))
for i in range(k):
if cokolada[i] == '1':
+= 1
pocet_horkych
horke.append(i)# na koniec poľa nesmieme zabudnúť pridať koniec čokolády
horke.append(k)
if pocet_horkych != n:
print('nie')
sys.exit()
for i in range(n):
= rez(interval, i)
interval if interval[0] > interval[1]:
print('nie')
sys.exit()
if interval[1] < k:
print('nie')
else:
print('ano')
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ť.