| Fişierul intrare/ieşire: | password2.in, password2.out | Sursă | RMI 2018 |
| Autor | Costin Oncescu | Adăugată de |  Laura Georgescu •laurageorgescu |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/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
| stdout | stdin |
|---|---|
| | 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ă.
