Fișierul intrare/ieșire transform.in, transform.out Sursă Concurs IQ Academy | Clasa a 10-a
Autor Teodor Plop Adăugată de avatar teodor94 Teodor Plop • teodor94
Timp de execuție pe test 0.05 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Transform (clasa a 10-a)

Avem o lume virtuală reprezentată printr-un spațiu de coordonate 2D. Avem N obiecte în acest spațiu, fiecare obiect având o poziție la care se află și opțional, un alt obiect considerat părinte.

Obiectele se pot muta în voie (își pot schimba poziția). În momentul în care un obiect părinte își schimbă poziția, această schimbare influențează toate pozițiile copiilor. De exemplu, dacă părintele se mută cu 5 coordonate către dreapta, atunci toți copiii acestuia se vor muta cu 5 coordonate către dreapta.

Cerință.

Avem starea inițială a spațiului:

  • Toate obiectele se află în originea spațiului, la coordonatele (0, 0) (putem avea mai multe obiecte în aceeași poziție).
  • Niciun obiect nu are părinte.

Asupra spațiului se vor aplica Q operații:

  • move(i,x,y): mutăm obiectul cu indicele i la poziția (x, y)
  • parent(i,j): setăm obiectul cu indicele i ca fiind părintele direct al obiectului cu indicele j
  • parent(0,j): obiectul cu indicele j nu mai are părinte
  • query(i): care este poziția obiectului cu indicele i?

Să se afișeze răspunsurile tuturor operațiilor de tip query, în ordine.

Date de intrare

Fișierul de intrare transform.in conține pe prima linie numerele naturale N și Q, având semnificația din enunț. Pe următoarele Q linii este descrisă câte o operație.

Date de ieșire

În fișierul de ieșire transform.out se vor găsi răspunsurile fiecărei operații de tip query sub forma (X,Y). Se va scrie câte un răspuns pe fiecare rând.

Restricții

  • 1 ≤ N ≤ 1.000
  • 1 ≤ Q ≤ 10.000
  • Pentru fiecare operație:
    • 1 ≤ i, j ≤ N
    • -1.000.000 ≤ x, y ≤ 1.000.000
  • Se garantează că i nu face parte din subarborele care îl are pe j ca rădăcină.
  • Cele mai multe operații sunt de tip query.

Exemplu

transform.in transform.out
5 9
move(1,1,5)
query(1)
move(1,2,3)
query(1)
query(5)
parent(1,5)
query(5)
move(1,3,0)
query(5)
 (1,5)
(2,3)
(0,0)
(0,0)
(1,-3)
3 11
parent(2,3)
parent(1,2)
move(1,5,5)
query(1)
query(2)
query(3)
parent(0,2)
move(1,10,10)
query(1)
query(2)
query(3)
 (5,5)
(5,5)
(5,5)
(10,10)
(5,5)
(5,5)
5 23
parent(1,2)
parent(2,3)
parent(1,4)
parent(4,5)
move(1,5,5)
query(1)
query(2)
query(3)
query(4)
query(5)
parent(2,4)
parent(0,2)
move(1,10,10)
query(1)
query(2)
query(3)
query(4)
query(5)
move(2,10,10)
query(2)
query(3)
query(4)
query(5)
 (5,5)
(5,5)
(5,5)
(5,5)
(5,5)
(10,10)
(5,5)
(5,5)
(5,5)
(5,5)
(10,10)
(10,10)
(10,10)
(10,10)

Explicație

În primul exemplu, avem 5 obiecte și 9 operații:

  • move(1,1,5) -> obiectul 1 ajunge la poziția (1, 5)
  • query(1) -> afișăm 1 5
  • query(5) -> obiectul 5 este încă la poziția (0, 0), deci afișăm 0 0
  • parent(1,5) -> obiectul 1 devine părintele obiectului 5
  • query(5) -> poziția obiectului 5 nu s-a schimbat încă, deci afișăm tot 0 0
  • move(1,3,0) -> obiectul 1 se mută la poziția (3, 0); această mutare influențează și obiectul 5, mutându-l la poziția (1, -3)
  • query(5) -> afișăm poziția obiectului 5 care tocmai a fost influențată de mutarea obiectului 1, adică afișăm (1, -3)

În cel de-al doilea exemplu:

  • În prima operație de tip [$move], mutarea obiectului 1 influențează pozițiile obiectelor 2 și 3$
  • În cea de-a doua operație de tip [$move], mutarea obiectului 1 nu mai influențează pozițiile obiectelor 2 și 3$

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii