Fişierul intrare/ieşire:petrecere.in, petrecere.outSursăBaraj Tudor Vianu RMI 2015
AutorVictor ManzAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test0.3 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

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.inpetrecere.outExplicaţ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 sa te autentifici pentru a trimite solutii. Click aici