Fişierul intrare/ieşire:	mixedsignals.in, mixedsignals.out	Sursă	Junior Challenge 2019
Autor	Bogdan Sitaru	Adăugată de	Junior Challenge 2019 •JuniorChallenge2019
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Mixed Signals

Sperând să descifreze semnalele mixte, Petrică a decis că vrea să înţeleagă o dată pentru totdeauna cum socializează oamenii, aşa că s-a înscris în Semicercul Dopaţilor Anonimi.

Aici el a găsit oameni aşezaţi într-un pătrat, numerotaţi de la 1 la N, identificând 3 tipuri de persoane:

• persoane care spun mereu adevărul, având încredere în restul grupului
• persoane care mint mereu, vorbind mereu fals
• persoane mute, care doar ascultă discuţiile

Fiind un semicerc de oameni sociabili, există cel mult oameni muţi, iar fiecare persoană ştie despre orice altă persoană ce tip de om este.

Dorind să se integreze în grup, protagonistul nostru s-a hotărât să afle ce tip de om e fiecare punând următoarele întrebări:

1. Petrică îl intreabă pe ce ar zice dacă ar fi întrebat ce ar zice dacă ar fi întrebat ce ar zice .... dacă ar fi întrebat ce zice despre , unde , cu , sunt persoane diferite din grup.
     De exemplu: pentru , Petrică îl întreabă pe dacă minte sau nu
     pentru , Petrică îl întreabă pe ce ar zice dacă e intrebat de dacă minte sau nu
     Dacă vreuna dintre persoanele este mută, atunci Petrică nu va primi niciun raspuns.
2. Petrică află prin intuiţia sa ce tip de om este (acesta nu îşi poate folosi intuiţia de mai mult de 5 ori într-o situaţie)

Interacţiune

Pentru fiecare test trebuie procesate mai multe situaţii.
Astfel, prima linie val conţine un număr natural , reprezentând numărul de situaţii.

Pentru fiecare situaţie, pe prima linie va fi un număr natural , reprezentând numărul de oameni.

Programul vostru are voie să pună întrebări scriind în standard output:

• "" reprezentând o întrebare de tipul 1
• "" reprezentând o întrebare de tipul 2
• "" reprezentând răspunsul

Pentru fiecare întrebare de tipul 1 sau 2, interactorul o să răspundă în standard input cu:

• "0" dacă zice că zice că ... spune mereu adevărul sau spune adevărul (în cazul unei întrebări de tipul 2)
• "1" dacă zice că zice că ... minte mereu sau minte (în cazul unei întrebări de tipul 2)
• "2" dacă printre este vreun mut sau este mut (în cazul unei întrebări de tipul 2).

Dacă după vreo întrebare răspunsul este , întrebarea este invalidă, iar programul trebuie să se termine imediat.

Pentru fiecare situaţie, operaţia "0" va fi apelată fix o singură dată.

Citirea şi afişarea se vor face cu standard input/output.
După fiecare operaţie trebuie afişat caracterul newline('\n' sau endl).
Încercarea de-a deschide vreun fişier poate duce la o eroare în executarea programului vostru.
Nu uitaţi să daţi flush la bufferul de ieşire, cu cout.flush() sau fflush(stdout).

Restricţii

• 1 ≤ T ≤ 20
• 5 ≤ N ≤ 300
• Vor exista mereu cel puţin 3 oameni care nu sunt muţi.
• Cel mult jumătate din oameni sunt muţi.
• Pentru o situaţie, întrebarea de tip 2 poate fi apelată de maxim 5 ori.

Punctare

Testele respectă următoarele:

Număr test	Limita N	Conţine persoane mute	Punctaj maxim
1	15	NU	10
2	100	NU	20
3	300	NU	30
4	20	DA	10
5	100	DA	10
6	300	DA	20

Pentru testele care nu conţin persoane mute, se punctează astfel, în funcţie de numărul de întrebări de tipul 1 şi de tipul 2 (notat cu Q):

• Q ≤ N, 100% din punctajul pe acel test
• N < Q ≤ N + 5, 80% din punctajul pe acel test
• N + 5 < Q ≤ 2 * N + 10, 60% din punctajul pe acel test
• 2 * N + 10 < Q, 20% din punctajul pe acel test

Pentru testele care conţin persoane mute, se punctează astfel, în funcţie de numărul de întrebări de tipul 1 şi de tipul 2 (notat cu Q):

• Q ≤ N + 15, 100% din punctajul pe acel test
• N + 15 < Q ≤ 2 * N + 10, 60% din punctajul pe acel test
• 2 * N + 10 < Q, 20% din punctajul pe acel test

Pentru folosirea unei întrebări de tipul 2 nu se acordă decât jumătate din punctajul testului.

Exemplu

standard input	standard output
1 4 2 1 0 0	‏‏‎ 1 2 1 2 1 2 1 3 2 1 2 4 0 0 2 1 0

Explicaţie

• Din prima întrebare, 1 sau 2 sunt muţi.
• Din a doua întrebare, 1 spune că 3 minte.
• Din a 3-a întrebare, 1 spune adevărul.
• Din a 4-a întrebare, 4 spune adevărul.

Se poate demonstra că singura soluţie validă este când:

• 1 spune adevărul
• 2 este mut
• 3 minte
• 4 spune adevărul
  
  Trebuie sa te autentifici pentru a trimite solutii. Click aici

  Cum se trimit solutii?