Fişierul intrare/ieşire:movedel.in, movedel.outSursăONI 2016, clasa a 10-a
AutorAdrian Budau, Eugen NodeaAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test0.1 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/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:
Testul12345678910
N23235010050100500100015502000
M50107250160100700150080001200016000

Exemplu

movedel.inmovedel.outExplicatie
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

Cum se trimit solutii?