Doprogramovanie do: 31. január 2022 23:59
11 dní
Popisy už neodovzdávajte. Ešte stále však môžete odosielať vaše programy, za ktoré dostanete časť bodov.
Počet bodov:
Popis:  12b
Program:  8b

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

\(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.