Cerința

După ce au vizitat toate obiectivele turistice din municipiul Iaşi, Ioana şi Maria au inventat un joc.

Ele au la dispoziţie un număr de n cutii aranjate în linie dreaptă, numerotate în ordine de la 1 la n, şi un număr de m bile ce pot fi aşezate în unele dintre aceste cutii. Unele cutii sunt deteriorate, astfel că bilele dispar dacă sunt puse în acele cutii.

O mutare constă în alegerea unei bile şi poziţionarea ei în una din cutiile învecinate (precedenta sau următoarea ). Bilele pot fi mutate după următoarea regulă: când o bilă a fost mutată pentru prima dată într-o anumită direcţie, atunci bila îşi păstrează direcţia de deplasare la următoarele mutări (de exemplu, dacă o bilă a fost mutată pentru prima dată spre stânga atunci orice mutări ulterioare ale acestei bile se pot face doar spre stânga).

Jocul se termină atunci când nici un jucător nu mai poate face nici o mutare. Pierde primul jucător care nu mai poate face nici o mutare. Fetele joacă un număr de T astfel de jocuri. Ştiind că Ioana este prima care face o mutare, iar apoi fetele mută alternativ, se cere să se stabilească pentru fiecare din cele T jocuri dacă ea are sau nu o strategie sigură de câştig.

Date de intrare

Fişierul .in conţine pe prima linie un număr natural T, care reprezintă numărul de jocuri pe care le joacă cele două fete.

Pe următoarele linii fişierul conţine, în ordine, descrierea celor T jocuri. Fiecare joc este descris prin câte 3 linii:

prima linie va conţine, în ordine, trei numere naturale n, k, m separate prin câte un singur spaţiu (n reprezintă numărul de cutii, k reprezintă numărul de cutii deteriorate şi m reprezintă numărul de bile)
a doua linie va conţine k numere naturale, separate prin câte un singur spaţiu, reprezentând numerele de ordine ale cutiilor deteriorate
a treia linie va conţine m numere naturale reprezentând numerele de ordine ale cutiilor care conţin bile la începutul jocului.

Date de ieșire

Fişierul .out va conţine pe prima linie un şir de T valori de 0 şi 1 neseparate prin spaţii, având următoarea semnificaţie: valoarea de pe poziţia i din şir (i={1,2,…,T}) este 1 daca jocul i este câştigat de Ioana sau 0 dacă jocul i este pierdut de Ioana.

Restricții și precizări

1 ≤ T ≤ 10
1 ≤ n ,m ≤ 10000
0 ≤ k ≤ 10000
se consideră că din prima nu poate fi mutată o bilă spre stânga, iar din ultima nu se poate muta o bila spre dreapta;
iniţial nici o bilă nu se află în prima , în ultima sau într-o deteriorată;
în fişierul de intrare poziţiile bilelor şi cele ale cutiilor deteriorate sunt sortate crescător;

Exemplu

cutie.in

cutie.out

Explicație

Pentru primul joc, Ioana are o strategie sigură de câştig (pentru a câştiga va muta bila la dreapta), iar pentru al doilea joc nu are o strategie sigură de câştig.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Cutie:

#include<fstream>

using namespace std;

int b[10005],c[10005];

int main()
{
    int t,i,nrp,nri,ok,soli,solip,solp,m,n,k,indb,indc;
    ifstream f("cutie.in");
    ofstream g("cutie.out");
    f>>t;
    for (;t;--t)
    {
        f>>n>>k>>m;
        for (i=1;i<=k;++i)
            f>>c[i];

        c[0]=1; c[k+1]=n;

        for (i=1;i<=m;i++)
            f>>b[i];

        solp=soli=solip=0;
        nrp=nri=0;

        indb=1;

        for (i=1;i<=k+1;i++)
        {
            nrp=nri=0;
            while (b[indb]<=c[i] && indb <=m)
            {
                if ((b[indb]-c[i-1])%2==0)
                    nrp++;
                else
                    nri++;
                indb++;
            }
            if ((c[i]-c[i-1]+1)%2==0)
                solip+=(nrp+nri);
            else
            {
                solp+=nrp;
                soli+=nri;
            }
        }
        if (solip%2==1) g<<1;
        else
            if ((solip%2==0) && (soli%2==1))
                g<<1;
            else
                g<<0;
    }
    g.close();
    f.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1765 Cutie

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1765 Cutie de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1765 Cutie