Mógłby mi ktoś krok po kroku wytłumaczyć co tu się po kolei dzieje i jaka jest złożoność obliczeniowa programu? Z góry dzięki.
Treść.
Robotnicy budowlani pracujący na placu przy hurtowni piwa zauważyli, że magazyn
hurtowni jest bardzo słabo pilnowany i bez problemu można z niego wynieść puszki piwa.
Tylko jak? Wpadli na genialny pomysł. Zauważyli, że rury sanitarne, które mogli bez
problemu przewozić przez bramę hurtowni mają średnicę niewiele większą od średnic puszek
piwa. Postanowili upakować każdą z rur puszkami, a następnie wywieźć tak „obciążone” rury
z hurtowni. Każda z puszek piwa miała znaną cenę, więc fachowcy dbali też o to, aby w rurach znalazły się najcenniejsze z nich. Dla niepoznaki każda rura miała nałożone obustronne zaślepki, aby
strażnik nie zauważył jej wnętrza. Spryt fachowców nie znał granic, więc zadbali też o to, aby
każda z rur była maksymalnie upakowana, czyli suma wysokości puszek w rurze była równa
wysokości całej rury. Wysokość puszek, które mogły być włożone do rury oraz wysokość rur
jest z założenia pewną całkowitą potęgą dwójki. \(\displaystyle{ 2 ^{i} gdzie (1 \le i \le 1000)}\)
Napisz program, który:
· po podaniu danych określających wysokości rur wyrażonych wykładnikami potęg
dwójki oraz danym asortymencie puszek, określającym ich wysokości (również w
postaci wykładników potęg dwójki) oraz wartości,
· sprawdzi, czy możliwe jest upakowanie wszystkich rur puszkami. Jeżeli sposobów
upakowania będzie kilka, to należy wybrać taki, który ma największą wartość łączna
puszek.
Wejście
W pierwszej linii pliku tekstowego in.txt zapisana jest jedna liczba n -liczba puszek w magazynie n, która spełnia nierówność: \(\displaystyle{ 1 \le n \le 1000000}\). W następnych n liniach znajdują się dwójki liczb całkowitych nieujemnych i oraz w oddzielone spacją: i –wysokość puszki, w - wartość puszki. Wiadomo, że wysokość jest potęgą dwójki, zatem i jest wykładnikiem tej potęgi. Wartość puszki w spełnia warunek \(\displaystyle{ w \le 10000}\) . W kolejnej linii pliku znajduje się dodatnia liczba całkowita t określająca, ile różnych wysokości mają rury, którymi dysponują fachowcy. W następnych t liniach zapisane są pary dodatnich liczb całkowitych oddzielonych pojedynczym odstępem. Pierwsza z tych liczb l jest wysokością rury (właściwie wykładnikiem potęgi dwójki), natomiast druga liczba d oznacza liczbę dostępnych rur tej wysokości. Zakładamy, że \(\displaystyle{ t \le 5000 a l \le 1000}\)
Wyjście
W pliku out.txt należy wypisać napis NIE, jeżeli nie istnieje możliwość upakowania wszystkich rur puszkami albo liczba całkowita równa maksymalnej, łącznej wartości puszek z wszystkich rur, o ile można nimi szczelnie wypełnić wszystkie rury z podanego zestawu.
KOD:
Kod: Zaznacz cały
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
struct para{
int first;
int second;
};
void merge(para tab[] ,int pocz, int sr, int kon)
{
int i,j,q;
para t[kon];
for (i=pocz; i<=kon; i++) t[i]=tab[i];
i=pocz; j=sr+1; q=pocz;
while (i<=sr && j<=kon) {
if ((t[i].first)<(t[j].first))
tab[q++]=t[i++];
else if((t[i].first)==(t[j].first))
if((t[i].second)<(t[j].second))
tab[q++]=t[i++];
else
tab[q++]=t[j++];
else
tab[q++]=t[j++];
}
while (i<=sr) tab[q++]=t[i++];
}
void mergesort(para tab[] ,int pocz, int kon)
{
int sr;
if (pocz<kon) {
sr=(pocz+kon)/2;
mergesort(tab, pocz, sr);
mergesort(tab, sr+1, kon);
merge(tab, pocz, sr, kon);
}
}
int partition2(int tablica[], int p, int r)
{
int x = tablica[p];
int i = p, j = r, w;
while (true)
{
while (tablica[j] > x)
j--;
while (tablica[i] < x)
i++;
if (i < j)
{
w = tablica[i];
tablica[i] = tablica[j];
tablica[j] = w;
i++;
j--;
}
else
return j;
}
}
void quicksort2(int tablica[], int p, int r)
{
int q;
if (p < r)
{
q = partition2(tablica,p,r);
quicksort2(tablica, p, q);
quicksort2(tablica, q+1, r);
}
}
int potega(int n)
{
if(n==0)
return 1;
return 2*potega(n-1);
}
bool sort( int i, int j)
{
return (i >j);
}
int main()
{
int ip, x, ir, y;
para *tab;
fstream plik;
plik.open("in.txt");
plik>>ip;
tab=new para[ip];
int *tablica_wysokosci=new int [ip];
int i=0;
while(i<ip)
{
plik>>x;
plik>>y;
tab[i].first = y;
cout<<tab[i].first<<endl;
tab[i].second = potega(x);
i++;
}
mergesort(tab, 0, ip-1);
for(i=ip-1; i>-1; i--)
{
if(i!=0)
if(tab[i].first == tab[i-1].first)
{
if(tab[i].second > tab[i-1].second)
{
int tmp = tab[i].second;
int tmpF = tab[i].first;
tab[i].second = tab[i-1].second;
tab[i].first = tab[i-1].first;
tab[i-1].second = tmp;
tab[i-1].first = tmpF;
i=ip;
}
}
}
for(i=ip-1; i>-1; i--)
{
cout<<"Wart "<< tab[i].first<<" wys "<<tab[i].second<<endl;
}
plik>>ir;
endl;
int ilosc=0;
i=0;
while(i<ir)
{
plik>>x;
tablica_wysokosci[ilosc]=potega(x);
plik>>y;
ilosc++;
while (y>1)
{
tablica_wysokosci[ilosc]=potega(x);
ilosc++;
y--;
}
i++;
}
quicksort2(tablica_wysokosci, 0, ilosc);
for(i=0; i<ilosc; i++)
{
cout<<"wys "<<tablica_wysokosci[i]<<endl;
}
int suma=0, j;
bool empty=false;
for(i=0; i<ilosc; i++)
{
cout<<"wys "<<tablica_wysokosci[i]<<endl;
for(j=ip-1; j>-1; j--)
{
if(tab[j].second<=tablica_wysokosci[i] && tab[j].first!=-1)
{
suma+=tab[j].first;
cout<<"Tab1 "<<tablica_wysokosci[i]<<" wart "<< tab[j].first<<endl;
tab[j].first=-1;
tablica_wysokosci[i]-=tab[j].second;
cout<<"Tab2 "<<tablica_wysokosci[i]<<" wart "<< tab[j].first<<endl;
tab[j].second=-1;
}
}
if(tablica_wysokosci[i]!=0)
empty=true;
}
plik.close();
string nie="Nie";
ofstream plik2;
plik2.open("out.txt");
switch (empty)
{
case true:
cout<<"Nie mozna umiescic puszek"<<endl;
plik2<<"Nie";
break;
case false:
cout<<"Suma wartosi = "<<suma<<endl;
plik2<<suma;
break;
}
plik2.close();
delete [] tablica_wysokosci;
system("pause");
return 0;
}