Olimpiada nationala de informatica - clasa a X-a

Problema 1 - cutie     100 puncte

Dupa ce au vizitat toate obiectivele turistice din municipiul Iasi, Ioana si Maria au inventat un joc. Ele au la dispozitie un numar de n cutii aranjate in linie dreapta, numerotate in ordine de la 1 la n, si un numar de m bile ce pot fi asezate in unele dintre aceste cutii. Unele cutii sunt deteriorate, astfel ca bilele dispar daca sunt puse in acele cutii. O mutare consta in alegerea unei bile si pozitionarea ei in una din cutiile invecinate (precedenta sau urmatoarea cutie). Bilele pot fi mutate dupa urmatoarea regula: cand o bila a fost mutata pentru prima data intr-o anumita directie, atunci bila isi pastreaza directia de deplasare la urmatoarele mutari (de exemplu, daca o bila a fost mutata pentru prima data spre stanga atunci orice mutari ulterioare ale acestei bile se pot face doar spre stanga). Jocul se termina atunci cand nici un jucator nu mai poate face nici o mutare. Pierde primul jucator care nu mai poate face nici o mutare. Fetele joaca un numar de T astfel de jocuri. Stiind ca Ioana este prima care face o mutare, iar apoi fetele muta alternativ, se cere sa se stabileasca pentru fiecare din cele T jocuri daca ea are sau nu o strategie sigura de castig. 

Date de intrare

Fisierul cutie.in contine pe prima linie un numar natural T, care reprezinta numarul de jocuri pe care le joaca cele doua fete. Pe urmatoarele linii fisierul contine, in ordine, descrierea celor T jocuri. Fiecare joc este descris prin cate 3 linii: prima linie va contine, in ordine, trei numere naturale n, k, m separate prin cate un singur spatiu (n reprezinta numarul de cutii, k reprezinta numarul de cutii deteriorate si m reprezinta numarul de bile), a doua linie va contine k numere naturale, separate prin cate un singur spatiu, reprezentand numerele de ordine ale cutiilor deteriorate, iar a treia linie va contine m numere naturale reprezentand numerele de ordine ale cutiilor care contin bile la inceputul jocului.

Date de iesire

Fisierul cutie.out va contine pe prima linie un sir de T valori de 0 si 1 neseparate prin spatii, avand urmatoarea semnificatie: valoarea de pe pozitia i din sir (i I este 1 daca jocul i este castigat de Ioana sau 0 daca jocul i este pierdut de Ioana.  

Restrictii si precizari

T

n ,m

k

se considera ca din prima cutie nu poate fi mutata o bila spre stanga, iar din ultima cutie nu se poate muta o bila spre dreapta

initial nici o bila nu se afla in prima cutie, in ultima cutie sau intr-o cutie deteriorata;

in fisierul de intrare pozitiile bilelor si cele ale cutiilor deteriorate sunt sortate crescator;

intr-o cutie se pot afla mai multe bile;

pentru 20% dintre teste k are valoarea 0 sau 1.

Exemplu

Timp maxim de executare/test secunde

Limite de memorie: total memorie disponibila 4MB, din care pentru stiva maxim 4MB

Dimensiunea maxima a sursei 10KB