h2. Date de ieşire
În fişierul de ieşire $turcane.out$ ...
In fişierul de ieşire se va afişa, corespunzător valorii lui $C$, numărul cerut. Rezultatul se va afişa *modulo $10^9^ + 7$*.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ M, N ≤ 1 000$
* $0 ≤ P ≤ N - 1$
* $0 ≤ Q ≤ M - 1$
* $0 ≤ R ≤ _min_(N - 1, M - 1)$
* dacă $P = 0$ nu poate sări la dreapta, dacă $Q = 0$ nu poate sări în jos, iar dacă $R = 0$ nu poate sări pe diagonală
h2. Punctare
table(example). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $26$ | $C = 1$, $M = 1$|
| $2$ | $15$ | $C = 1$, $M = 2$|
| $3$ | $7$ | $C = 1$, $M = 3$|
| $4$ | $7$ | $C = 1$, $1 ≤ M, N ≤ 200$ |
| $5$ | $8$ | $C = 1$, $1 ≤ M, N ≤ 1 000$ |
| $6$ | $11$ | $C = 2$, $1 ≤ M, N ≤ 5$ |
| $7$ | $12$ | $C = 2$, $1 ≤ M, N ≤ 200$ |
| $8$ | $14$ | $C = 2$, $1 ≤ M, N ≤ 1 000$ |
h2. Exemple
table(example). |_. turcane.in |_. turcane.out |_. Explicaţii |
| 1
4 3
2 3 1
| 2
| Notăm cu O{~i~} săritura la dreapta cu i pătrăţele, cu V{~i~} săritura în jos cu i pătrăţele, cu D{~i~} săritura pe diagonală cu i pătrăţele, cu Cd săritura calului spre dreapta-jos şi cu Cj săritura calului spre jos-dreapta.
Numărul minim de sărituri este 2, şi avem şase soluţii: V{~3~} − O{~2~} sau Cd − V{~2~} sau Cj − D{~1~} sau O{~2~} - V{~3~} sau V{~2~} − Cd sau D{~1~} − Cj.
|
| 2
2 3
2 1 1
| 8
| Cele opt moduri de a ajunge în pătrăţelul (2, 3) sunt:
O{~1~} - O{~1~} - V{~1~}, O{~1~} - V{~1~} - O{~1~}, O{~1~} - D{~1~}, O{~2~} - V{~1~}, D{~1~} - O{~1~}, V{~1~} - O{~1~} - O{~1~}, V{~1~} - O{~2~}, Cd
|
h2. Exemplu
Pentru primul exemplu, numărul minim de sărituri este 2. Cele şase soluţii cu număr minim de sărituri sunt ilustrate în figurile următoare:
table(example). |_. turcane.in |_. turcane.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
!problema/turcane?explicatie1.png!
h3. Explicaţie
Pentru al doilea exemplu, numărul soluţiilor distincte este 8. Pentru fiecare soluţie, săriturile ţurcanei sunt ilustrate în figurile următoare:
...
!problema/turcane?explicatie2.png!
== include(page="template/taskfooter" task_id="turcane") ==
