Fişierul intrare/ieşire:	interesant.in, interesant.out	Sursă	OJI 2016, clasa a 10-a
Autor	Vlad Nicu	Adăugată de	Vlad Rochian •vladrochian
Timp execuţie pe test	0.5 sec	Limită de memorie	12288 kbytes
Scorul tău	N/A	Dificultate	1/5

Vezi solutiile trimise | Statistici

Interesant

Se consideră o mulţime S care conţine N şiruri de caractere formate din litere mici ale alfabetului englezesc.

Un şir de caractere se numeşte interesant în raport cu celelalte şiruri ale mulţimii dacă nu există un alt şir în mulţime care să-l conţină ca subşir. De exemplu, dacă mulţimea S conţine şirurile abc, bde şi abcdef, atunci singurul şir interesant este abcdef, deoarece abc şi bde nu îl conţin ca subşir. abc şi bde sunt subşiruri în abcdef, deci nu sunt interesante.

Cerinţă

Fiind dată o mulţime S formată din N şiruri de caractere, se cere:

1. Să se determine cel mai lung şir. Dacă sunt mai multe şiruri având aceeaşi lungime maximă, se cere cel mai mic din punct de vedere lexicografic.
2. Să se determine toate şirurile interesante din mulţimea S.

Date de intrare

Fişierul de intrare interesant.in conţine pe prima linie două numere naturale p şi N, despărţite prin spaţiu. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe următoarele N linii se găsesc şirurile de caractere, câte unul pe linie.

Date de ieşire

Dacă valoarea lui p este 1, se va rezolva numai cerinţa 1. În acest caz, în fişierul de ieşire interesant.out se va scrie cel mai lung şir dintre cele citite. Dacă există mai multe şiruri de aceeaşi lungime, se va scrie cel mai mic din punct de vedere lexicografic.

Dacă valoarea lui p este 2, se va rezolva numai cerinţa 2. În acest caz, fişierul de ieşire interesant.out va conţine pe prima linie o valoare K ce reprezintă numărul de şiruri interesante, iar pe următoarele K linii, şirurile interesante în ordinea în care apar în fişierul de intrare.

Restricţii

• 2 ≤ N ≤ 200
• Lungimea unui şir va fi cuprinsă între 1 şi 5000.
• Un subşir al şirului de caractere C₀C₁C₂...C_n se defineşte ca o succesiune de caractere C_i1C_i2C_i3...C_ik, unde 0 ≤ i₁ < i₂ < i₃ < ... < i_k ≤ n.
• Fişierul de intrare nu conţine şiruri identice.
• Pentru rezolvarea corectă a cerinţei 1 se acordă 20% din punctaj.
• Pentru rezolvarea corectă a cerinţei 2 se acordă 80% din punctaj.

Exemplu

Explicaţie

În primul exemplu, şirurile abcacaaz şi abcacaad au lungimea maximă, dar abcacaad este mai mic decât abcacaaz din punct de vedere lexicografic.

În al doilea exemplu, ad şi acd sunt subşiruri ale lui abcacaad, iar zyt este subşir al lui zayyt.

Cum se trimit solutii?