6. Bašta sljezove boje - rešenje

Varijanta I: Upotrebom ugnježdenih petlji

Ovo rešenje je da se naprave dve for petlje, jedna da bude ugnježdena u drugoj. Spoljašnja simulira promenu deljenja, N puta.
Unutrašnja uzima tekući broj koji je u tom ciklusu i učitan i poredi sa prethodnim u okviru istog deljenja, tj. u prethodnom ciklusu ugnježdene petlje. U svakom novom ciklusu tekući broj postaje prethodnik za novi ciklus.
​Ako  se dobije da u nekom ciklusu tekući i prethodni broj nisu u neopadajućem poretku, konstatuje se da je tekuće deljenje "neispravno"  i brojač neispravnih deljenja se poveća za 1. Postupak se pomoću spoljašnje petlje ponavlja i za ostala "deljenja", tako da će na kraju vrednost brojača u stvari biti traženi broj neispravnih deljenja.
#include <iostream>

using namespace std;
/*
Primer 1
Ulaz
4
3
1
2
3
4
3
4
1
5
5
8
8
8
Izlaz
1
Učitani su podaci za 4 deljenja. Dobro je posloženo prvo, treće, četvrto deljenje.
Nije dobro posloženo drugo deljenje sa karticama 4,3,4.
*/

int main()
{
    int n, k, br = 0, b, p;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        bool dobro = true;
        for (int j = 0; j < k; j++)
        {
            cin >> b;
            if (j > 0 && b < p)
            {
                dobro = false; // Nije dobro deljenje
            }
            /* Prethodnik za sledeći ciklus postaje jednak broju u tekućem ciklusu –
               u SVAKOM ciklusu, a ne samo kada je pronađena greška */
            p = b;
        }
        /* Ako deljenje nije dobro, brojač se povećava za 1 */
        if (!dobro)
        {
            br++;
        }
    }
    cout << br << endl;

    return 0;
}

Varijanta II: Rešenje pomoću vektora.

Ovde koristimo vektore za pamćenje brojeva kartica u svakom deljenu. Uneti brojeve na karticama u vektor za svako deljenje. Deljenja se menjaju pomoću petlje. Treba napraviti kopiju vektora i sortirati(samo kopiju) po neopadajućem redosledu.
Zatim se ta kopija upoređuje sa originalnim vektorom.
Ako su original i kopija jednaki, to znači da je i originalni vektor bio u samom početku ispravno sortiran. Dakle, ako nisu jednaki reč je o "lošem" deljenju i brojač loših deljenja se povećava za 1.
Postupak se ponovlja i za ostala deljenja, tako da će na kraju vrednost brojača u stvari biti traženi broj neispravnih deljenja.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, k; // Broj deljenja i broj kartica u jednom deljenju
    cin >> N >> k;

    int brojGresaka = 0; // broj pogrešnih deljenja, u početku je jednak nuli

    for (int i = 0; i < N; ++i) {
        vector<int> kartice(k);
        for (int j = 0; j < k; ++j) {
            cin >> kartice[j];
        }

        vector<int> sortiraneKartice = kartice; // Kopija vektora kartice
        sort(sortiraneKartice.begin(), sortiraneKartice.end());

        if (kartice != sortiraneKartice) {
            ++brojGresaka;
        }
    }

    cout << brojGresaka << endl;

    return 0;
}

Rezime:

  1. Čitanje ulaza:
    • cin >> N >> k; učitava broj deljenja N i broj kartica u svakom deljenju k.
  2. Provera svakog deljenja:
    • vector<int> kartice(k); kreira vektor veličine k za čuvanje kartica.
    • cin >> kartice[j]; učitava kartice za trenutno deljenje.
    • vector<int> sortiraneKartice = kartice; pravi kopiju kartica koja će biti sortirana.
    • sort(sortiraneKartice.begin(), sortiraneKartice.end()); sortira kopiju kartica.
    • if (kartice != sortiraneKartice) { ++brojGresaka; } proverava da li su kartice u početnom nizu različite od sortiranih kartica. Ako jesu, povećava broj grešaka.
  3. Ispis rezultata:
    • cout << brojGresaka << endl; ispisuje ukupan broj deljenja u kojima kartice nisu bile pravilno poredane.
Ovaj program čita sve podatke, proverava svako deljenje i računa broj grešaka prema zadatim uslovima.