Fişierul intrare/ieşire:stiva2.in, stiva2.outSursăInfoarena Monthly 2012, Runda 2
AutorAndrei CiocanAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test0.15 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/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.instiva2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content