Fişierul intrare/ieşire:marfa2.in, marfa2.outSursăLot Vaslui 2014 Seniori Baraj 5
AutorZoltan SzaboAdăugată dedariusdariusMarian Darius dariusdarius
Timp execuţie pe test0.1 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Marfa2

Maxi a deschis un magazin de mobilă secănd şi are multe comenzi de dulapuri pe care le transportă cu o maşină învechită (e o maşină secănd). Maşina este concepută special pentru a transporta dulapuri grele. Remorca maşinii este împărţită în două părţi (stanga si dreapta). Maşina e aşa de veche încât dacă timp de k zile consecutive o parte a maşinii (stânga sau dreapta) este folosită continuu, se rupe osia pe acea parte. În continuare spunem că rezistenţa maşinii este k. Maşina poate transporta 0, 1 sau 2 dulapuri pe zi şi transporturile vor fi planificate în aşa fel ca maşina să nu se strice.
În oraşul lui Maxi o săptămână are n zile, iar comenzile de transport se repetă identic în fiecare săptămână. De exemplu: rezistenţa maşinii este k=3, o săptămână are n=8 zile, iar comanda săptămânală distribuită pe zile este: 1, 2, 1, 0, 1, 1, 2, 1.

Cerinta

Aflaţi în câte moduri modulo 40099 se pot planifica transporturile pe z zile date, dacă se cunoaşte rezistenţa k a maşinii, numărul n al zilelor din săptămână, respectiv şirul comenzilor săptămânale.

Date de intrare

Fişierul marfa2.in conţine pe prima linie două numere naturale z şi k cu semnificaţiile de mai sus. Pe linia a doua se găseşte numărul n al zilelor din săptămână. Pe linia a treia sunt scrise n numere naturale de valori 0, 1 sau 2 separate prin spaţiu, reprezentând comanda săptămânală de mobilă.

Date de ieşire

Fişierul marfa2.out va conţine un singur număr natural, numărul planificărilor corecte distincte modulo 40099.

Restricţii

  • 3 ≤ k ≤ 4
  • 5 ≤ n ≤ 19
  • 1 ≤ z ≤ 2 000 000 000
  • Atentie! O parte a maşinii (stânga sau dreapta) poate transporta un singur dulap într-o zi.

Exemplu

marfa2.inmarfa2.out
6 3
5
1 0 2 2 0
4

Explicaţie

Se cere numărul planificărilor pe 6 zile, cu rezistenţa maşinii k=3 zile. Săptămâna are 5 zile.
Pentru comanda 1 0 2 2 0 1 avem 4 planificări posibile (comanda din ziua 6 este 1, la fel ca şi prima zi, pentru că se reia săptămâna).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?