Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | piruete.in, piruete.out | Sursă | Lot 2017 Baraj 2 |
| Autor | Teodor Ionescu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Piruete
Fie un număr natural N şi o încăpere de lungime 2*N+2 văzută ca un interval închis [-N-1,N+1]. În centrul C al camerei (C=0), se află iniţial o balerină pe nume Costelina Salopeta. Ea urmează să efectueze T paşi de dans de lungime 1, făcând primul pas spre dreapta. În cele 2*N puncte distincte de coordonate întregi din interiorul camerei se pot plasa K obstacole. Atunci când balerina ajunge într-un punct cu obstacol, ea se împiedică şi face o piruetă. Astfel ea îşi schimbă sensul de mişcare, iar obstacolul din punctul respectiv dispare.
Nu se pot pune obstacole în punctele de coordonate -N-1, 0 respectiv N+1. Pereţii camerei de coordonate -N-1 respectiv N+1 se consideră obstacole permanente ce nu vor dispărea la atingere, iar punctul de coordonată C=0 reprezintă poziţia iniţială a Costelinei.
Dându-se valorile lui T, N şi K, calculaţi în câte moduri se pot plasa cele K obstacole, astfel încât după o reprezentaţie completă de T paşi Costelina să se întoarcă în punctul de pornire C.
Date de intrare
Fişierul piruete.in conţine pe prima linie numerele naturale T, N şi K separate prin câte un spaţiu, cu semnificaţiile de mai sus.
Date de ieşire
Fişierul piruete.out va conţine pe prima linie un singur număr natural reprezentând răspunsul modulo 109 + 7.
Restricţii
- 0 ≤ T ≤ 200, T este număr par
- 1 ≤ N ≤ 100
- 0 ≤ K ≤ 2*N
- Atentie! Răspunsul se cere modulo 109 + 7
- Pentru 10% din teste avem N ≤ 10
- Pentru 30% din teste avem N ≤ 30
- Pentru 70% din teste avem T ≤ 2*N+2
Exemplu
| piruete.in | piruete.out |
|---|---|
| 6 3 4 | 7 |
Explicaţie
Balerina va efectua T=6 paşi într-o cameră de lungime 2*N+2=2*3+2=8, se plasează K=4 obstacole.
Există 7 modalităţi de amplasare a obstacolelor:
1. [.x.Cxxx] 2. [.xxC.xx] 3. [x.xC.xx]
4. [xx.Cx.x] 5. [xx.Cxx.] 6. [xxxC.x.]
7. [xxxC..x]
S-a notat cu ’.’ poziţia unui loc liber, respectiv cu ’x’ poziţia unui obstacol.
