Intr-o gara se
afla n vagoane, numerotate de
la 1 la n.
Fiecare vagon i (1
<= i <= n) are în spate un brat metalic pe care se afla x[i]
gauri, iar în fata un brat metalic cu y[i]
suruburi. Astfel orice vagon i
contine:
- bratul din spate, care are prima gaura la distanta s[1]
de marginea din stânga, a doua la distanta s[2]
de prima gaura, a treia la distanta s[3]
de a doua gaura, si asa mai departe.
- bratul din fata, care are primul surub la distanta f[1]
de marginea din dreapta, al doilea la distanta f[2]
de primul surub, al treilea la distanta f[3]
de a doua gaura, si asa mai departe.
Gaurile si suruburile fiind de dimensiuni mult mai mici decât
vagoanele le vom considera punctiforme.
Spre exemplu un vagon cu trei gauri în spate, aflate la distantele 3,
5, 7
si cu doua suruburi, aflate la distantele 4,
6 arata astfel:
Un vagon poate
sa fie legat de un alt vagon numai daca toate suruburile bratului din fata ale
primului vagon pot fi introduse în gaurile bratului din spatele celui
de-al doilea vagon. Pot sa ramâna gauri nefolosite oriunde pe bratul din
spatele unui vagon. Bratul din spatele oricarui vagon este suficient de lung
ca sa poata intra orice surub de pe bratul din fata al oricarui vagon.
Toate vagoanele au aceeasi lungime, la fel si bratele metalice
sunt de aceasi forma si lungime.
Seful de gara doreste sa formeze un tren cu cât mai multe vagoane dintre
cele n de care dispune.
Cerinta
Sa se scrie un
program care sa determine lungimea (numarul de vagoane) celui mai lung tren
si câte astfel de trenuri se pot alcatui.
Date de intrare
Fisierul de intrare
vagoane.in are pe prima linie
numarul natural n, apoi pentru
fiecare vagon (în ordinea vagoanelor 1,
2, …, n)
se dau informatii pe cate doua linii. Prima linie contine numarul x[i],
urmat de x[i] numere s[1],
s[2], …, s[x[i]]
pentru bratul din spate separate prin câte un spatiu, apoi pe linia urmatoare
numarul y[i], urmat de y[i]
numere f[1], f[2],
…, f[y[i]] pentru bratul din
fata separate prin câte un spatiu.
Date de iesire
Fisierul de iesire
vagoane.out va contine pe prima
linie numerele cerute separate între ele printr-un spatiu (în ordinea:
lungimea trenului si apoi numarul de trenuri).
Restrictii
0 < n < 51
Numarul de gauri,
numarul de suruburi, distantele pentru gauri, distantele pentru suruburi sunt
numere naturale nenule <21.
Exemplu
vagoane.in
vagoane.out
4
3 1 2 3
2 2 3
2 6 7
1 8
3 1 1 3
1 3
2 2 1
2 3 3
4
8
prof.
Doru Popescu Anastasiu Colegiul Naţional "R. Greceanu" Slatina dopopan@yahoo.com
