Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | portale.in, portale.out | Sursă | Summer Challenge 2021 |
| Autor | Luca Perju Verzotti | Adăugată de |  comisia summer 2k21 •summer21 |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Portale
Într-un alt episod in care Rick si Morty pleacă să salveze Atlantida, Citadela se află, din nou, in 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 si b ori returnează un dublet (x,y) semnalând că un nou portal se va deschide între a si b, în timp ce, portalul dintre x si 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 in Portal Gun.
Dupa fiecare astfel de query, interactorul va raspunde in stdin astfel:
- "0 0": daca muchia (a,b) există deja in arbore.
- "x y": daca 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 muchile arborelui, afişati "!" pe o singură linie urmat de n-1 linii cu "a b" semnificând ca exista o muchie intre a si b.
După fiecare query si dupa ce afisaţi rezultatul unui test, trebuie sa afişaţi '\n' şi să daţi flush la standard output. Pentru a da flush vă puteţi folosi de următorul tabel:
| Limbaj | C/C++ | Pascal | Python | Java | Rust |
|---|---|---|---|---|---|
| Header necesar | import sys | use std::io::{self,Write}; | |||
| Functie | fflush(stdout) sau cout.flush() | flush(output) | sys.stdout.flush() | System.out.flush() | io::stdout().flush().unwrap(); |
Restricţii si precizări
- După apelarea query-ului, mai intai se formează un ciclu, de unde, ulterior, este aleasă muchia care trebuie ştearsă excluzând-o pe cea mai recent adaugata
- T=30
- 3 ≤ N ≤ 100
Punctare
- Subtask 1 : interactorul este random - 30 de puncte
- Subtask 2 : interactorul este adaptiv - 70 de puncte
In cadrul unui test:
- Fie Q = numarul de query-uri efectuate;
- Fie Opt =
;
Atunci, punctajul pe acel test va fi:
- maxim, daca Q <= Opt;
- 0, daca N*N < Q
* punctajul care ar fi fost acordat acestui test
Exemplu
| Stdin | Stdout | Explicatie |
|---|---|---|
| 2 3 | Se rezolvă primul arbore | |
| ? 1 3 | Apelăm funcţia pentru muchia 1 3 | |
| 0 0 | Aflăm ca muchia 1 3 există deja in arbore | |
| ? 2 3 | ||
| 0 0 | ||
| ! 1 3 2 3 | Afişăm muchiile primului arbore | |
| 3 | Se dă al doilea arbore | |
| ? 1 2 | Apelăm funcţia pentru muchia 1 2 | |
| 1 3 | Aflăm ca muchia 1 3 a fost ştearsă ca să introducem muchia 1 2 | |
| ! 1 2 2 3 | Prin eliminare, ştim ca muchia 2 3 se află in arbore |
