== include(page="template/taskheader" task_id="reactii") ==
Să considerăm o secvenţă de n substanţe chimice s=s1,s2,…,sn. Substanţele sunt numerotate distinct de la 1 la n şi fiecare substanţă apare în secvenţa s o singură dată.
Să considerăm o subsecvenţă sij=(sisi+1…sj) şi să notăm cu minij şi maxij cel mai mic, respectiv cel mai mare număr din subsecvenţă. Subsecvenţa respectivă constituie un interval dacă ea conţine toate numerele naturale cuprinse între minij şi maxij.
Cu substanţele din secvenţa s se vor efectua diferite experimente. În timpul unui experiment pot reacţiona două substanţe alăturate si şi si+1 doar dacă numerele lor de ordine sunt consecutive. În urma reacţiei se obţine o nouă substanţă, formată din substanţele care au reacţionat, notată (si,si+1). Mai mult, substanţele obţinute pot reacţiona dacă ele sunt alăturate, iar prin reunirea subsecvenţelor de substanţe ce le compun se obţine un interval.
Experimentul este declarat reuşit dacă în final, urmând regulile de mai sus, se obţine o singură substanţă formată din toate cele n substanţe din secvenţa s, aceasta fiind declarată stabilă.
De exemplu, pentru n=6 substanţe şi secvenţa s=6,3,2,1,4,5 se poate proceda astfel:
|_.Etapa |_.Acţiune |_. Configuraţie |
|1. |Secvenţa iniţială | 6 3 2 1 4 5 |
|2. |Reacţionează substanţa 2 cu 1 şi se obţine substanţa (2,1) |6 3 (2,1) 4 5 |
|3. |Reacţionează substanţa 4 cu substanţa 5 şi se obţine substanţa (4,5) |6 3 (2,1)(4,5) |
|4. |Reacţionează substanţa 3 şi (2,1) rezultând (3,2,1) |6 (3,2,1)(4,5) |
|5. |Reacţionează substanţele (3,2,1) şi (4,5) rezultând substanţa (3,2,1,4,5) |6 (3,2,1,4,5) |
|6. |Reacţionează substanţa 6 cu (3,2,1,4,5) şi rezultă substanţa stabilă (6,3,2,1,4,5). |(6,3,2,1,4,5) |
Să considerăm o secvenţă de $N$ substanţe chimice $S$ = s{~1~},s{~2~},…,s{~n~}. Substanţele sunt numerotate distinct de la $1$ la $N$ şi fiecare substanţă apare în secvenţa $S$ o singură dată. Să considerăm o subsecvenţă s{~ij~} = (s{~i~},s{~i+1~},...,s{~j~}) şi să notăm cu $min${~ij~} şi $max${~ij~} cel mai mic, respectiv cel mai mare număr din subsecvenţă. Subsecvenţa respectivă constituie un interval dacă ea conţine toate numerele naturale cuprinse între $min${~ij~} şi $max${~ij~}. Cu substanţele din secvenţa s se vor efectua diferite experimente. În timpul unui experiment pot reacţiona două substanţe alăturate s{~i~} şi s{~i+1~} doar dacă numerele lor de ordine sunt consecutive. În urma reacţiei se obţine o nouă substanţă, formată din substanţele care au reacţionat, notată (s{~i~},s{~i+1~}). Mai mult, substanţele obţinute pot reacţiona dacă ele sunt alăturate, iar prin reunirea subsecvenţelor de substanţe ce le compun se obţine un interval.
Experimentul este declarat reuşit dacă în final, urmând regulile de mai sus, se obţine o singură substanţă formată din toate cele $N$ substanţe din secvenţa S, aceasta fiind declarată stabilă.
De exemplu, pentru $N$={$6$} substanţe şi secvenţa S=({$6$}, $3$, $2$, $1$, $4$, $5$) se poate proceda astfel:
|_. Etapa |_. Acţiune |_. Configuraţie |
|1 |Secvenţa iniţială | 6 3 2 1 4 5 |
|2 |Reacţionează substanţa 2 cu 1 şi se obţine substanţa (2,1) |6 3 (2,1) 4 5 |
|3 |Reacţionează substanţa 4 cu substanţa 5 şi se obţine substanţa (4,5) |6 3 (2,1)(4,5) |
|4 |Reacţionează substanţa 3 şi (2,1) rezultând (3,2,1) |6 (3,2,1)(4,5) |
|5 |Reacţionează substanţele (3,2,1) şi (4,5) rezultând substanţa (3,2,1,4,5) |6 (3,2,1,4,5) |
|6 |Reacţionează substanţa 6 cu (3,2,1,4,5) şi rezultă substanţa stabilă (6,3,2,1,4,5). |(6,3,2,1,4,5) |
h2. Cerinta
h2. Date de intrare
Fişierul de intrare reactii.in conţine pe prima linie numărul natural n, numărul de substanţe. Pe cea de a doua linie se află un număr natural m, reprezentând numărul de secvenţe de n substanţe din fişierul de intrare. Fiecare dintre următoarele m linii conţine câte n numere naturale distincte, separate prin câte un spaţiu, reprezentând o secvenţă de n substanţe.
Fişierul de intrare $reactii.in$ conţine pe prima linie numărul natural $N$, numărul de substanţe. Pe cea de a doua linie se află un număr natural $M$, reprezentând numărul de secvenţe de $N$ substanţe din fişierul de intrare. Fiecare dintre următoarele $M$ linii conţine câte $N$ numere naturale distincte, separate prin câte un spaţiu, reprezentând o secvenţă de $N$ substanţe.
h2. Date de ieşire
Fişierul de ieşire reactii.out conţine, pentru fiecare secvenţă de substanţe din fişierul de intrare, câte o linie, pe care este afişată valoarea 1 dacă pentru secvenţa respectivă se poate obţine o substanţă stabilă sau valoarea 0 în caz contrar.
Fişierul de ieşire $reactii.out$ conţine, pentru fiecare secvenţă de substanţe din fişierul de intrare, câte o linie, pe care este afişată valoarea $1$ dacă pentru secvenţa respectivă se poate obţine o substanţă stabilă sau valoarea $0$ în caz contrar.
h2. Restricţii
* 2 ≤ n ≤ 15000
* 1 ≤ m ≤ 20
* $2$ ≤ $N$ ≤ $15000$
* $1$ ≤ $M$ ≤ $20$
* La un moment dat pot reacţiona doar două substanţe.
* Nu din orice secvenţă de substanţe se poate obţine în urma reacţiilor o substanţă finală stabilă.
