Trepte


Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Dorel o supără zilnic pe femeia de servici de la bloc. Vine de la joacă şi, având ghetele murdare, urcă scara proaspăt spălată lăsând urme vizibile.
Se ştie că el poate urca una sau două trepte dintr-o dată. Când păşeşte sărind doar pe următoarea treaptă, aterizează pe un picior şi apoi poate sări mai departe sau poate face o pauză aşezând şi celălalt picior pe treaptă. Dacă păşeşte urcând două trepte dintr-o dată, aterizează pe un picior şi face obligatoriu o pauză aşezând şi celălalt picior pe treaptă.
De exemplu, pe scara cu 5 trepte din figură, Dorel poate urca astfel:

  • urcă prima treaptă pe un picior şi lasă o urmă
  • fără a face pauză, sare în continuare direct pe treapta a treia unde face obligatoriu pauză şi lasă două urme
  • sare pe treapta a patra unde (din motive numai de el ştiute) face iar o pauză, lăsând două urme
  • apoi sare pe treapta a cincea unde lasă o urmă

Cerinţa

Să se determine în câte moduri diferite poate urca Dorel t trepte lăsând în total u urme. Dacă numărul determinat are mai mult de 6 cifre, se va afişa numărul format din ultimele 6 cifre ale rezultatului.

Date de intrare

Pe ecran se află cele două numere t şi u scrise pe aceeaşi linie, cu spaţiu între ele, reprezentând numărul de trepte şi respectiv numărul total de urme lăsate de Dorel.

Date de ieșire

Se va afișa o singura valoare repezentând rezultatul cerut.

Restricţii şi observaţii

  • t, u sunt numere naturale
  • 1 < t <1 000
  • t \le u \le 2t
  • Două moduri sunt distincte, dacă cel puţin o treaptă diferă prin numărul de urme lăsate pe ea. La baza tuturor treptelor este un covoraş, deci acolo Dorel nu lasă urme. Pe ultima treaptă, Dorel poate lăsa fie una, fie două urme, în funcţie de situaţie sau de inspiraţie.

Exemplu

Date de intrare
3 4
Date de ieșire
5
Explicație

Cele 5 moduri de a distribui 4 urme pe 3 trepte, sunt:

tr.1 tr.2 tr.3
   0    2    2
   1    1    2
   1    2    1
   2    0    2
   2    1    1

Comments


  • 1
    Andreos  commented on April 12, 2017, 7:25 p.m.

    Cand o sa puneti si testele la problema? Multumesc!