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.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.