Fişierul intrare/ieşire:cabane.in, cabane.outSursăLot 2005
AutorMarius AndreiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test1.95 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cabane

Balaurul Arhirel este pus in fata unei mari dileme. Fara sa vrea, a ajuns in muntii Romaniei si trebuie sa parcurga un traseu de-a lungul caruia sa viziteze N cabane. El poate porni de la orice cabana, dar trebuie sa treaca pe la fiecare cabana exact o data.
Cabanele sunt numerotate de la 1 la N, iar fiecare se afla la o inaltime egala cu indicele sau exprimat in metri. Deplasarea intre oricare doua cabane se face in linie dreapta (creste sau scade constant). Problema este ca Balaurul nu poate urca sau cobori mai mult de K metri intre oricare doua cabane consecutive de pe traseu, deci traseul trebuie sa fie bine ales.
Norocul Balaurului este ca exista multe posibilitati. Ghinionul vostru este ca Balaurul stie cate posibilitati sunt si vrea sa vada daca si voi stiti.
Pentru valorile N si K date, determinati numarul de posibilitati de a vizita fiecare dintre cele N cabane exact o data, astfel incat diferenta de nivel (in valoare absoluta) dintre oricare doua cabane vizitate consecutiv sa fie de maxim K metri. Rezultatul trebuie sa fie dat modulo 30103 (restul impartirii la 30103).

Date de intrare

Fisierul de intrare cabane.in va contine pe prima linie valorile N si K separate printr-un spatiu.

Date de iesire

Fisierul de iesire cabane.out va contine o singura linie pe care va fi scris numarul total de posibilitati modulo 30103.

Restrictii

  • K ≤ N ≤ 200
  • 1 ≤ K ≤ 6

Exemplu

cabane.incabane.out
4 2
12

Explicatie

Din cele 24 de trasee posibile 12 sunt valide:
1 2 3 4, 1 2 4 3, 1 3 2 4, 1 3 4 2,
2 1 3 4, 2 4 3 1, 3 1 2 4, 3 4 2 1,
4 2 1 3, 4 2 3 1, 4 3 1 2, 4 3 2 1
Iar celelalte 12 nu sunt. De exemplu 2 1 4 3 nu e valid pentru ca intre cabana 1 si cabana 4 este o diferenta de 3 metri.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content