Unul dintre participanții la concursul Bursele Agora avea, la un moment dat, N scânduri de lungimi a1, a2, ..., aN. Mânat de porniri distructive, datorită faptului că nu a reușit să rezolve toate problemele de la primele două runde, el a luat un topor și a tăiat fiecare scândură în două bucăți. Astfel a obținut 2N bucăți de lungimi b1, b2, ..., b2N.
Câteva zile mai târziu, participantului i-a părut rău că a stricat scândurile și a dorit să reconstituie scândurile inițiale. Din nefericire, bucățile s-au amestecat, deci el nu a mai știut cum să le lipească. Sarcina voastră este de a scrie un program care determină perechile de bucăți care trebuie lipite pentru a reconstitui scândurile inițiale.
Prima linie a fișierului de intrare conține numărul N care reprezintă numărul scândurilor inițiale. Pe următoarele N linii se află N numere întregi, reprezentând lungimile celor N scânduri inițiale. Pe următoarele 2N linii se află 2N numere întregi care reprezintă cele 2N lungimi ale bucăților obținute după tăiere.
Pe prima linie a fișierului de ieșire se află numărul K al scândurilor reconstituite. Pe următoarele K linii se află câte trei numere întregi S, X și Y (S = X + Y) cu semnificația: o scândură de lungime S este reconstituită din două bucăți de lungime X și Y.
Numerele S reprezintă lungimi ale scândurilor inițiale. Dacă o valoare S apare la începutul unor linii din fișierul de ieșire de x ori, atunci trebuie să existe cel puțin x scânduri de lungime S. Numerele X și Y reprezintă lungimi ale bucăților obținute după tăiere. Dacă o valoare X apare ca al doilea sau al treilea număr pe o linie a fișierului de ieșire de y ori, atunci trebuie să existe cel puțin y bucăți obținute după tăiere care au lungimea X.
PLANKS.IN 6 10 15 20 25 30 35 5 5 5 10 10 10 10 15 15 15 15 20 PLANKS.OUT 6 15 10 5 20 10 10 25 10 15 30 15 15 35 20 15 10 5 5
|