Fişierul intrare/ieşire:episoade.in, episoade.outSursăStelele Informaticii 2009, clasele 9-10
AutorSilviu-Ionut GanceanuAdăugată desilviugSilviu-Ionut Ganceanu silviug
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Episoade

Au venit Stelele şi e timpul ca Algorel să apară iar în viaţa mondenă. Ziarele au scris zilele trecute că Algorel în loc să se pregătescă pentru Stele se uită de zor la un serial de desene animate. Şi chiar aşa este... Tocmai a făcut rost de un nou sezon ce are N episoade şi Algorel vrea să ştie în ce ordine ar putea să le vadă (fiindcă nu-i place ordinea originală). El are de la un prieten o expresie care descrie cum se leagă episoadele între ele. Expresia dată respectă anumite reguli:

  • într-o expresie pot apărea numerele de la 1 la N precum şi caracterele: ()>#
  • fiecare număr între 1 şi N apare o singură dată în expresie; fiecărui episod îi corespunde în mod unic un număr
  • un grup de episoade este definit ca un singur episod sau o subexpresie ce decrie relaţii între mai multe episoade
  • > şi # sunt operatori pe grupuri de episoade şi au următoarele proprietăţi:
    • ge1 > ge2 - grupul de episoade ge2 trebuie văzut imediat după grupul de episoade ge1
    • ge1 # ge2 # ... # gek - grupurile de episoade pot fi văzute în orice ordine dar fără să se intercalaze
    • > are prioritate mai mare faţă de #
  • parantezele pot apărea oriunde în expresie cu condiţia să fie bine închise

Pentru a vă ajuta să înţelegeţi regulile mai bine, Algorel vă pune la dispoziţie şi câteva exemple:

ExpresieOrdini posibile
1#2>3>4
1 2 3 4
2 3 4 1
((3>(4#5)>(1#(2>6))))
3 4 5 1 2 6
3 4 5 2 6 1
3 5 4 1 2 6
3 5 4 2 6 1
1>2#3>4#5>6
1 2 3 4 5 6
1 2 5 6 3 4
3 4 1 2 5 6
3 4 5 6 1 2
5 6 1 2 3 4
5 6 3 4 1 2

Algorel are nişte ordini în care ar vrea să vadă episoadele. El vrea să ştie care din aceste ordini sunt posibile luând în considerare regulile descrise de expresie. Cum în ultimul timp s-a tot uitat la desene, nu prea ştie să rezolve problema şi a propus-o la concurs.

Date de intrare

Fişierul de intrare episoade.in va conţine pe prima linie expresia care descrie relaţiile dintre episoade. Pe a doua linie se află două numere: T - numărul de ordini preferate de Algorel şi N - numărul de episoade. Fiecare din următoarele T linii descriu o anumită ordine: pe fiecare linie se află o permutare a numerelor de la 1 la N; numerele sunt separate prin spaţii.

Date de ieşire

În fişierul de ieşire episoade.out veţi afişa T linii: pe linia i veţi scrie 1 dacă ordinea i din fişierul de intrare este posibilă conform regulilor expresiei sau 0 în caz contrar.

Restricţii

  • 1 ≤ N ≤ 100
  • 1 ≤ T ≤ 20
  • Lungimea expresiei nu depăşeşte 1000 caractere
  • Expresia nu conţine spaţii
  • Pentru 50% din teste nu vor aparea paranteze în expresie

Exemplu

episoade.inepisoade.out
1#2>3>4
3 4
1 2 3 4
2 1 3 4
2 3 4 1
1
0
1
((3>(4#5)>(1#(2>6))))
3 6
1 2 3 4 5 6
3 5 4 1 2 6
3 5 1 4 2 6
0
1
0
3#(2#1)
4 3
1 2 3
3 2 1
3 1 2
1 3 2
1
1
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content