| Fişierul intrare/ieşire: | pokemon3.in, pokemon3.out | Sursă | ONIS 2016 Runda Online |
| Autor | Adrian Budau | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pokemon3
Dupa indelungate cautari Ash, eroul nostru, a prins toti pokemonii posibili de fiecare tip. Tot ce ii ramane acum de facut e sa castige ultimul campionat, care se desfăşoară in castelul Pokemon unde sunt M antrenori, fiecare cu 3 pokemoni. Ash poate sa-si construiasca ce echipa vrea inainte de a intra in castel, dar nu are voie sa mai schimbe ceva dupa ce intra. Inauntru inainte de fiecare lupta el va alege intre 1 si 3 pokemoni pentru a-i folosi. O lupta decurge in felul urmator:
1. Adversarul trimite urmatorul pokemon din cei ramasi.
2. Ash alege un pokemon sa-l trimita in lupta.
3. Daca unul din pokemoni este supereficient impotriva celuilalt acesta castiga batalia, altfel oricare din cei doi poate castiga.
4. Pokemonul care pierde batalia este eliminat, el nemaiputand fi folosit pentru tot restul campionatului.
5. Daca atat Ash cat si adversarul sau mai au pokemoni se repeta de la pasul 1.
Pokemonii pot fi clasificati in N categorii, iar pentru fiecare doua tipuri i si j se stie daca tipul i este supereficient impotriva tipului j. Evident daca tipul i este supereficient impotriva tipului j, atunci tipul j nu poate fi supereficient impotriva tipului i.
Ash isi doreste sa castige cele M lupte din prima, iar din acest motiv el va alege intotdeauna intr-o lupta un pokemon supereficient fata de cel al adversarului sau. Stiind dinainte listele de tipuri ale pokemonilor celor M adversari, Ash va roaga sa-i spuneti care este numarul minim de pokemoni pe care trebuie sa ii aduca ca sa castige campionatul.
Date de intrare
Fişierul de intrare pokemon3.in va contine pe prima linie N, M numarul de tipuri diferite de pokemoni, respectiv numarul de adversari din castel.
Urmatoarele N linii vor contine N valori separate prin spatiu 0 sau 1. Daca a j-a valoare de pe linia i este 1 inseamna ca tipul i este supereficient impotriva tipului j.
Urmatoarele M linii vor contine 3 valori fiecare cuprinse intre 1 si N reprezentand cele 3 tipuri de pokemon ale acelui adversar.
Date de ieşire
În fişierul de ieşire pokemon3.out se va afla un singur numar reprezentand numarul minim de pokemoni pe care trebuie sa ii aduca Ash astfel incat sa castige campioanatul sigur sau -1 daca nu poate castiga campionatul din prima fara niciun risc.
Restricţii
- 1 ≤ N ≤ 20
- 1 ≤ M ≤ 10.000
Exemplu
| pokemon3.in | pokemon3.out |
|---|---|
| 3 2 0 1 0 0 0 1 1 0 0 3 1 1 2 2 3 | 3 |
Explicaţie
Ash va avea nevoie de un pokemon de fiecare tip pentru a castiga campionatul.
