Fişierul intrare/ieşire:jocs.in, jocs.outSursăLot Sibiu 2011
AutorAndrei ParvuAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test1.8 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Jocs

Gauss şi Seidel, plictisiţi de activităţile lor cotidiene, s-au apucat de un nou joc. Fiind dat un şir de N caractere şi un număr K, trebuie găsită o subsecvenţă [i, j] a acestuia (adică o submulţime de elemente aflate pe poziţii consecutive) de lungime minimă K, astfel încât numărul de apariţii a subsecvenţei [i, j] în şirul dat plus j – i + 1 să fie maxim.

Cerinta

Fiind dat un şir de N caractere şi un număr natural K, găsiţi pentru acest şir o subsecvenţă cuprinsă între poziţiile [i, j] care maximizează numărul de apariţii a acestei subsecvenţe în şir plus lungimea acesteia, adică j – i + 1.

Date de intrare

Fişierul de intrare jocs.in conţine pe prima linie un număr natural T reprezentând numărul cazurilor de test. Un test este descris prin două linii. Prima linie conţine numerele N şi K cu semnificaţia de mai sus. Pe a doua linie se află N caractere, reprezentând şirul dat.

Date de ieşire

Fisierul de ieşire jocs.out va conţine 2 * T linii, reprezentând răspunsurile pentru cele T teste. Un răspuns se scrie pe două linii: pe prima linie se va scrie numărul de apariţii al subsecvenţei găsite plus lungimea sa, iar pe a doua linie numerele i şi j (i ≤ j) reprezentând capetele subsecvenţei.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ K ≤ N
  • 1 ≤ T ≤ 5
  • pentru ca un răspuns sa fie considerat corect, subsecvenţa afişată trebuie sa apară în şirul iniţial de cel puţin 2 ori
  • se garantează că pentru fiecare K dat există o soluţie
  • în cazul în care există mai multe răspunsuri corecte, puteţi să afişaţi oricare dintre acestea

Exemplu

jocs.injocs.out
2
18 1
atasarapavamefgefg
18 2
atasarapavamefgefg
7
1 1
5
13 15

Explicaţie

Pentru primul caz, litera “a” apare de 6 ori in sir, raspunsul fiind 6 + 1 = 7
Pentru al doilea caz, sirul “efg” apare de 2 ori, raspunsul fiind 2 + 3 = 5

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content