| Fişierul intrare/ieşire: | minesweeper2.in, minesweeper2.out | Sursă | Algoritmiada 2015 Runda 1 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
Minesweeper 2
Akiyama a gasit un nou joc. Minesweeper pe o tabla de 2*N(o tabla cu 2 linii si N coloane). Akiyama stie ca in Minesweeper casutele din matrice sunt de 2 tipuri: cu bombe si fara. Cu toate acestea, acest joc este putin diferit: casutele de pe prima linie nu contin bombe. Akiyama trebuie sa determine cate configuratii posibile sunt pentru cea de-a doua linie, stiind pentru anumite casute de pe linia 1 cu cate bombe se invecineaza (pe verticala sau diagonala).
Date de intrare
Fişierul de intrare minesweeper2.in va contine pe prima linie un numar natural N. Pe urmatoarea linie vor fi N numere naturale, elementul al i-lea reprezentand numarul de bombe cu care se invecineaza casuta de pe linia 1, coloana i. Daca nu se cunoaste acest numar, pe pozitia respectiva se va afla valoarea -1.
Date de ieşire
Fişierul de ieşire minesweeper2.out va contine un singur numar natural reprezentand numarul configuratiilor posibile pentru linia 2 a matricei, modulo 666013.
Restricţii
- 1 ≤ N ≤ 300.000
- Pentru 20% din teste, N ≤ 15
- Pentru alte 30% se cunosc toate cele N casute (nu o sa intalniti valoarea -1)
Exemplu
| minesweeper2.in | minesweeper2.out |
|---|---|
| 3 1 -1 -1 | 4 |
Explicaţie
Exista 4 posibilitati: 011,010,101,100 (unde cu 0 am notat casuta libera si cu 1 bomba)
