Fişierul intrare/ieşire: | munte.in, munte.out | Sursă | info-arena 1.0 |
Autor | Dan Popovici | Adăugată de | |
Timp execuţie pe test | 0.025 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Munte
Gheorghe vrea sa cucereasca un munte. El are anumite informatii despre munte. Stie cat de inalt este muntele si care e distanta pana la celaltalta parte a muntelui. El mai are si o lista cu puncte speciale prin care trebuie sa treaca, despre acest puncte stie inaltimea lor si ordinea in care apar, nu stie distanta dintre aceste puncte. Muntele este format din 3 tipuri de teren.
- Tipul 1: teren crescator, unde muntele creste un metru pe verticala pentru fiecare metru pe orizontala.
- Tipul 2: teren drept. Pe acesta portiune terenul nici nu urca nici nu coboara.
- Tipul 3: teren descrescator , unde muntele scade un metru pe verticala pentru fiecare metru pe orizontala.
Cerinta
Gheorghe avand toate aceste informatii, N (inaltimea maxima a muntelui, presupunand ca muntele incepe la nivelul 0 si se termina la nivelul 0), D - distanta pe orizontala a muntelui si inaltimea la fiecare punct special, vrea sa stie cate posibilitati are de a parcurge muntele.
Date de Intrare
Pe prima linie din fisierul munte.in se va afla numarul N - inaltimea maxima a muntelui, D - distanta pe orizontala a muntelui si K - numarul de puncte speciale.
Pe urmatoarele K linii sunt scrise inaltimile punctelor speciale
Date de Iesire
Pe prima linie a fisierului munte.out se va gasi P - numarul de posibilitati de a traversa muntele.
Observatii
- Gheoghe incepe la nivelul 0 si trebuie sa termine la nivelul 0
- Doar incepul si sfasitul au nivelul 0!
Restrictii
- 1 ≤ N ≤ 50
- 1 ≤ D ≤ 100
- 0 ≤ K ≤ 50
- 0 ≤ P ≤ 263-1
Exemple
munte.in | munte.out |
---|---|
2 5 0 | 3 |
Explicatii
Cele 3 posibilitati diferite sunt:
nu este o parcurgere valida pentru ca inaltimea muntelui nu este 2, ci 1
munte.in | munte.out |
---|---|
2 5 2 2 2 | 1 |
Explicatii
Singura parcurgere posibila este cea de sus
munte.in | munte.out |
---|---|
3 8 4 2 2 3 1 | 7 |