| Fişierul intrare/ieşire: | xormites.in, xormites.out | Sursă | Algoritmiada 2017 Runda 2 |
| Autor | Andrei Popa, Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Xormites
Sunteti poate familiari cu urmatorul joc: dandu-se o secventa de N numere naturale, doi jucatori muta alternativ, o mutare constand in extragerea unei valori de la unul din capetele secventei (fie cel stang, fie cel drept). Valorea este stearsa din secventa, iar apoi este adunata la scorul total al jucatorului. Jocul se termina atunci cand secventa devine vida, iar castigator este declarat jucatorul cu suma mai mare.
Acest joc este de domeniul trecutului. Toti copiii cool joaca varianta "xor" a acestui joc. Mai exact, jocul decurge identic, dar scorul unui jucator este calculat ca suma xor a valorilor alese.
Dandu-se o secventa de N numere, trebuie sa decideti daca jocul ar fi castigat de primul jucator (definit prin faptul ca executa prima mutare), de al doilea jucator sau se va termina la egalitate. In acest scop, veti presupune ca cei doi jucatori actioneaza optim: daca un jucator are la dispozitie o strategie castigatoare, o va folosi.
Date de intrare
Fişierul de intrare xormites.in va contine pe prima sa linie valoarea T, numarul de teste din fisier. Urmeaza cele T teste, structura unui test fiind urmatoarea: pe prima linie se afla valoarea N, reprezentand numarul de valori din secventa. Urmeaza N numere naturale, reprezentand valorile secventei.
Date de ieşire
În fişierul de ieşire xormites.out se va afla un sir de T caractere, reprezentand rezultatele jocurilor descrise in fisierul de intrare. Al i-lea caracter al sirului va fi egal cu 2, daca jocul se termina la egalitate, cu 1 daca este castigat de primul jucator, respectiv cu 0, daca jocul este castigat de al doilea jucator.
Restricţii
- 1 ≤ T ≤ 12
- 1 ≤ N ≤ 100.000
- 0 ≤ V[i] ≤ 1.000.000.000
- Pentru teste in valoare de 20 de puncte 1 ≤ N ≤ 100 si 0 ≤ V[i] ≤ 150
- Pentru alte teste in valoare de 20 de puncte 1 ≤ N ≤ 1000
Exemplu
| xormites.in | xormites.out |
|---|---|
| 3 2 3 3 2 3 5 3 4 4 4 | 210 |
