Fişierul intrare/ieşire:perrynator.in, perrynator.outSursăJunior Challenge 2021
AutorLuca Perju VerzottiAdăugată dejc2021Comisia jc2021
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Perrynator

O, nu! Agent P a căzut în capcana doctorului Doofenshmirtz! Acesta i-a dezvăluit planul său malefic, acela de a folosi ultima lui invenţie, Perrynatorul, pentru a eradica toţi ornitorincii de pe faţa Pământului. Dar Perry e mereu cu un pas înainte. Odată evadat (în stilul său bine-cunoscut), găseşte panoul de control al Perrynatorului. Spre mirarea lui, pentru a-şi salva specia, el trebuie să găsească o permutare secretă! Dându-i-se numărul N de elemente ale permutarii, el are la dispoziţie următoarea operaţie: întreabă, pentru un set de poziţii din permutare, care este minimul dintre valorile de pe acele poziţii. Dar Doofenshmirtz îi face viaţa un calvar! După fiecare query, elementele din afara setului întrebat se permută cu o poziţie la stânga sau la dreapta. Din păcate, P nu ştie să vă spună în care parte se rotesc, aşa că sunteţi pe cont propriu.

Interacţiune

Iniţial se citeşte din stdin numărul N.

Programul vostru are voie să pună query-uri scriind în standard output:

  • ? k p_1  p_2  ... p_k

După fiecare astfel de query interactorul vă va răspunde în stdin cu un număr din mulţimea  \{1, 2,.., N\} , reprezentând minimul valorilor de pe acele poziţii, la momentul queryului.

Când sunteţi siguri că aţi aflat permutarea, afişaţi un query de forma:

  • ! p_1  p_2  ... p_N

reprezentând permutarea la acel moment. Pe scurt, nu trebuie să aflaţi permutarea iniţială, ci doar cea de după queryuri.

După fiecare query, inclusiv cel final trebuie să afişaţi '\n' şi să daţi flush la standard output. Pentru a da flush vă puteţi folosi de următorul tabel:

LimbajC/C++PascalPythonJavaRust
Header necesarimport sysuse std::io::{self,Write};
Funcţiefflush(stdout) sau cout.flush()flush(output)sys.stdout.flush()System.out.flush()io::stdout().flush().unwrap();

Restricţii

  • 1 ≤ N ≤ 100
  • Pentru teste în valoare de 20 de puncte, shiftarea se face doar la dreapta.
  • Pentru alte teste în valoare de 20 de puncte, N ≤ 4.
  • Pentru cel mult 205 query-uri (fără cel final), punctajul pe test este de 100%
  • Pentru mai mult de 205 query-uri (fără cel final), punctajul pe test este de 50%
  • Pentru mai mult de 10000 query-uri (fără cel final), punctajul pe test este de 0%

Exemplu

stdinstdout
5

3

2

? 1 3

? 2 1 4

! 5 3 4 2 1

Explicaţie

Permutarea secretă era 1\;2\;3\;4\;5. După primul query, Perry primeşte numărul 3, semnificând chiar că pe poziţia 3 se află 3, iar permutarea putea deveni:

*2\;4\;3\;5\;1, adică permutare la stânga.
*5\;1\;3\;2\;4, adică permutare la dreapta.

deoarece poziţia 3 rămâne pe loc, iar celelalte se pot permuta la stânga sau la dreapta. Perrynatorul a ales să fie 5\;1\;3\;2\;4, adică la dreapta.

La fel, după al doilea query, Perry primeşte min(5,2) = 2, permutarea putând deveni:

*5\;4\;1\;2\;3, la dreapta.
*5\;3\;4\;2\;1, la stânga.

Perrynatorul a ales-o pe 5\;3\;4\;2\;1, adică la stânga, iar Perry pur şi simplu a ghicit-o şi şi-a salvat specia.
Reamintim că Perrynatorul nu este nici sub controlul nostru, noi îl ajutăm pe Perry, aşa că nici noi nu ştim în ce parte alege să permute.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?