Fişierul intrare/ieşire:xormites.in, xormites.outSursăAlgoritmiada 2017 Runda 2
AutorAndrei Popa, Mihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inxormites.out
3
2
3 3
2
3 5
3
4 4 4
210
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?