Lista de probleme 1991

Asupra unui număr se efectuează o serie de transformări (mutare cifre pe alte poziții). Să se afle numărul după mai multe asemenea serii de transformări.

Se dau înălțimile a n copii, numerotați de la 1 la n, exprimate prin numere naturale. Afișați numerele de ordine ale copiilor în ordinea crescătoare a înălțimii lor.

Se citește un număr natural n. Să se determine suma divizorilor săi.

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 .

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.

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.

La un concurs de robotică, în timpul prezentării, un roboţel cu corp cilindric cu diametrul de o unitate scapă de sub control şi se deplasează într-un ring de formă dreptunghiulară. Ringul este împărţit în N x M pătrate identice, cu latura de o unitate, aşezate pe N linii şi M coloane.

Robotul poate părăsi ringul numai pe la colţuri, acestea fiind numerotate de la 1 la 4, colţul cu numărul 1 fiind cel din stânga jos apoi restul fiind numerotate în sens trigonometric. Suprafaţa ringului este delimitată de exterior prin intermediul a patru pereţi despărţitori: doi pereţi “verticali” (aşezaţi de la colţul 1 la colţul 4, respectiv de la colţul 2 la colţul 3) şi doi pereţi “orizontali” (aşezaţi de la colţul 1 la colţul 2, respectiv de la colţul 3 la colţul 4), fără a bloca ieşirile, ca în desenul alăturat.

Se cere să se determine:

a) după câte secunde şi prin ce colţ al ringului va ieşi robotul;
b) de câte ori se ciocneşte robotul de pereţii orizontali şi verticali, rezultând o schimbare de direcţie, până la ieşirea din ring.

Să se determine un șir strict crescător, cu lungimea N, format din numere naturale nenule, \( 1 ≤ a_1 < a_2 < a_3 < … < a_N ≤ [2 \cdot N \cdot \sqrt{N}] \), cu proprietatea că oricare trei termeni distincți ai șirului nu sunt în progresie aritmetică, adică pentru oricare numere naturale i, j şi k cu 1 ≤ i < j < k ≤ N, este îndeplinită condiţia: \( a_i + a_j \neq 2 \cdot a_j \). Prin [x] s-a notat partea întreagă a lui x.

De exemplu, pentru N = 5, cel mai mare termen al șirului va trebui să fie mai mic sau egal cu \( [2 \cdot 5 \cdot \sqrt{5} ] \), adică aN ≤ 22, deci o soluție este: 1, 2, 4, 5, 10.

Fie un număr natural N. Spunem că (a, b, c) este un triplet geometric limitat de N, dacă a, b și c sunt trei numere naturale astfel încât 1 ≤ a < b < c ≤ N și \( b = \sqrt {a \cdot c} \).

Să se determine numărul tripletelor geometrice limitate de numărul natural N.

Se consideră N vectori cu elemente întregi, numerotați de la 1 la N, sortați crescător, fiecare vector având un număr precizat de elemente.

Să se răspundă la Q întrebări de tipul:
a) 1 i j, cu semnificaţia: care este minimul dintre modulele diferențelor oricăror două elemente, primul element aparținând vectorului numerotat cu i, iar cel de al doilea element aparținând vectorului numerotat cu j ?
b) 2 i j, cu semnificația: care este valoarea ce se găsește pe poziția mediană în vectorul obținut prin interclasarea vectorilor având numerele de ordine i,i+1,…,j (i<j).

Pe baza unei imagini preluate din satelit, se realizează harta unei mici localități. Localitatea ocupă o suprafață dreptunghiulară, cu laturile orientate pe direcțiile Nord-Sud, respectiv Est-Vest. Studiind imaginea obținută de la satelit, cartografii au constatat că toate cele k clădiri au forma unor dreptunghiuri distincte. Imaginea poate fi reprezentată sub forma unui tablou cu n•m celule așezate pe n linii numerotate de la 1 la n și m coloane numerotate de la 1 la m.

Numim drum, un dreptunghi al tabloului care străbate întreaga localitate pe direcția Est-Vest și are un număr maxim de linii sau un dreptunghi care străbate întreaga localitate pe direcția Nord-Sud și are un număr maxim de coloane. Drumurile, evident, nu trebuie să treacă prin clădiri.

Cartografii sunt interesați ca pe această hartă să fie reprezentate la scară doar clădirile, nu și drumurile. De aceea, pentru realizarea hărții, lățimile drumurilor au fost reduse la o singură celulă

Tabloul care reprezintă imaginea localității se codifică astfel: 1 pentru o celulă ocupată de o clădire și 0 pentru o celulă neocupată.

Cunoscând n, m și k, precum și tabloul care codifică imaginea, se cere să se determine:

1. Numărul S de celule ocupate de către clădirea pătratică cu latura maximă și numărul de clădiri C alese dintre celelalte k – 1 clădiri, cu proprietatea că fiecare dintre ele “încape” în interiorul clădirii pătratice cu latură maximă, fără să se suprapună peste celulele marginale ale acesteia.
2. Tabloul care reprezintă harta, în urma prelucrării imaginii inițiale.