| Fişierul intrare/ieşire: | marfa2.in, marfa2.out | Sursă | Lot Vaslui 2014 Seniori Baraj 5 |
| Autor | Zoltan Szabo | Adăugată de |  Marian Darius •dariusdarius |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | marfa2.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).
