ZADATAK: TEŠKE TORBE(DRŽAVNO TAKMIČENJE IZ INFORMATIKE, 7. RAZRED) - REŠENJE
Tekst zadatka:
Dva mala putnika imaju ukupno četiri teške torbe. Svaki od putnika može da ponese najviše dve torbe, po jednu u svakoj ruci.
Sve torbe su zajedničke i bilo koji putnik može da nosi bilo koju torbu. U slučaju da su im torbe preteške,
naši putnici žele da koriste što manje tuđe pomoći.
Poznata je težina svake torbe, kao i najveći teret koji može da ponese svaki od putnika.
Potrebno je odrediti najmanju ukupnu težinu torbi koje oni ne mogu da ponesu.
Ulaz
U prvom redu standardnog ulaza su četiri prirodna broja razdvojena po jednim razmakom, težine torbi.
U drugom redu su dva prirodna broja razdvojena jednim razmakom, težine koje mogu da ponesu mali putnici.
Svi brojevi su manji od 1000.
Izlaz
Na standardni izlaz ispisati jedan neoznačen ceo broj, najmanju ukupnu težinu torbi za koje je putnicima potrebna pomoć.
Primer 1
Ulaz
1 2 3 4
5 6
Izlaz
0
Objašnjenje
Jedan putnik može da ponese torbe težina 1 i 4, a drugi torbe težina 2 i 3, tako da im nije potrebna pomoć.
Primer 2
Ulaz
2 3 4 5
5 6
Izlaz
3
Objašnjenje
Jedan putnik može da ponese torbu težine 5, a drugi torbe težina 2 i 4, pa im je potrebna pomoć za torbu težine 3.
Primer 3
Ulaz
12 20 15 17
17 14
Izlaz
35
99 56 34 22
3 4
211
Primer 4
7 5 4 2
7 9
Izlaz 2
Primer 5
1 1 1 1
1 1
Izlaz 2
Primer 6
99 99 99 99
1 1
Izlaz 396
Primer 7
99 45 44 99
144 99
Izlaz 44
primer 8
6 7 8 9
5 10
izlaz 21
primer 9
11 11 11 11
44 44
izlaz 0
primer 10
11 11 11 11
10 44
Izlaz 22
Dva mala putnika imaju ukupno četiri teške torbe. Svaki od putnika može da ponese najviše dve torbe, po jednu u svakoj ruci.
Sve torbe su zajedničke i bilo koji putnik može da nosi bilo koju torbu. U slučaju da su im torbe preteške,
naši putnici žele da koriste što manje tuđe pomoći.
Poznata je težina svake torbe, kao i najveći teret koji može da ponese svaki od putnika.
Potrebno je odrediti najmanju ukupnu težinu torbi koje oni ne mogu da ponesu.
Ulaz
U prvom redu standardnog ulaza su četiri prirodna broja razdvojena po jednim razmakom, težine torbi.
U drugom redu su dva prirodna broja razdvojena jednim razmakom, težine koje mogu da ponesu mali putnici.
Svi brojevi su manji od 1000.
Izlaz
Na standardni izlaz ispisati jedan neoznačen ceo broj, najmanju ukupnu težinu torbi za koje je putnicima potrebna pomoć.
Primer 1
Ulaz
1 2 3 4
5 6
Izlaz
0
Objašnjenje
Jedan putnik može da ponese torbe težina 1 i 4, a drugi torbe težina 2 i 3, tako da im nije potrebna pomoć.
Primer 2
Ulaz
2 3 4 5
5 6
Izlaz
3
Objašnjenje
Jedan putnik može da ponese torbu težine 5, a drugi torbe težina 2 i 4, pa im je potrebna pomoć za torbu težine 3.
Primer 3
Ulaz
12 20 15 17
17 14
Izlaz
35
99 56 34 22
3 4
211
Primer 4
7 5 4 2
7 9
Izlaz 2
Primer 5
1 1 1 1
1 1
Izlaz 2
Primer 6
99 99 99 99
1 1
Izlaz 396
Primer 7
99 45 44 99
144 99
Izlaz 44
primer 8
6 7 8 9
5 10
izlaz 21
primer 9
11 11 11 11
44 44
izlaz 0
primer 10
11 11 11 11
10 44
Izlaz 22
Kompletno rešenje je prikazano u nastavku:
#include <iostream>
#include <algorithm>
#include <stdint.h>
using namespace std;
/* globalna nizovna promenljiva koja čuva broj torbi koje su poneli putnici u početku inicijalizovana na nule*/
int broj_torbi[2]= {0};
/* Rekurzivna funkcija koja određuje najmanju vrednost ostatka težine koju putnici nisu mogli da ponesu
* parametri:
* ost tip int- ostatak težina koji je do tog trenutka preostao
*/
uint64_t odredi_manji(uint64_t &ost, int i,uint64_t &prvi, uint64_t &drugi,uint64_t niz[],bool okrenuto)
{
/*Ako je nivo poziva rekurzivne funkcije po dubini prešao poslednji onda se rekurzija vraća unazad i vraća vrednost ostatka težina na kraju rekurzije*/
if(i>=4)
{
return ost;
}
cout << "Pozivanje odredi_manji sa i=" << i << ", ost=" << ost << ", prvi=" << prvi << ", drugi=" << drugi << endl;
uint64_t a1 = prvi;//5,1,3,1 po dubini rekurzije za 1. primer
uint64_t b1 = drugi;//6,6,1,1
uint64_t a2 = drugi;//6,6,1,1
uint64_t b2 = prvi;//5,1,3,1
uint64_t ost1=ost;
uint64_t ost2=ost;
bool uzeo1=false;
int ind1=okrenuto ? 1 : 0;
// cout<<"Prvo: i="<<i<<", broj torbi: "<<broj_torbi[ind1]<<endl;
if(a1 >= niz[i] && broj_torbi[ind1] < 2) //razmatra da ce b dati manji ostatak do kraja
{
a1 = a1 - niz[i];/* Ako je prvi koji može da ponese još a1(5kg u nivou i=0 i u prvoj varijanti, uzeo sledeću torbu iz niza, niz[i], treba umanjiti vrednost koju u nastavku taj isti putnik mo]e da ponese. Za primer 1: 1=5-4,1=3-2,0=1-1 i 6 */
ost1=ost1-niz[i]; //Preračunava ukupan ostatak težina torbi. 6=10-4,
broj_torbi[ind1]++;
//cout << "prvo:Uzeta torba od putnika "<<a1<<", i="<<i<<", broj torbi: "<<broj_torbi[ind1]<<endl;
uzeo1=true;
}
/* cout << "Razmatram prvo pri i="<<i<<", ost1=" << ost1 << ", a=" << a1 << " za torbu težine " << niz[i]<< " i broj torbi "<<broj_torbi[ind1] << endl;*/
ost1=odredi_manji(ost1,i+1,a1,b1,niz,okrenuto);
if(uzeo1)
{
broj_torbi[ind1]--;
// cout<<"Posto je prvi uzeo("<<a1<<"), smanjujem broj torbi na "<<broj_torbi[ind1]<<endl;
}
/**Kraj razmatranja prvog u i-toj iteraciji**/
// cout<<"Kraj razmatranja prvog u "<<i<<" toj iteraciji, gde je ost1= "<<ost1<<endl;
bool uzeo2=false;
int ind2=okrenuto ? 0 : 1;
// cout<<"Drugo: i="<<i<<", broj torbi za tezinu "<<a2<<" je "<<broj_torbi[ind2]<<endl;
if(a2 >= niz[i] && broj_torbi[ind2] < 2) //razmatra da ce b dati manji ostatak do kraja
{
a2 = a2-niz[i]; /*Ako je prvi koji može da ponese još a2(6kg u nivou i=0 i u prvoj varijanti, uzeo sledeću torbu iz niza, niz[i], treba umanjiti vrednost koju u nastavku taj isti putnik mo]e da ponese. Za primer 1: 2=6-4 */
ost2=ost2-niz[i];//Preračunava ukupan ostatak težina torbi. 6=10-4,
broj_torbi[ind2]++;
// cout<<"drugo:Uzeta torba od putnika: "<<a2<<", i="<<i<<", broj torbi: "<<broj_torbi[ind2]<<endl;
uzeo2=true;//Uzeo je torbu
}
// cout << "Razmatram drugo pri i="<<i<<", ost2=" << ost2 << ", b=" << b2 << " za torbu težine " << niz[i] << endl;
okrenuto=!okrenuto; //menja logičku vrednost za novi poziv rekurzivne funkcije
ost2=odredi_manji(ost2,i+1,a2,b2,niz,okrenuto);//Novi poziv rekurzivne funkcije
if(uzeo2)
{
broj_torbi[ind2]--;
// cout<<"Posto je drugi uzeo("<<a2<<"), smanjujem broj torbi na "<<broj_torbi[ind2]<<endl;
}
/*Kraj razmatranja drugog u i-toj iteraciji*/
//cout<<"Kraj razmatranja drugog u "<<i<<" toj iteraciji, gde je ost1= "<<ost2<<endl;
uint64_t x=min(ost1,ost2);
//cout<<"Vracam "<<x<<" za i="<<i<<endl;
return x;
}
int main()
{
uint64_t niz[4],x,y; /*Niz težina torbi, x-težina koju može da ponese prvi putnik, y-težina koju može da ponese drugi putnik*/
uint64_t ost=0;
/*Učitavane težina torbi i smeštanje u niz*/
for(uint8_t i = 0; i < 4; i++)
{
cin >> niz[i];
ost += niz[i];/*Računa ukupan ostatak težina na početku*/
}
cin >> x >> y;
uint64_t min=x,max=y;
if(x>y)
{
min=y;
max=x;
}
sort(niz, niz + 4,greater<int>()); /*Sortira težine torbi po opadajućem redosledu*/
/* for(int i=0;i<4;i++){
cout<<niz[i]<<endl;
}*/
ost=odredi_manji(ost,0,max,min,niz,false);
cout<< ost<<endl;
return 0;
}
#include <algorithm>
#include <stdint.h>
using namespace std;
/* globalna nizovna promenljiva koja čuva broj torbi koje su poneli putnici u početku inicijalizovana na nule*/
int broj_torbi[2]= {0};
/* Rekurzivna funkcija koja određuje najmanju vrednost ostatka težine koju putnici nisu mogli da ponesu
* parametri:
* ost tip int- ostatak težina koji je do tog trenutka preostao
*/
uint64_t odredi_manji(uint64_t &ost, int i,uint64_t &prvi, uint64_t &drugi,uint64_t niz[],bool okrenuto)
{
/*Ako je nivo poziva rekurzivne funkcije po dubini prešao poslednji onda se rekurzija vraća unazad i vraća vrednost ostatka težina na kraju rekurzije*/
if(i>=4)
{
return ost;
}
cout << "Pozivanje odredi_manji sa i=" << i << ", ost=" << ost << ", prvi=" << prvi << ", drugi=" << drugi << endl;
uint64_t a1 = prvi;//5,1,3,1 po dubini rekurzije za 1. primer
uint64_t b1 = drugi;//6,6,1,1
uint64_t a2 = drugi;//6,6,1,1
uint64_t b2 = prvi;//5,1,3,1
uint64_t ost1=ost;
uint64_t ost2=ost;
bool uzeo1=false;
int ind1=okrenuto ? 1 : 0;
// cout<<"Prvo: i="<<i<<", broj torbi: "<<broj_torbi[ind1]<<endl;
if(a1 >= niz[i] && broj_torbi[ind1] < 2) //razmatra da ce b dati manji ostatak do kraja
{
a1 = a1 - niz[i];/* Ako je prvi koji može da ponese još a1(5kg u nivou i=0 i u prvoj varijanti, uzeo sledeću torbu iz niza, niz[i], treba umanjiti vrednost koju u nastavku taj isti putnik mo]e da ponese. Za primer 1: 1=5-4,1=3-2,0=1-1 i 6 */
ost1=ost1-niz[i]; //Preračunava ukupan ostatak težina torbi. 6=10-4,
broj_torbi[ind1]++;
//cout << "prvo:Uzeta torba od putnika "<<a1<<", i="<<i<<", broj torbi: "<<broj_torbi[ind1]<<endl;
uzeo1=true;
}
/* cout << "Razmatram prvo pri i="<<i<<", ost1=" << ost1 << ", a=" << a1 << " za torbu težine " << niz[i]<< " i broj torbi "<<broj_torbi[ind1] << endl;*/
ost1=odredi_manji(ost1,i+1,a1,b1,niz,okrenuto);
if(uzeo1)
{
broj_torbi[ind1]--;
// cout<<"Posto je prvi uzeo("<<a1<<"), smanjujem broj torbi na "<<broj_torbi[ind1]<<endl;
}
/**Kraj razmatranja prvog u i-toj iteraciji**/
// cout<<"Kraj razmatranja prvog u "<<i<<" toj iteraciji, gde je ost1= "<<ost1<<endl;
bool uzeo2=false;
int ind2=okrenuto ? 0 : 1;
// cout<<"Drugo: i="<<i<<", broj torbi za tezinu "<<a2<<" je "<<broj_torbi[ind2]<<endl;
if(a2 >= niz[i] && broj_torbi[ind2] < 2) //razmatra da ce b dati manji ostatak do kraja
{
a2 = a2-niz[i]; /*Ako je prvi koji može da ponese još a2(6kg u nivou i=0 i u prvoj varijanti, uzeo sledeću torbu iz niza, niz[i], treba umanjiti vrednost koju u nastavku taj isti putnik mo]e da ponese. Za primer 1: 2=6-4 */
ost2=ost2-niz[i];//Preračunava ukupan ostatak težina torbi. 6=10-4,
broj_torbi[ind2]++;
// cout<<"drugo:Uzeta torba od putnika: "<<a2<<", i="<<i<<", broj torbi: "<<broj_torbi[ind2]<<endl;
uzeo2=true;//Uzeo je torbu
}
// cout << "Razmatram drugo pri i="<<i<<", ost2=" << ost2 << ", b=" << b2 << " za torbu težine " << niz[i] << endl;
okrenuto=!okrenuto; //menja logičku vrednost za novi poziv rekurzivne funkcije
ost2=odredi_manji(ost2,i+1,a2,b2,niz,okrenuto);//Novi poziv rekurzivne funkcije
if(uzeo2)
{
broj_torbi[ind2]--;
// cout<<"Posto je drugi uzeo("<<a2<<"), smanjujem broj torbi na "<<broj_torbi[ind2]<<endl;
}
/*Kraj razmatranja drugog u i-toj iteraciji*/
//cout<<"Kraj razmatranja drugog u "<<i<<" toj iteraciji, gde je ost1= "<<ost2<<endl;
uint64_t x=min(ost1,ost2);
//cout<<"Vracam "<<x<<" za i="<<i<<endl;
return x;
}
int main()
{
uint64_t niz[4],x,y; /*Niz težina torbi, x-težina koju može da ponese prvi putnik, y-težina koju može da ponese drugi putnik*/
uint64_t ost=0;
/*Učitavane težina torbi i smeštanje u niz*/
for(uint8_t i = 0; i < 4; i++)
{
cin >> niz[i];
ost += niz[i];/*Računa ukupan ostatak težina na početku*/
}
cin >> x >> y;
uint64_t min=x,max=y;
if(x>y)
{
min=y;
max=x;
}
sort(niz, niz + 4,greater<int>()); /*Sortira težine torbi po opadajućem redosledu*/
/* for(int i=0;i<4;i++){
cout<<niz[i]<<endl;
}*/
ost=odredi_manji(ost,0,max,min,niz,false);
cout<< ost<<endl;
return 0;
}
Komentari svetlo sive boje se odnose na kod za debug-ovanje.
Posle uklanjanja nekih komentara za debagovanje i za testiranje npr. primera 1, pokrenu'emo aplikaciju i dobiti sledeći izlaz:
Posle uklanjanja nekih komentara za debagovanje i za testiranje npr. primera 1, pokrenu'emo aplikaciju i dobiti sledeći izlaz:
Slika 1: Zadatak Teške torbe-izlaz za primer 1 - 1 deo
Ovde se može pratiti rekurzija u svom toku kroz više poziva u dubinu do nivoa 4 i povratak kroz rekurziju. Vrednost i=0 znači da je reč o početnom nivou rekurzije. Odatle imamo dve grane jer postoje dve varijante koje izračunavaju ostatak 1 i ostatak 2 i sa tog nivoa se vraća manja od te dve vrednosti. Mogu se dalje pratiti rekurzije u višim nivoima npr za i=1, i=2 i i=3. Za i=4, počnje proces vraćanja ostatka, kroz nivoe nazad.
Kroz nivoe, takoće treba pratiti koliko torbi je do tog nivoa pokupljeno od strane oba putnika i ako ta vrednost dostigne 2, taj putnik dalje ne može uzimati torbe. U nastavku izvršenja može se videti:
Kroz nivoe, takoće treba pratiti koliko torbi je do tog nivoa pokupljeno od strane oba putnika i ako ta vrednost dostigne 2, taj putnik dalje ne može uzimati torbe. U nastavku izvršenja može se videti:
Slika 2: Zadatak Teške torbe-izlaz za primer 1 - 2 deo
Slika 3: Zadatak Teške torbe-izlaz za primer 1 - 3 deo
Pri prosleđivanju broja torbi kroz nivoe rekurzije i čitanju ovih vrednosti za prvog i drugog putnika mora se voditi računa iz koje varijante, prve ili druge, je pozvana rekurzivna funkcija jer od toga zavisi da li se vrednost broja ponetih torbi za npr. prvog putnika trebala pročitati sa pozicije 0 ili sa pozicije 1 iz niza broj_torbi[], jer se tokom rekurzije menja redosled onog putnika koji se razmatra kao putnik 1(a1 i a2) i onog putnika koji se razmatra kao putnik 2(b1 ili b2). Za ovu potrebu je uvedena logićna promenljiva "obrnuto".