| Fişierul intrare/ieşire: | movedel.in, movedel.out | Sursă | ONI 2016, clasa a 10-a |
| Autor | Adrian Budau, Eugen Nodea | Adăugată de |  Tatomir Alex •atatomir |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Movedel
Se consideră două şiruri de caractere A şi B, ambele şiruri având acelaşi număr de caractere.
Asupra şirurilor se aplică următorul algoritm:
- şirul A se permută circular cu k i poziţii spre stânga
- din cele două şiruri se elimină caracterele care coincid din punct de vedere al poziţiei şi valorilor
Algoritmul se opreşte când fie ambele şiruri devin vide, fie şirurile nu mai au caractere comune. Valoarea k i pentru fiecare pas i reprezintă al i-lea număr prim din mulţimea numerelor prime.
Cerinţă
Dându-se N şi M, să se genereze şirurile A şi B, ambele având lungimea N, astfel încât numărul de repetări ale algoritmului aplicat celor două şiruri să fie M.
Date de intrare
Fişierul de intrare movedel.in conţine pe prima linie valorile N şi M.
Date de ieşire
În fişierul de ieşire movedel.out se vor scrie şirurile de caractere A şi B de lungime N, fiecare pe câte un rând.
Restricţii
- Şirurile trebuie să conţină doar litere mici ale alfabetului englez.
- În cazul în care algoritmul efectuează cel puţin M repetări pentru şirurile afişate, se va obţine punctajul maxim pentru test. În caz contrar se vor obţine [X/M*10] puncte pe test, unde X este numărul de repetări ale algoritmului (prin [X/M] se înţelege partea întreagă a numărului X/M).
- Se garantează că există soluţie pentru datele de test:
| Testul | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| N | 23 | 23 | 50 | 100 | 50 | 100 | 500 | 1000 | 1550 | 2000 |
| M | 50 | 107 | 250 | 160 | 100 | 700 | 1500 | 8000 | 12000 | 16000 |
Exemplu
| movedel.in | movedel.out | Explicatie |
|---|---|---|
| 3 5 | abc cba | Prima aplicare a algoritmului: cab - după permutarea spre stânga cu 2 poziţii (2 - primul număr prim), după eliminarea caracterelor comune, cele două şiruri vor fi: ab ba A doua aplicare a algoritmului: ba - după permutarea spre stânga cu 3 poziţii (3 – al doilea număr prim), după eliminarea caracterelor comune, cele două şiruri devin vide, algoritmul încheindu-se. Astfel se obţin [2/5*10]=4 puncte pentru acest test |
| 5 5 | abcde edabc | Pentru şirurile găsite, algoritmul se încheie după 20 de etape. Astfel se obţin 10 puncte |
Trebuie sa te autentifici pentru a trimite solutii. Click aici
