| Fişierul intrare/ieşire: | calatorie1.in, calatorie1.out | Sursă | Lot Vaslui 2014 - Baraj 4 Juniori |
| Autor | Marius Nicoli | Adăugată de |  Alexandru Valeanu •AlexandruValeanu |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | calatorie1.out |
|---|---|
| 3 10 1 1 | 8 |
