Vladko sa veľmi rád hrá počítačové hry. Naposledy si cez letné zľavy v intergalatickom obchode Para™ kúpil vesmírnu plošinovku. Narazil však na náročný level, v ktorom sa nachádza niekoľko políčok vedľa seba, na niektorých sa nachádzajú plošinky. Vladko začína úplne vľavo, cieľ levelu je úplne vpravo. Hýbať sa môže iba doprava. Vždy, keď sa postaví na políčko s plošinkou, môže sa posunúť doprava a plošinka sa za ním rozpadne. Ak sa postaví na políčko bez plošinky, spadne do lávy (musí začať znovu) a na políčku sa objaví nová plošinka.
Úloha
Vladko chce zistiť, na koľko najmenej pokusov vie tento level dokončiť.
Formát vstupu
V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 60\)), ktoré určuje počet políčok vedľa seba.
Nasleduje jeden riadok, na ktorom je medzerou oddelených \(n\) čísiel \(0\) alebo \(1\), ktoré určujú, či sa na danom políčku nachádza plošinka, alebo nie.
| Sada | 1, 2 | 3, 4 | 5, 6 | 7, 8 |
|---|---|---|---|---|
| \(1 \leq n \leq\) | \(10\) | \(30\) | \(60\) | \(60\) |
Formát výstupu
Vypíšte jeden riadok s najmenším počtom pokusov, s ktorým sa dá tento
level vyhrať. Pozor, výstupné číslo sa ti nemusí zmesiť do premennej
typu int v C++.
Príklad
Input:
3
0 0 1Output:
3Potrebuje 3 pokusy: 0 0 1 → 1 0 1 →
0 1 1 → 1 1 1
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.