Fişierul intrare/ieşire:popa.in, popa.outSursăBOI 2018
AutorChichirim GeorgeAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Popa

E haiduc, şi e vestit
Andrii Popa cel voinic
Zi şi noapte tot călare
Trage bir din drumul mare
Şi din ţară peste tot
Fug neferii cât ce pot
- "Andrii Popa", Phoenix

Ghiţă are o secvenţa S cu N numere întregi, indexată de la 0. Cum el e regele Carpaţilor, vrea să construiască un arbore binar al căror noduri au indicii 0, 1, ..., N-1 astfel încât:

  • Parcurgerea inordine (adică fiu stâng, apoi rădăcină, apoi fiu drept) a arborelui este 0, 1, ..., N-1.
  • Dacă nodul x este părintele nodului y, atunci Sx divide Sy.

Din nefericire, haiducul vestit Andrii Popa a furat secvenţa S, şi Ghiţă nu mai o poate accesa direct. Cu ajutorul tehnologiei avansate (telefonul lui mobil), el poate, pentru oricare doua subsecvenţe continue [a, b], [c, d] ale lui S, să determine dacă cmmdc(Sa, ..., Sb) = cmmdc(Sc, ..., Sd). Din nefericire, tehnologia e scumpă - daca Ghiță o foloseşte de mai mult de Q ori, va trebui să plătească mai mult. Ajutaţi-l să folosească tehnologia de cel mult Q ori pentru a construi arborele dorit.

Interacţiune

Problema aceasta este interactiva. Initial veti putea citi de la stdin numarul T de teste care va trebui sa le rezolvati. Fiecare test va avea urmatorul format: initial veti putea citi de la stdin pe N. Pentru a folosi tehnologia lui Ghiţă, afişaţi 0 urmat de 4 numere a b c d la stdout, toate urmate (inclusiv d) prin spaţiu alb, apoi daţi flush la stdout (de exemplu cu fflush(stdout) in C sau cu std::cout << std::flush în C++). Apoi citiţi răspunsul la interogarea voastră din stdin (1 indică ca cmmdc-urile coincid, 0 că nu).
Pentru a vă afişa răspunsul, afişaţi 1, urmat de răspuns, în formatul următor: mai întâi rădăcina arborelui, urmată de N numere, unde al i-lea număr reprezintă fiul stâng al lui i-1, sau -1 dacă i+1 nu are fiu stâng, apoi alte N numere, unde al i-lea număr reprezintă fiul drept al lui i-1, sau -1 daca i-1 nu are fiu drept, toate urmate prin spaţiu alb (inclusiv ultimul numar). Daţi apoi flush la stdout.

Restricţii şi precizări

  • Există mereu soluţie
  • Orice arbore ce respectă condiţiile va fi acceptat
  • Pentru 40 puncte, N = 100 şi Q = 10 000
  • Pentru 20 puncte, N = 1 000 şi Q = 20 000
  • Pentru 40 puncte, N = 1 000 şi Q = 2 000
  • Q nu este vizibil programului concurentului.

Exemplu

stdoutstdinExplicare
 1 6T si N
0 0 1 3 5 Interogare
 0Raspuns la interogare
0 4 5 1 3 Interogare
 1Raspuns la interogare
1
3
-1 0 -1 1 -1 -1
-1 2 -1 4 5 -1
 Raspuns final la problema

Explicaţie

Aici, S = [12, 4, 16, 2, 2, 20].

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?