Etichetele scaunelor dintr-o sală de spectacole

Cele două etichete ale unui scaun

Fie scaunul al j-lea de pe rândul i. Enunțul spune că cifrele rândului se alipesc numărului de ordine al scaunului, la stânga sau la dreapta. Rezultă exact două etichete:

• alipite la dreapta lui j: numărul obținut este j urmat de cifrele lui i, adică valoarea întoarsă de apelul eticheta(j, i, x);
• alipite la stânga lui j: numărul obținut este i urmat de cifrele lui j, adică valoarea întoarsă de apelul eticheta(i, j, y).

Pentru scaunul 123 de pe rândul 45, primul apel dă 12345, iar al doilea 45123, adică cele două etichete din enunț. Elementul tabloului este cea mai mică dintre ele.

Subprogramul cerut face o singură operație: alipește la dreapta lui s cifrele lui d. Alipirea a k cifre înseamnă deplasarea lui s cu k poziții spre stânga, adică înmulțirea lui cu 10 de k ori, urmată de adunarea lui d. Numărul de cifre ale lui d se află împărțindu-l repetat la 10 până devine 0.

Parametrul n este parametru de ieșire, adică prin el subprogramul furnizează rezultatul, deci se transmite prin referință (int &n în C++, var n: integer în Pascal), nu prin valoare.

Descrierea algoritmului în limbaj natural

Se citesc de la tastatură numerele m și n, reprezentând numărul de rânduri, respectiv numărul de scaune de pe fiecare rând.

Pentru fiecare poziție (i, j) a tabloului, cu i luând valori de la 1 la m și j de la 1 la n, se determină cele două etichete care se pot genera pentru scaunul al j-lea de pe rândul i. Prima se obține apelând subprogramul eticheta cu numărul scaunului ca prim parametru și numărul rândului ca al doilea, iar a doua apelându-l cu parametrii în ordine inversă. Elementul tabloului de pe linia i și coloana j primește valoarea mai mică dintre cele două.

Subprogramul eticheta alipește la dreapta primului număr primit cifrele celui de-al doilea: numără cifrele lui d, calculând în același timp puterea lui 10 corespunzătoare, înmulțește s cu această putere și adună d. Rezultatul se transmite în afara subprogramului prin parametrul de ieșire.

După construirea completă a tabloului în memorie, acesta se scrie în fișierul text def2025.txt: se parcurg liniile de la 1 la m și, pentru fiecare linie, elementele de la 1 la n, care se scriu despărțite prin câte un spațiu; după ultimul element al unei linii se trece la linia următoare a fișierului. La sfârșit fișierul se închide.

Programul

#include <iostream>
#include <fstream>
using namespace std;

ofstream g("def2025.txt");

int a[101][101];

/* Alipeste la dreapta lui s cifrele lui d, in ordinea in care apar in
   acesta: pentru s=123 si d=75 rezulta n=12375. Deplasarea lui s spre
   stanga se face inmultind cu 10 de atatea ori cate cifre are d.

   Rezultatul se furnizeaza prin parametrul n, transmis prin referinta:
   asa cere enuntul, care spune ca prin n subprogramul „furnizeaza" un
   numar, nu ca il primeste. */
void eticheta(int s, int d, int &n) {
    int p = 1, t = d;
    while (t != 0) {
        p = p * 10;
        t = t / 10;
    }
    n = s * p + d;
}

int main() {
    int m, n, i, j, x, y;

    cin >> m >> n;

    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++) {
            eticheta(j, i, x);   /* cifrele randului alipite la dreapta */
            eticheta(i, j, y);   /* cifrele randului alipite la stanga  */
            if (x < y)
                a[i][j] = x;
            else
                a[i][j] = y;
        }

    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (j > 1)
                g << " ";
            g << a[i][j];
        }
        g << "\n";
    }

    g.close();
    return 0;
}