Fişierul intrare/ieşire:portale.in, portale.outSursăSummer Challenge 2021
AutorLuca Perju VerzottiAdăugată desummer21comisia summer 2k21 •summer21
Timp execuţie pe test2.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Portale

Într-un alt episod în care Rick şi Morty pleacă să salveze Atlantida, Citadela se află, din nou, în pericol datorită unui Portal Gun pierdut. Rezistenta Morty-lor, obţinând această armă, plănuieşte o revoluţie, creând un sistem de portale, sub forma unui arbore ascuns, între n locaţii principale (numerotate de la 1 la n).

Ştiind ca dimensiunea Citadelei este suprasolicitată, Militia Rick poate schimba forţat reţeaua de portaluri pentru a o determina. Astfel, aceasta poate introduce într-un Portal Gun coordonatele a două locaţii cheie (a,b) determinând una din două posibilităţi: arma returnează (0,0) semn că un portal deja există între a şi b ori returnează un dublet (x,y) semnalând că un nou portal se va deschide între a şi b, în timp ce, portalul dintre x şi y se va închide pentru a preveni apariţia unui ciclu, menţinând forma de arbore a reţelei.

Ajutaţi Miliţia Rick să găsească sistemul de portaluri pentru a preveni rănirea inutilă a Morty-lor.

Interacţiune

Iniţial se citeşte din stdin numărul T reprezentând numărul de teste.
Pentru fiecare test se citeşte, apoi, N numărul de noduri ale arborelui.

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

  • "? a b" reprezentând introducerea unui dublet în Portal Gun.

După fiecare astfel de query, interactorul va răspunde în stdin astfel:

  • "0 0": dacă muchia (a,b) există deja în arbore.
  • "x y": dacă muchia (a,b) nu există, dubletul (x,y) reprezintă muchia care se va şterge din graf odată cu adăugarea muchiei (a,b) pentru a păstra forma de arbore.

După ce aţi aflat muchiile arborelui, afişaţi "!" pe o singură linie urmat de n-1 linii cu "a b" semnificând că există o muchie între a şi b.

După fiecare query şi după ce afişaţi rezultatul unui test, 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};
Functiefflush(stdout) sau cout.flush()flush(output)sys.stdout.flush()System.out.flush()io::stdout().flush().unwrap();

Restricţii şi precizări

  • După apelarea query-ului, mai întâi se formează un ciclu, de unde, ulterior, este aleasă muchia care trebuie ştearsă excluzând-o pe cea mai recent adăugată
  • T = 30
  • 3 ≤ N ≤ 100

Punctare

În cadrul unui test:

  • Fie Q = numărul de query-uri efectuate;
  • Fie Opt = N(\lceil log_2{N} \rceil - 1) ;

Atunci, punctajul pe acel test va fi:

  • maxim, dacă Q $\leq$Opt;
  • 0, dacă N*N $\leq$Q;
  • 0.9*(\frac{N*N - Q}{N*N - Opt})^3*maxim, altfel;

În cadrul unui subtask, punctajul va fi egal cu punctajul minim dintre testele acestuia:

  • Subtask 1 : interactorul este random - 30 de puncte
  • Subtask 2 : interactorul este adaptiv - 70 de puncte

Exemplu

StdinStdoutExplicaţie
2
3		Aflăm numărul de teste si numărul de noduri din primul arbore
? 1 3Muchia 1 3 este adăugată
0 0Operaţia returnează că muchia 1 3 există deja in arbore
? 2 3
0 0Gun-ul returnează ca muchia 2 3 există deja in arbore
!
1 3
2 3		Urmeaza să afişăm muchiile primului arbore
3Se dă al doilea arbore
? 1 2Apelăm funcţia pentru muchia 1 2
1 3Aflăm ca muchia 1 3 a fost ştearsă ca să introducem muchia 1 2
!
1 2
2 3		Prin eliminare, ştim că muchia 2 3 se află în arbore
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?