Fişierul intrare/ieşire:interesant.in, interesant.outSursăOJI 2016, clasa a 10-a
AutorVlad NicuAdăugată devladrochianVlad Rochian vladrochian
Timp execuţie pe test1 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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 C0C1C2...Cn se defineşte ca o succesiune de caractere Ci1Ci2Ci3...Cik, unde 0 ≤ i1 < i2 < i3 < ... < ik ≤ 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

interesant.ininteresant.out
1 5
abcacaaz
ad
abcacaad
acd
zyt
abcacaad
2 5
abcacaad
ad
zayyt
acd
zyt
2
abcacaad
zayyt

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?