Fişierul intrare/ieşire:password2.in, password2.outSursăRMI 2018
AutorCostin OncescuAdăugată delaurageorgescuLaura Georgescu laurageorgescu
Timp execuţie pe test2.5 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Password2

Mi-am uitat parola din nou! Stau la calculator introducând nervos parole greşite. Tot ce îmi aduc aminte este că parola este formată doar din litere mici din alfabetul englez. Din fericire, sistemul de login răspunde cu mai mult decât "parolă greşită". Îmi spune de asemenea lungimea prefixului maximal din parola introdusă de mine care apare ca subşir (nu neaparat continuu) în parola corectă. Formal, pentru o parolă P = p1p2...pN şi şirul introdus Q = q1q2...qN, răspunsul sistemului de login este cel mai mare L pentru care există indicii 1 ≤ k1 < k2 < ... < kL ≤ N astfel încât qi = pki, pentru toţi 1 ≤ i ≤ L. Sistemul mi-l spune de asemenea pe N, lungimea parolei mele, şi S, însemnând că parola conţine doar primele S litere din alfabet. De exemplu, S = 4 înseamnă că parola mea conţine doar a, b, c şi d (nu neaparat toate).

Ajută-mă să îmi recuperez parola!

Interacţiune

Această problemă este interactivă.
Iniţial veţi putea citi de la stdin N, lungimea parolei, şi S.
Pentru a introduce un şir, afişaţi-l în stdout, urmat de '\n', iar apoi daţi flush la stdout (de exemplu cu fflush(stdout) în C sau cu std::cout << std::flush în C++).
Interactorul va răspunde în stdin cu L, lungimea prefixului maximal care se găseşte ca subşir în parola corectă.
Interacţiunea se termină când găsiţi parola corectă (L = N) sau după ce aţi pus a 50 000 - a întrebare.

Restricţiiţi

  • Puteţi introduce maxim 50 000 parole.
  • Pentru 10% din punctaj, N ≤ S ≤ 26 şi caracterele din parolă sunt distincte.
  • Pentru 20% din punctaj, 2 ≤ N ≤ 100, 2 ≤ S ≤ 4.
  • Pentru 20% din punctaj, 2 ≤ N ≤ 2 000, 2 ≤ S ≤ 20.
  • Pentru 30% din punctaj, 2 ≤ N ≤ 3 500.
  • Pentru 20% din punctaj, 2 ≤ N ≤ 5 000. 

Exemplu

stdoutstdin
 
3 2
ab
 
 
2
abb
 
 
2
bab
 
 
1
aab
 
 
3

Explicaţii

Parola corectă este aab. Interactorul dă N = 3 şi S = 2.
Pentru interogarea ab, L = 2 (aab).
Pentru interogarea abb, L = 2 (aab).
Pentru interogarea bab, L = 1 (aab).
Pentru interogarea aab, L = 3 (aab) şi interacţiunea se opreşte pentru că s-a găsit parola corectă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?