Fişierul intrare/ieşire:doipe.in, doipe.outSursăWinter Challange, Runda 01, clasele 11-12
AutorBogdan Ionescu, Csaba Patcas, Mugurel Ionut AndreicaAdăugată defireatmyselfBogdan-Alexandru Stoica fireatmyself
Timp execuţie pe test0.6 secLimită de memorie11096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Doipe

Pentru orice permutare de N elemente putem determina un sir de N-1 relatii (relatiile folosite fiind < sau >). Daca al i-lea element al permutarii este mai mic decat al i+1-lea element, al i-lea element al sirului de relatii va fi <, in caz contrar, al i-lea element al sirului de relatii va fi >. De exemplu pentru permutarea (1,3,2,4) de patru elemente determinam sirul (<, >, <). Va trebui sa determinati cate permutari de N elemente exista carora le corespunde un anumit sir de relatii. Ne intereseaza doar restul impartirii acestui numar la 29997.

Date de intrare

Pe prima linie a fisierului doipe.in se va afla numarul T semnificand numarul testelor din fisier. Pe urmatoarele 2*T linii se vor afla informatii despre fiecare test. Astfel pe linia 2*k (1 ≤ k ≤ T) se va alfa numarul N, iar pe linia 2*k+1 (1 ≤ k ≤ T), sirul de relatii.

Date de iesire

Fisierul doipe.out va trebui sa contina exact T linii. Pe a i-a linie va trebui sa se afle raspunsul pentru al i-lea test din fisierul de intrare.

Restrictii

  • 1T20
  • 1N2.000
  • 40% din fisierele de test vor avea toate valorile lui N mai mici sau egale cu 16
  • 70% din fisierele de test vor avea toate valorile lui N mai mici sau egale cu 200

Exemplu

doipe.indoipe.out
3
2
<
10
<><<<><<<
15
<<>>><><>>><><
1
2896
17401
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content