Fişierul intrare/ieşire:ausoara.in, ausoara.outSursăONI 2013 Clasele 11-12
AutorAndrei Parvu, Marius Stroe, Mugurel Ionut AndreicaAdăugată decrushackPopescu Silviu crushack
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ausoara

Dorind să se angajeze, Arius M. a fost nevoit să dea un interviu în care a primit următoarea problemă simplă: dându-se N şiruri crescătoare de numere întregi, să se determine cel mai lung subşir comun al acestora.

Cerinta

Rezolvaţi această problemă pe care Arius M. a considerat-o destul de uşoară.

Date de intrare

Pe prima linie a fişierului ausoara.in se află N, numărul şirurilor. Următoarele N linii descriu cele N şiruri. Linia i este formată din M i, numărul elementelor şirului curent, urmat de M i numere, reprezentând elementele şirului i.

Date de ieşire

Fişierul de ieşire ausoara.out va conţine pe prima linie T, numărul elementelor celui mai lung subşir comun al celor N şiruri. Urmează T numere întregi ce descriu elementele subşirului comun de lungime maximă.

Restricţii

  • 1N100
  • 1M1000
  • Dacă avem un şir de numere a 1, a 2, …, a n atunci numim subşir un şir de forma a i1, a i2, …, a ik cu i1, i2, …, ik aparţinând mulţimii {1, 2, …, n} şi i1 < i2 < ... < ik.
  • Elementele şirurilor sunt numere întregi în intervalul [1, 1 000 000].
  • Elementele fiecărui şir sunt date în ordine crescătoare.
  • Pentru 60% din teste, elementele fiecărui şir sunt distincte.
  • Pentru 90% din teste, elementele şirurilor sunt în intervalul [1, 10 000].

Exemplu

ausoara.inausoara.out
1
3 1 2 3
3 1 2 3
2
2 1 2
2 2 3
1 2
3
6 1 2 2 3 5 5
9 2 2 2 2 2 5 5 5 7
9 2 2 2 4 5 7 7 7 7
3 2 2 5
3
3 1 2 3
3 4 5 6
3 7 8 9
0
3
3 1 1 1
1 1
2 1 1
1 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content