Lista de probleme 3

#1121 p2048

Ada și Ben sunt pasionați de jocurile pe calculator și tocmai au descoperit cea mai recentă versiune a jocului 2048.

Scrieţi un program care să citească numerele naturale N (numărul inițial de piese) și M (numărul maxim de mutări), un șir de N numere reprezentând, în ordine, numerele înscrise pe cele N piese și cel mult M caractere din mulțimea {S, D} ce reprezintă mutările fixate de către Ada și Ben, și care determină:

a) numărul X de mutări efectuate până la încheierea jocului;
b) numărul maxim Y înscris pe una dintre piese la încheierea jocului;
c) numărul maxim Z de fuzionări efectuate la o mutare.

#1122 Babilon

Babilonienii au dezvoltat un sistem pozițional de scriere a numerelor, în care orice număr natural se poate reprezenta utilizând semnele (unu), (zece) şi spaţii.

Valorile k din {2, 3, … , 9} se obțin scriind semnul de k ori (scrierea babiloniană a lui 3 este ).

Numerele 11, 12, … , 59 se obțin ca succesiuni de semne urmate de semne (43 se reprezintă ca
).

Sistemul folosește gruparea unităților câte șaizeci. Astfel, pentru a scrie umărul șaizeci se folosește același semn ca pentru unu, dar valoarea sa este dată de poziția în care se găsește semnul !/resurse/9dc152/p-1100/babilon1.png!.

Babilonienii nu foloseau cifra 0. Pentru poziţionarea corectă a semnelor se utiliza spațiu (60 se reprezintă ca , 3600 se reprezintă ca etc.).

Se codifică scrierea babiloniană a unui număr utilizând cifra 1 în locul semnului , cifra 2 în locul semnului și cifra 3 în loc de spațiu.

Dându-se un număr natural n și un șir de n cifre din mulțimea {1, 2, 3}, reprezentând codificarea scrierii babiloniene a unui număr natural, să se determine:
a) numărul maxim de cifre 1 aflate pe poziții consecutive în codificarea scrierii babiloniene date;
b) numărul natural din sistemul zecimal corespunzător scrierii babiloniene date.

ONI GIM 2014, Clasa a V-a

Se construieşte un şir de numere naturale care respectă restricţiile:

  • primul număr din şir este 9;
  • numerele se generează în ordine strict crescătoare;
  • şirul conţine toate numerele formate doar cu cifrele 7, 8 şi 9 cu proprietatea că numărul cifrelor 9 este mai mare sau egal decât numărul cifrelor 8 şi numărul cifrelor 8 este mai mare sau egal decât numărul cifrelor 7.
    Primii 14 termeni ai şirului, în ordine, sunt: 9, 89, 98, 99, 789, 798, 879, 897, 899, 978, 987, 989, 998, 999.

Pornind de la aceste numere, Liv a inventat un joc interactiv: N iepuraşi sunt aşezaţi în şir, fiecare având câte un cartonaş. Fiecare cartonaş are două feţe, o faţă albă pe care este inscripţionat un număr din acest şir şi o faţă gri, pe care este inscripţionată poziţia acelui număr în şir, poziţii numerotate în ordine, începând cu valoarea 1.

Exemple. Cartonaşul care are pe faţa gri inscripţionat numărul 1 va avea pe faţa albă inscripţionat numărul 9, iar cartonaşul care are pe faţa gri inscripţionat numărul 5 va avea pe faţa albă inscripţionat numărul 789.

Iepuraşii sunt aşezaţi într-o ordine oarecare şi ţin cartonaşele astfel încât să se vadă faţa gri. Jocul constă în a rearanja iepuraşii de la stânga la dreapta, descrescător după numerele inscripţionate pe feţele gri, având la dispoziţie doar operaţia TAP pe un iepuraş. Când se aplică operaţia TAP unui iepuraş atunci secvenţa de iepuraşi, începând de la cel pe care s-a făcut TAP şi până la sfârşitul şirului (spre dreapta), este oglindită (ca în imaginea de mai sus). După oglindire, toţi iepuraşii din acea secvenţă ţin cartonaşele astfel încât să se vadă faţa albă. Se doreşte aplicarea unui număr cât mai mic de operaţii TAP pentru rearanjarea iepuraşilor.

Scrieţi un program care să citească numerele naturale N (reprezentând numărul de iepuraşi) şi a1, a2,…, aN (reprezentând, în ordine, numerele inscripţionate pe feţele gri) și care să determine:

a) Numărul minim de operaţii TAP necesare rearanjării iepuraşilor;
b) Cel mai mic număr aflat pe o faţă albă care nu se vede, în cazul în care au rămas cartonaşe neîntoarse. Dacă toate cartonaşele au fost întoarse (la toate fiind vizibilă faţa albă) se va afişa cel mai mare număr aflat pe o faţă albă a unui cartonaş.