Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | transform3.in, transform3.out | Sursă | Summer Challenge 2021 |
| Autor | Alexandru Luchianov | Adăugată de |  comisia summer 2k21 •summer21 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Transform3
După ce a văzut cât de impresionaţi au fost toţi atunci când s-a transformat în murătură, Rick s-a hotărât să creeze un device că să se poată transforma în mai multe obiecte, legume sau specii de extratereştrii cât mai diverse.
Totuşi, el are anumite restricţii în ceea ce priveşte felul în care poate construi device-ul. Mai exact, el cunoaşte un număr N şi Q intervale: l[i] r[i], 1 ≤ i ≤ Q care au proprietatea că l[i] ≤ l[i + 1] şi r[i] ≤ r[i + 1] pentru orice i < Q. Acestea intervin in felul următor:
Când programează device-ul, el trebuie să îi dea cel mult 4 * N + 2 * Q instrucţiuni de forma "x y" (fără ghilimele), însemnând că dacă el la un moment dat este obiectul, leguma, specia cu numărul x, se poate transforma în cea cu numărul y. Transformarea este una unidirecţionala, adică din starea y nu se poate "reîntoarce" direct în x decât dacă există şi instrucţiunea "y x".
Rick va consideră că device-ul este bine făcut dacă există o modalitate să ajungă din starea cu numărul x (1 ≤ x ≤ N) în cea cu numărul y (N + 1 ≤ y ≤ N + Q) dacă şi numai dacă l[y – N] ≤ x ≤ r[y – N]
Date de intrare
Prima linie a fişierului de intrare transform.in contine numerele N şi Q. Pe următoarele Q linii apar câte două numere, pe linia i apărând l[i] si r[i].
Date de ieşire
Pe prima linie a fişierului transform.out se va afişa numarul de instructiuni pe care Rick le va programa in device-ul lui, fie M numarul lor. Apoi, pe fiecare dintre urmatoarele M linii se vor afisa cate doua numere x si y, insemnand ca din starea cu numarul x se poate trece in cea cu numarul y.
Restricţii
- 0 ≤ N ≤ 106
- 1 ≤ l[i] ≤ r[i] ≤ N
- Rick nu este obligat sa foloseasca la programarea device-ului sau doar stari cuprinse intre 1 si N + Q, el se poate folosi de stari intermediare oricat de diverse, atata vreme cat in final este respectata conditia din enunt$
- Pentru teste in valoare $
- Pentru alte teste in valoare de$
- Pentru alte teste in valoare de$
- Pentru alte teste in valoare de nu există restricţii suplimentare
Exemplu
| transform3.in | transform3.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
