Choose jour language!

---

|

28. Seča drva - rešenje

Na sledećoj slici je prikazana traka sa drvima,  u skladu sa primerom 1, sa 4 komada drveta i pozicijama testere P0,P1,P2 i P3 koja seče po jednos horizontalnoj liniji sve komade. Zamislimo da su svi komadi podeljeni na kockice tako da broj kockica za svaki komad iznosi kxk, a gde je k-najveća dimenzija komada. Ako bi od tih jediničnih kockica kao sa lego kockicama sastavili svaki deo, to bo izgledalo kao na slici 1:

Slika 1: Prikaz svih komada od drveta na traci, sastavljenog od kockica za primer 1

Ovo su samo zamišljene kocke. Posmatrajmo ulazne podatke za primer 1:
4
4
​1 1 0 0
1 1 0 0
1 1 0 0
1 1 0 0
0 0 1 0
1 1 1 0
1 1 1 0
1 1 1 0
0 1 0 0
1 1 0 0
1 1 0 0
0 0 0 0
0 0 0 0
1 1 1 0
1 0 1 0
0 0 0 0

Prvi broj n=4, predstavlja broj komada na traci, koji je u ovom primeru jednak 4. Drugi broj k=4, predstavlja maksimalnu dimenziju matrice, koja pokazuje da li u prostoru u kome se mora nalaziti jedan deo, koji je u ovom slučaju prostor od 16 kockica rasporećenih u 4 reda i 4 kolone. Delovi neće popuniti uvek ovaj prostor u potpunosti i brojevi u matrici 4x4, 0 ili 1, govore da li je odrećena kockica ispunjena materijalom ili nije(1-da, 0 ne). Npr. možemo uočiti da je prvi deo ispunio dve kolone, a dve su prazne(beli kvadratići). To govori matrica:
​1 1 0 0
1 1 0 0
1 1 0 0
1 1 0 0
Na ovaj način moglo bi se, npr. izmeriti broj kockica iznad i ispod položaja testere(horizontalne linij) i tako prebrojati količina materijala ispod i iznad i odrediti razlika.

Neoptimizovan algoritam

Zadatak bi se mogao rešiti kako je prethodno opisano, prolaskom kroz petlju for npr. u kojoj se menjaju kolone i onda u svakom ciklusu prebrojati koliko ima kockica sa materijalom(vrednost 1 u matrici), iznad, a koliko ispod i naći razliku istih. Pri tome, u skladu sa algoritmom o traženju minimalne vrednosti za, u ovom primeru razliku broja komada iznad i ispod, treba posle svakog ciklusa ispitati da li je nova razlika manja od one iz prethodnog ciklusa i ako jeste ažurirati minimalnu razliku. U svakom ciklusu, tj. za svaku kolonu, prebrojavanje se vrši upotrebom unutrašnje ugnježdene petlje. Ovo se može uraditi na sledeći način:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> brojDrvaPoRedu(k, 0); // Broj drva u svakom redu kroz sve delove
    int ukKom = 0;

    for (int i = 0; i < n; i++) { // Svaki deo
        for (int j = 0; j < k; j++) { // Svaki red u delu
            for (int l = 0; l < k; l++) { // Svaka kolona u redu
                int x;
                cin >> x;
                if (x == 1) {
                    brojDrvaPoRedu[j]++; // Dodaj drvo u odgovarajući red
                    ukKom++;
                }
            }
        }
    }

    // Sada možemo da pronađemo optimalnu poziciju za testeru
    int dole = 0;
    int gore = ukKom;
    int minRazKD = abs(gore - dole);

    for (int i = 0; i < k; i++) { // Pomera poziciju testere kroz redove
        dole += brojDrvaPoRedu[i];
        gore = ukKom - dole;
        int razlika = abs(gore - dole);
        if (razlika < minRazKD) {
            minRazKD = razlika;
        }
    }

    cout << minRazKD << endl;
    return 0;
}

1. Ulaz i inicijalizacija:
   
   • Program na početku čita brojeve n i k koji predstavljaju broj komada drva i veličinu svakog komada (dimenzije matrice).
   • Kreiramo vektor matrica, koji će sadržati nizove podataka o svakom redu svakog dela drva, i promenljive za računanje ukupnog broja komada drva (ukKom) i broj redova za svaki deo (nRMax).
2. Učitavanje drva i računanje broja komada:
   
   • Program koristi petlju za unos nRMax redova. U svakoj iteraciji unosi red podataka red za jedan komad drva, računa broj jedinica u tom redu i proverava prisustvo drva.
   • U prvih k redova popunjava vektor matrica, dok za ostale redove dodaje redove na odgovarajuću poziciju u matrica, što omogućava čuvanje podataka u pravilnim delovima.
3. Postavljanje testere i računanje razlike:
   
   • Program prvo računa ukupnu količinu drva (ukKom) koja predstavlja ukupan broj jedinica u matrici.
   • Postavlja testeru tako da podeli ukupno drvo na levu (dole) i desnu stranu (gore).
   • Koristi petlju koja pomera testeru po redovima, ažurira broj jedinica na levoj i desnoj strani i računa apsolutnu razliku između te dve vrednosti.
4. Pronalazak optimalne pozicije testere:
   
   • Svakom pozicijom, program računa trenutnu razliku između levo i desno prikupljenog drva (r), a najmanja vrednost te razlike (minRazKD) predstavlja optimalno rešenje.

Na kraju, rezultat minRazKD predstavlja minimalnu razliku između količine drva koju će dobiti Ana i Biljana, što znači da su one dobile što je moguće sličniju količinu drva.

---