Fişierul intrare/ieşire:piruete.in, piruete.outSursăLot 2017 Baraj 2
AutorTeodor IonescuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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.inpiruete.out
6 3 4
7
8 3 1
3

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?