Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | vecini3.in, vecini3.out | Sursă | Science On 2021, clasa 9 |
| Autor | Mihaela Cismaru | Adăugată de |  Todoran Alexandru Raul •alextodoran |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 268435 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Vecini3
Suntem în anul 2030 şi ăn sfârşit pandemia s-a încheiat iar elevii s-au întors la şcoală. La ora de sport sunt N copii numerotaţi cu numerele naturale de la 1 la N. La început, aceştia sunt aşezaţi în linie dreaptă într-o anumită ordine. Aşezarea copiilor poate fi văzută ca pe o permutare A a numerelor de la 1 la N. Copiii joacă un joc în care au voie să efectueze următoarele 2 tipuri de operaţii:
- Vecinii copilului de pe poziţia i îşi schimbă locurile (1 < i < numărul de copii rămaşi in joc).
- Vecinii copilului de pe poziţia i sunt eliminaţi din joc (1 < i < numărul de copii rămaşi in joc).
Chiar dacă una dintre operaţii implică eliminarea a doi copii, acest joc nu este despre un singur câştigător, ci despre lucrul în echipă. Aşadar, profesorul de sport le cere copiiloe să colaboreze şi, plecând de la configuraţia iniţială A şi folosind cele două tipuri de operaţii, să ajungă la o configuraţie finală B. Configuraţia finală B este formată dintr-o submulţime de M copii (M ≤ N) a tuturor celor N copii aşezaţi în linie dreaptă într-o anumită ordine. Se garantează că N şi M au aceeaşi paritate. Copiii cunt puţin bulversaţi şi ar vrea mai întâi să ştie dacă măcar este posibil să ajungă din configuraţia iniţială A la cea finală B. Ai putea să îi ajuţi şi să le răspunzi la această întrebare?
Date de intrare
Prima linie a fişierului de intrare vecini3.in conţine numărul T de teste din cadrul inputului. Urmează cele T teste.
Fiecare test conţine pe prima linie numerele naturale N şi M. Pe a doua linie a fiecărui test se află N numere reprezentând configuraţia iniţială A. Pe a treia linie a fiecărui test se află M numere reprezentând configuraţia finală B. Şirul A este o permutare a numereleor de la 1 la N, iar şirul B este alcătuit din M numere distincte cu valori cuprinse între 1 şi N.
Date de ieşire
Fişierul de ieşire vecini3.out va conţine răspunsul pentru cele T teste, pe rânduri separate. Dacă este posibil să se ajungă din configuraţia iniţială în cea finală atunci se afişează 1, altfel se afişează 0.
Restricţii generale
- 2 ≤ M ≤ N
- Suma N-urilor a celor T teste este ≤ 106
- N şi M au aceeaşi paritate
Subtaskuri
Subtask 1 (10 puncte)
- N = M în toate cele T teste ale fişierului
- T ≤ 10
- 2 ≤ N ≤ 8
Subtask 2 (20 puncte)
- N=M în toate cele T teste ale fişierului
Subtask 3 (20 puncte)
- T ≤ 10
- 2 ≤ N ≤ 8
Subtask 4 (50 puncte)
- Fără restricţii suplimentare
Exemplu
| vecini3.in | vecini3.out |
|---|---|
| 4 5 5 3 1 4 2 5 5 2 3 1 4 4 4 3 2 4 1 1 2 4 3 6 4 1 6 4 3 2 5 6 3 4 5 5 3 4 2 3 1 5 2 4 1 | 1 0 1 0 |
Explicaţie
În primul test, copiii pot efectua următoarele operaţii:
[3, 1, 4, 2, 5] → interschimbă vecinii lui 2 → [3, 1, 5, 2, 4] → interschimbă vecinii lui 1 → [5, 1, 3, 2, 4] → interschimbă vecinii lui 3 → [5, 2, 3, 1, 4]
În al doilea test, nu este posibil să se obţină [1, 2, 4, 3] plecând de la [3, 2, 4, 1].
În al treilea test, copiii pot efectua următoarele operaţii:
[1, 6, 4, 3, 2, 5] → interschimbă vecinii lui 3 → [1, 6, 2, 3, 4, 5] → elimină vecinii lui 6 → [6, 3, 4, 5].
În al patreulea test, nu este posibil să se obţină [2, 4, 1] plecând de la [4, 2, 3, 1, 5].
