Repoziționarea participanților în sală

Ce se cere de fapt pentru fiecare rând

Configurația finală a unui rând nu depinde de așezarea inițială, ci numai de câți participanți din fiecare echipă se află pe el. Locul din mijloc rămâne liber, cei cu −1 se strâng imediat la stânga lui, cei cu 1 imediat la dreapta lui, iar restul locurilor rămân libere.

Rândul are n locuri, cu n impar, deci locul din mijloc are numărul de ordine (n+1)/2. La stânga lui rămân (n−1)/2 locuri, iar la dreapta tot atâtea. Condiția din enunț — cel mult jumătate din locurile unui rând ocupate de participanți din aceeași echipă — asigură că fiecare echipă încape: pentru n = 7 sunt cel mult 3 participanți din aceeași echipă, iar de fiecare parte a mijlocului sunt exact 3 locuri.

Prin urmare, pentru fiecare rând sunt de ajuns două numere: câți au 1 pe bilet și câți au −1. Exact acestea sunt cele două valori pe care le furnizează subprogramul numarare.

Descrierea algoritmului în limbaj natural

Se citesc numărul de rânduri m, numărul de locuri n și cele m·n valori ale configurației inițiale, care se rețin într-un tablou bidimensional cu m linii și n coloane, cu indicii începând de la 1.

Se calculează o singură dată numărul de ordine al locului din mijloc, (n+1)/2.

Se parcurg rândurile, unul câte unul. Pentru rândul k se apelează subprogramul numarare, care parcurge cele n locuri și numără separat valorile 1 și valorile −1, furnizându-le prin parametrii nrP și nrM.

Rândul se rescrie apoi în trei pași: mai întâi toate locurile lui primesc valoarea 0, deci rândul devine gol; apoi se așază cei nrM participanți cu −1, pe locurile aflate imediat la stânga mijlocului, adică pe pozițiile mijloc−1, mijloc−2 și așa mai departe; în sfârșit, se așază cei nrP participanți cu 1, pe pozițiile mijloc+1, mijloc+2 și așa mai departe. Locul din mijloc nu este atins de niciunul dintre acești doi pași, deci rămâne cu valoarea 0.

Golirea rândului înaintea reașezării este esențială: fără ea, valorile din configurația inițială care nu sunt suprascrise de noua așezare ar rămâne pe loc și ar apărea în rezultat.

Rândurile se prelucrează independent unul de altul, în ordinea în care au fost citite. La sfârșit se afișează tabloul obținut, câte o linie pe câte o linie a ecranului.

Programul

#include <iostream>
using namespace std;

int s[51][51];
int m, n;

/* Numara, pe linia k a tabloului, cate valori sunt egale cu 1 si cate cu -1.
   Cele doua rezultate se furnizeaza prin parametri, deci nrP si nrM se
   transmit prin referinta. */
void numarare(int n, int s[51][51], int k, int &nrP, int &nrM) {
    nrP = 0;
    nrM = 0;

    for (int j = 1; j <= n; j++)
        if (s[k][j] == 1)
            nrP++;
        else if (s[k][j] == -1)
            nrM++;
}

int main() {
    cin >> m >> n;

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> s[i][j];

    int mij = (n + 1) / 2;   // locul din mijlocul unui rand, n fiind impar

    for (int k = 1; k <= m; k++) {
        int nrP, nrM;
        numarare(n, s, k, nrP, nrM);

        /* Randul se goleste, apoi se reasaza cele doua echipe. */
        for (int j = 1; j <= n; j++)
            s[k][j] = 0;

        for (int j = 1; j <= nrM; j++)
            s[k][mij - j] = -1;

        for (int j = 1; j <= nrP; j++)
            s[k][mij + j] = 1;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++)
            cout << s[i][j] << " ";
        cout << endl;
    }

    return 0;
}