Fişierul intrare/ieşire:mixedsignals.in, mixedsignals.outSursăJunior Challenge 2019
AutorBogdan SitaruAdăugată deJuniorChallenge2019Junior Challenge 2019 JuniorChallenge2019
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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 N 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 {N/2} 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 X_1 ce ar zice X_2 dacă ar fi întrebat ce ar zice X_3 dacă ar fi întrebat ce ar zice X_4 .... dacă ar fi întrebat ce zice X_{K-1} despre X_K, unde X_1, X_2, ... X_K, cu K \ge 2, sunt persoane diferite din grup.
      De exemplu: pentru K=2, Petrică îl întreabă pe X_1 dacă X_2 minte sau nu
      pentru K=3, Petrică îl întreabă pe X_1 ce ar zice X_2 dacă e intrebat de X_3 dacă minte sau nu
      Dacă vreuna dintre persoanele X_1, X_2, ..., X_K este mută, atunci Petrică nu va primi niciun raspuns.
  2. Petrică află prin intuiţia sa ce tip de om este X (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 T, reprezentând numărul de situaţii.

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

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

  • "1 \: \: K \: X_1 \: X_2 \: ... \: X_K" reprezentând o întrebare de tipul 1
  • "2 \: \: X" reprezentând o întrebare de tipul 2
  • "0 \: \: T_1 \: T_2 \: ... \: T_N" reprezentând răspunsul

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

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

Dacă după vreo întrebare răspunsul este -1, î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 testLimita NConţine persoane mutePunctaj maxim
115NU10
2100NU20
3300NU30
420DA10
5100DA10
6300DA20

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 inputstandard 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: