Fişierul intrare/ieşire:minesweeper2.in, minesweeper2.outSursăAlgoritmiada 2015 Runda 1
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inminesweeper2.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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?