Fișierul intrare/ieșire | petrecere.in, petrecere.out | Sursă | Baraj Tudor Vianu RMI 2015 |
---|---|---|---|
Autor | Victor Manz | Adăugată de | Spatarel Dan-Constantin • spatarel |
Timp de execuție pe test | 0.3 sec | Limită de memorie | 1024 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Petrecere
Peste o săptămână va fi ziua lui Andrei. Prin urmare e timpul ca acesta să își definitiveze lista cu invitați. În afara numelor acestora, Andrei se gândește la relațiile de prietenie dintre copii și își notează pe o foaie câți amici (dintre cei N invitați) are fiecare. Formează astfel un șir de numere naturale x1, x2, ..., xN. Fratelui său mai mare, Bogdan îi place să îl necăjească, și îi spune că șirul nu este corect. Andrei verifică, face unele modificări și îi cere din nou părerea fratelui său, dar răspunsul lui Bogdan e mereu același: ”Ai greșit!”.
După un timp Andrei își pierde răbdarea și se enervează (exact ceea ce își dorea Bogdan). Cum numărul N al viitorilor invitați e destul de mare, Andrei își dă seama că e destul de greu de verificat corectitudinea șirurilor, așa că vă roagă pe voi să scrieți un program care să îi rezolve problema.
Cerință
Scrieți un program care citește T șiruri a câte N numere naturale și răspunde pentru fiecare dintre ele prin 1 sau 0 dacă poate reprezenta șirul numerelor de prieteni. De exemplu, dacă N = 3, șirul 1 2 1 este corect (al doilea invitat e prieten cu primul și al treilea, iar aceștia nu sunt prieteni între ei), dar șirurile 1 2 2 și 2 0 2 nu sunt corecte.
Date de intrare
Fișierul de intrare petrecere.in va conține pe prima linie numerele T și N, reprezentând numărul de teste (șiruri pentru care trebuie făcută verificarea), respeectiv numărul de elemente al fiecăruia. Pe următoarele T linii vor fi câte N numere naturale. Al j-lea număr de pe linia i reprezintă numărul de prieteni ai invitatului j pentru cel de-al i-lea test.
Date de ieșire
Fișierul de ieșire petrecere.out va conține T linii. Pe fiecare dintre acestea se va afla câte un 1 (unu) sau 0 (zero), corespunzător răspunsului asociat celui de-al i-lea șir. Răspunsul va fi 1 dacă șirul e corect sau 0 în caz contrar.
Restricții
- 50 ≤ T ≤ 100
- 2 ≤ N ≤ 100 000
- Fiecare termen xj, al fiecărui șir i, va fi un număr natural cu cel mult 9 cifre.
- Suma termenilor fiecărui șir va respecta restricția x1 + x2 + ... + xN ≤ 3 * N
- Relațiile de prietenie sunt bidirecționale (dacă i este prieten cu j, atunci și j e prieten cu i).
Exemplu
petrecere.in | petrecere.out | Explicații |
---|---|---|
50 4 1 2 3 0 1 0 1 0 ... |
0 1 ... |
Pentru al doilea șir primul și al treilea invitat sunt prieteni. |
100 8 1 1 1 1 1 1 1 1 0 1 1 1 1 1 2 1 ... |
1 1 ... |
Pentru primul șir: primul invitat e prieten cu al doilea, al treilea cu al patrulea etc. Pentru al doilea șir: al doilea invitat e prieten cu al optulea, al șaptelea cu al șaselea și al cincilea, al treilea cu al patrulea. |
Explicație
Exemplele sunt incomplete (dar relevante). Acestea ar trebui să aibă 50 respectiv 100 de linii dar ar fi fost prea lungi.