Fişierul intrare/ieşire:calatorie1.in, calatorie1.outSursăLot Vaslui 2014 - Baraj 4 Juniori
AutorMarius NicoliAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Calatorie1

Doreşti să mergi în vacanţă şi ai hotărât deja destinaţia. Formal, te afli în punctul (0,0) al unui sistem cartezian de axe şi trebuie să ajungi în punctul de coordonate (X,X). Ţara în care te afli are drumuri paralele cu axele de coordonate la fiecare abscisă şi la fiecare ordonată număr natural. În fiecare moment, dacă eşti în punctul de coordonate (a,b), ai 2 variante de deplasare: în punctul (a,b+1) sau în punctul (a+1,b). La fiecare astfel de pas consumi un litru de carburant. Prin unele puncte de forma (a,a) nu poţi trece, iar în celelalte puncte care au abscisa egală cu ordonata poţi trece şi în plus, acolo se află câte o staţie de benzină unde poţi să “faci plinul”. Prin toate punctele care nu au abscisa egală cu ordonata poţi trece dar acolo nu se află staţii de benzină. Rezervorul maşinii tale are o capacitate de K litri.

Cerinţă

Determinaţi toate traseele distincte prin care poţi ajunge la destinaţie. Două trasee sunt distincte dacă diferă prin cel puţin un punct.

Date de intrare

Fişierul calatorie1.in conţine pe prima linie două numere separate printr-un spaţiu, X şi K, cu semnificaţia din enunţ.
Pe linia a 2-a se găseşte un număr N, care reprezintă numărul de puncte de forma (a,a) care nu pot fi traversate. Pe fiecare dintre următoarele N linii se află câte un număr a, cu semnificaţia că punctul (a,a) nu poate fi vizitat.

Date de ieşire

Fişierul calatorie1.out conţine pe prima linie un singur număr natural reprezentând valoarea cerută, modulo 997.

Restricţii

  • 1 ≤ X ≤ 50000
  • 1 ≤ K ≤ 50
  • 0 ≤ N ≤ 10
  • Călătoria începe cu rezervorul plin;
  • Se garantează că există cel puţin un drum;

Exemplu

calatorie1.incalatorie1.out
3 10
1
1
8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?