Fişierul intrare/ieşire:magnet.in, magnet.outSursăAlgoritmiada 2016 - Runda 4 - Seniors
AutorAdrian BudauAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Magnet

Avem N obiecte punctiforme aflate la coordonate întregi pe axa Ox. Putem acţiona asupra acestor obiecte cu un magnet în felul următor: Magnetul va fi activat la o poziţie de coordonate întregi (care poate coincide sau nu cu poziţia unora din cele N obiecte) S, cu o anumită intensitate, număr natural, X. Obiectele aflate la stânga magnetului se vor muta în general cu X unităţi la dreapta, făcând excepţie doar cele care printr-o astfel de mutare ar trece de poziţia magnetului. Acestea se vor opri în schimb exact la poziţia magnetului. În mod analog, obiectele aflate la dreapta magnetului se vor deplasa cu X unităţi la stânga, dar niciunul din ele nu va depăşi poziţia magnetului. Dacă poziţia magnetului coincide deja cu poziţia unor obiecte, acestea vor rămâne pe loc.

Vi se dă un şir A de lungime N, reprezentând poziţiile de pe axa Ox în care există obiecte. Acest şir poate conţine duplicate. Vi se mai dă un şir B de lungime N, reprezentând poziţiile de pe axa Ox la care am dori să avem obiectele, după aplicarea succesivă a magnetului. Este posibil să mutăm obiectele la poziţiile respective? Dacă da, vi se cere un şir de maxim 10 * N operaţii care realizează acest lucru.

Date de intrare

Fişierul de intrare magnet.in va conţine pe prima sa linie numărul T, reprezentând numărul de teste.
Urmatoarele linii vor contine descrierea fiecarui test in parte, astfel pentru fiecare test pe prima linie se va citi N numarul de obiecte. Pe urmatoarea linie se vor afla N valori A1, A2, ...., AN reprezentand pozitiile initiale ale obiectelor, iar pe cel de-la treilea rand se vor afla alte N valori B1, B2, ..., BN reprezentand pozitiile la care ne dorim sa se afle obiectele dupa ce aplicam operatiile.

Date de ieşire

În fişierul de ieşire magnet.out trebuie sa contina T raspunsuri, reprezentand raspunsurile pentru fiecare test in parte. Astfel daca nu exista un sir de operatii pentru care sa se mute cele N obiecte de la pozitiile A1, A2, ...., AN la pozitiile B1, B2, ..., BN trebuie sa se gaseasca in fisierul de iesire -1. Daca exista un sir, trebuie afisat numarul de operatii K urmat de K linii. Pe fiecare din aceste K linii trebuie sa se gaseasca 2 numere S si X, acestea semnificand ca se activeaza magnetul la pozitia S cu intensitate X.

Restricţii

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 10.000
  • 0 ≤ Ai, Bi ≤ 1.000.000.000
  • Daca exista mai multe solutii se accepta oricare dintre acestea. Nu se cere numarul minim de operatii, doar ca acesta sa fie mai mic sau egal decat 10 * N.
  • Pentru orice operatie afisata trebuie ca 0 ≤ S, X ≤ 1.000.000.000
  • Pentru teste in valoare de 20% din punctaj N ≤ 15 si Ai, Bi ≤ 150
  • Pentru teste in valoare de 40% din punctaj N ≤ 550 si Ai, Bi ≤ 4500

Exemplu

magnet.inmagnet.out
2
2
5 7
9 6
4
4 2 4 10
5 7 5 5
-1
2
4 3
7 1

Explicaţie

Pentru primul test, orice operatie am face nu mai putem departa cele 2 obiecte, ele mereu for fi la distanta cel mult 2 unul de altul.
Pentru cel de-al doilea test dupa prima operatie obiectele se vor afla la pozitiile 4, 4, 4 si 7. Alt raspuns valabil ar fi fost:
2
10 1
5 3

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?