Fișierul intrare/ieșire petrecere.in, petrecere.out Sursă Baraj Tudor Vianu RMI 2015
Autor Victor Manz Adăugată de avatar spatarel 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
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii