7. KUVAR — REŠENJE



Tekst zadatka



NAPOMENA: Zadatak sa 1. kruga kvalifikacija, sezona 2022/2023. Preuzeto sa dms.rs/informatika-osnovne-skole/

Zadatak za 8. razred.

Potrebno predznanje: Podaci u C++, Operatori u C++

Kuvaru je za jednu porciju potrebno za glavno jelo (pored ostalih sastojaka) m grama mesa, a za salatu ili k grama kupusa ili c grama cvekle.

Na raspolaganju je M grama mesa, K grama kupusa i C grama cvekle, a svih ostalih sastojaka ima mnogo više.

Napisati program koji učitava potrebne količine za jednu porciju m, k, c, a zatim i raspoložive količine M, K, C, i ispisuje za koliko celih porcija (glavno jelo i salata) kuvar ima dovoljno sastojaka.



Ulaz


Na standardnom ulazu su redom brojevi m, k, c, M, K, C, svaki u posebnom redu.

Svi brojevi su celi, pozitivni i manji od 50000.



Izlaz


Na standardni izlaz ispisati samo jedan ceo neoznačen broj, a to je broj celih porcija koje mogu da se pripreme.



Primer 1


Ulaz

200
250
150
2200
1400
890

Izlaz

10


Primer 2


Ulaz

150
200
100
6100
5100
1000

Izlaz

35


Objašnjenje rešenja



Za jednu kompletnu porciju potrebno je pripremiti glavno jelo i salatu.

Najpre možemo izračunati koliko glavnih jela kuvar može da pripremi od raspoložive količine mesa: 

M / m

Pošto se traži broj celih porcija, koristi se celobrojno deljenje. Na primer, ako imamo 2200 grama mesa, a za jednu porciju je potrebno 200 grama, možemo pripremiti 11 celih glavnih jela.

Zatim računamo koliko salata možemo pripremiti od kupusa i koliko od cvekle. 

K / k
C / c

Važan detalj je to što za jednu salatu koristimo ili kupus ili cveklu. To znači da kuvar može neke salate napraviti od kupusa, a neke od cvekle. Zato se ova dva broja sabiraju. 

K / k + C / c

Na kraju, broj kompletnih porcija određuje manji od broja mogućih glavnih jela i broja mogućih salata. 

min(M / m, K / k + C / c)

Funkcija min() vraća manju od dve vrednosti. Upravo ta manja vrednost predstavlja maksimalan broj kompletnih porcija koje kuvar može da pripremi.



Ideja algoritma



  1. Učitati potrebne količine za jednu porciju: m, k i c.
  2. Učitati raspoložive količine: M, K i C.
  3. Izračunati koliko glavnih jela može da se pripremi: Pm = M / m.
  4. Izračunati koliko salata može da se pripremi od kupusa: Pk = K / k.
  5. Izračunati koliko salata može da se pripremi od cvekle: Pc = C / c.
  6. Izračunati ukupan broj salata kao Ps = Pk + Pc.
  7. Uzeti minimum između broja glavnih jela i ukupnog broja salata.
  8. Ispisati dobijeni broj.


Ključna ideja je da su za jednu kompletnu porciju potrebni i glavno jelo i salata. Zato ne možemo pripremiti više kompletnih porcija nego što možemo pripremiti jednog od ta dva dela obroka.



Kompletno C++ rešenje



// ZADATAK 7. KUVAR - REŠENJE

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int m, k, c, M, K, C;

    // m - količina mesa potrebna za jednu porciju
    // k - količina kupusa potrebna za jednu salatu
    // c - količina cvekle potrebna za jednu salatu
    //
    // M - raspoloživa količina mesa
    // K - raspoloživa količina kupusa
    // C - raspoloživa količina cvekle

    // Učitavanje podataka.
    cin >> m >> k >> c >> M >> K >> C;

    // Broj glavnih jela koja možemo pripremiti
    // na osnovu raspoložive količine mesa.
    int Pm = M / m;

    // Broj salata koje možemo pripremiti od kupusa.
    int Pk = K / k;

    // Broj salata koje možemo pripremiti od cvekle.
    int Pc = C / c;

    // Za svaku salatu možemo koristiti ili kupus ili cveklu.
    // Zato se ukupan broj mogućih salata dobija sabiranjem.
    int Ps = Pk + Pc;

    // Za kompletnu porciju potrebno je imati
    // i glavno jelo i salatu.
    // Zato uzimamo manju od ove dve vrednosti.
    int brojPorcija = min(Pm, Ps);

    // Ispis konačnog rezultata.
    cout << brojPorcija << endl;

    return 0;
}


Objašnjenje koda



1. Zaglavlja programa
Zaglavlje <iostream> omogućava rad sa standardnim ulazom i izlazom, odnosno korišćenje naredbi cin i cout.

Zaglavlje <algorithm> potrebno je zbog funkcije min(), koja se koristi na kraju programa.


2. Učitavanje podataka
Naredba cin >> m >> k >> c >> M >> K >> C; učitava svih šest vrednosti.

Prve tri vrednosti predstavljaju potrebne količine sastojaka za jednu porciju, a druge tri predstavljaju količine koje su kuvaru na raspolaganju.


3. Izračunavanje broja glavnih jela
Broj glavnih jela određujemo celobrojnim deljenjem raspoložive količine mesa sa količinom potrebnom za jedno jelo: 

int Pm = M / m;

Na primer, ako je M = 2200, a m = 200, dobijamo: 

2200 / 200 = 11

Dakle, imamo dovoljno mesa za 11 glavnih jela.


4. Izračunavanje salata od kupusa
Ako je za jednu salatu potrebno k grama kupusa, a imamo K grama, broj salata od kupusa je: 

int Pk = K / k;

5. Izračunavanje salata od cvekle
Na isti način računamo koliko salata možemo napraviti od cvekle: 

int Pc = C / c;

6. Ukupan broj salata
Pošto jednu salatu možemo napraviti ili od kupusa ili od cvekle, možemo iskoristiti oba raspoloživa resursa.

Zato ukupan broj salata računamo: 

int Ps = Pk + Pc;

Na primer, ako možemo napraviti 5 salata od kupusa i 5 salata od cvekle, ukupno možemo napraviti 10 salata.


7. Konačan broj kompletnih porcija
Za jednu kompletnu porciju potrebni su i glavno jelo i salata. Zato konačan rezultat ne može biti veći od bilo kog od ta dva broja.

Koristimo funkciju min(): 

int brojPorcija = min(Pm, Ps);

Ako imamo sastojke za 11 glavnih jela i 10 salata, možemo pripremiti samo 10 kompletnih porcija.



Praćenje algoritma na primeru 1



Potrebno je: 

m = 200
k = 250
c = 150

Na raspolaganju imamo: 

M = 2200
K = 1400
C = 890

Broj glavnih jela: 

Pm = 2200 / 200 = 11

Broj salata od kupusa: 

Pk = 1400 / 250 = 5

Broj salata od cvekle: 

Pc = 890 / 150 = 5

Ukupan broj salata: 

Ps = 5 + 5 = 10

Konačan broj kompletnih porcija: 

min(11, 10) = 10

Zato je rezultat: 

10


Praćenje algoritma na primeru 2



Potrebno je: 

m = 150
k = 200
c = 100

Na raspolaganju imamo: 

M = 6100
K = 5100
C = 1000

Broj glavnih jela: 

Pm = 6100 / 150 = 40

Broj salata od kupusa: 

Pk = 5100 / 200 = 25

Broj salata od cvekle: 

Pc = 1000 / 100 = 10

Ukupan broj salata: 

Ps = 25 + 10 = 35

Konačan broj kompletnih porcija: 

min(40, 35) = 35

Zato je rezultat: 

35


Zašto se ne koristi max()?



Jedna od mogućih grešaka u ovom zadatku jeste korišćenje funkcije max() za izbor između broja salata od kupusa i broja salata od cvekle.

Na primer, ako imamo mogućnost da napravimo 7 salata od kupusa i 4 salate od cvekle, nije tačno da možemo napraviti samo 7 salata. Možemo napraviti: 

7 + 4 = 11

Zato je ispravno: 

Ps = Pk + Pc;

Funkcija min() koristi se tek na kraju, kada upoređujemo broj glavnih jela sa ukupnim brojem salata.



Česte greške



1. Korišćenje max() umesto sabiranja
Pogrešno: 

int Ps = max(Pk, Pc);

Ispravno: 

int Ps = Pk + Pc;

2. Zaboravljanje funkcije min()
Nije dovoljno izračunati samo broj glavnih jela ili samo broj salata. Potrebno je imati oba dela kompletnog obroka.

Zato se na kraju koristi: 

min(Pm, Ps)

3. Korišćenje realnog deljenja
Zadatak traži broj celih porcija, pa je potrebno celobrojno deljenje.

Na primer: 

890 / 150 = 5

Ostatak od 140 grama nije dovoljan za još jednu celu salatu i zato se ne računa.


4. Izostavljanje zaglavlja <algorithm>
Funkcija min() pripada standardnoj biblioteci algoritama, pa je pravilno navesti: 

#include <algorithm>


Vremenska i memorijska složenost



Program izvršava samo nekoliko aritmetičkih operacija, bez obzira na veličinu ulaznih brojeva.

Zato je vremenska složenost: O(1).

Program koristi samo nekoliko celobrojnih promenljivih, pa je i memorijska složenost: O(1).



Sažetak rešenja



Za rešavanje zadatka potrebno je izračunati tri osnovne stvari: koliko glavnih jela možemo napraviti, koliko salata možemo napraviti od kupusa i koliko od cvekle.

Pošto jednu salatu možemo napraviti ili od kupusa ili od cvekle, ukupan broj salata predstavlja zbir: 

K / k + C / c

Kompletna porcija zahteva i glavno jelo i salatu, pa je konačan odgovor minimum između ta dva broja: 

min(M / m, K / k + C / c)

To je cela suština zadatka.



Povratak
|< Kvalifikacije za okružna takmičenja