| Fişierul intrare/ieşire: | stiva2.in, stiva2.out | Sursă | Infoarena Monthly 2012, Runda 2 |
| Autor | Andrei Ciocan | Adăugată de |  Mr. Noname •cezar305 |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Stiva2
In mitologia Acaerg, Mivas era zeul focului, iar Nivas zeul ghetii. Din cauza ca se plictiseau la Congresul Anual al Zeilor, cei doi au inceput sa se joace, folosind stiva pe care au gasit-o intamplator in sala. Puterea lui Mivas este de a crea globuri de foc, iar cea a lui Nivas de a crea cuburi de gheata. In fiecare dintre cele N secunde pe care le au la dispozitie, exact unul dintre ei isi foloseste puterea si isi introduce creatia in stiva. Atunci cand un cub de gheata este asezat in stiva peste un glob de foc (sau invers), cele doua elemente se transforma in abur si dispar. Din cauza ca stiva este fragila, un element introdus in stiva la secunda i, trebuie sa iasa cel tarziu la momentul i + K, in caz contrar stiva stricandu-se. Mivas si Nivas se intreaba in cate moduri pot introduce globuri de foc si cuburi de gheata in stiva, astfel incat aceasta sa nu se strice pe parcursul celor N secunde si la sfarsit sa fie goala? Ei stiu ca rezultatul poate fi destul de mare, asa ca se multumesc cu restul impartirii acestuia la 9973.
Date de intrare
Fişierul de intrare stiva2.in va contine pe prima linie numarul N de secunde, si K, durata maxima de viata a unui element in stiva.
Date de ieşire
În fişierul de ieşire stiva2.out se va afisa pe prima linie numarul de posibilitati, modulo 9973.
Restricţii
- 1 ≤ N ≤ 1000
- 1 ≤ K ≤ N
- Singura modalitate de a scoate un element din stiva este de a aseza un element de celalalt tip peste el.
Exemplu
| stiva2.in | stiva2.out |
|---|---|
| 4 2 | 4 |
Explicaţie
Modalitatile de introducere a globurilor de foc/gheata in stiva sunt: FGGF, GFFG, FGFG, GFGF. Observatie: FFGG nu este o introducere valida a globurilor. Prin G este reprezentata introducerea in stiva a unui glob de gheata, iar prin F operatia similara pentru un glob de foc.
