Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1603
Felix and Leti are going to get married soon, everybody is preparing their gifts, but they have a big problem: the money, their budget is not very high. They would like to get a good restaurant, to “sleep” their first night in a nice hotel and to spend a marvellous honey-moon travelling around the world. The best way to get the cheapest price is getting an all-included package, that is, we have to contract the travel, the restaurant and the hotel all together. Is that possible? We have to find the cheapest travel agency-restaurant-hotel combination.The problem is that not all the combinations are allowed. Input Each test case has the following format: • The first line consists of three integers T, R, H indicating the number of travel agencies, restaurants and hotels, respectively. Assume that T < 20, R < 20 and H < 20. Travel agencies, restaurants and hotels are numbered: 0, 1, 2, … • The next T + R + H lines are divided into three blocks: – The first block has T rows and R+ 1 columns. The first column are the travel agencies’ offer prices for the world-tour. In the rest of columns, cell (i, j) is ‘0’ if the travel agency (i) can be combined with the restaurant (j) and ‘1’ if not. – The second block has R rows and H + 1 columns. The first column are the restaurants’ offer prices. In the rest of columns, cell (i, j) is ‘0’ if the restaurant (i) can be combined with the hotel (j) and ‘1’ if not. – The third block has H rows and T + 1 columns. The first column are the hotels’ offer prices. In the rest of columns, cell (i, j) is ‘0’ if the hotel (i) can be combined with the travel-agency (j) and ‘1’ if not. • The input ends with an empty line. Output For each test case the output should consist of a single line with the number of the travel agency (T), restaurant (R) and hotel (H), and the cheapest total price (P). This values should be output in the format: T R H : P If there is not any combination, the output should be a line with the text: ‘Don't get married!’ If more than one possibility exists, you can output any of them.
Sample Input 2 2 2 12 0 0 1 1 1 34 0 0 3 1 1 21 1 0 2 1 0 2 2 2 12 0 0 1 0 0 34 0 0 3 0 0 21 0 0 2 0 0 5 5 6 970 0 1 1 1 0 856 0 0 0 0 0 1290 1 0 0 1 0 1361 0 0 1 0 0 82 0 0 0 0 1 1182 0 0 0 1 1 0 450 0 1 1 0 0 1 895 0 0 1 0 1 1 1865 0 1 0 0 1 1 183 1 1 1 1 1 0 252 1 1 1 0 1 1813 1 0 0 1 1 1429 0 0 1 0 0 1522 1 1 1 0 0 1762 0 0 1 0 1 1946 0 1 0 0 0
Sample Output Don't get married! 1 1 1:6 4 1 3:2054
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,r,h;
int p,a;
while(scanf("%d %d %d",&t,&r,&h) != EOF){
vector < unordered_set<int>> allowedR(t);
vector < unordered_set<int>> allowedH(r);
vector < unordered_set<int>> allowedT(h);
vector<int> Tprice;
vector<int> Rprice;
vector<int> Hprice;
for(int i=0;i < t;i++){
cin >> p;
Tprice.push_back(p);
for(int j=0;j < r;j++){
cin >> a;
if(a==0) allowedR[i].insert(j);
}
}
for(int i=0;i<r;i++){
cin >> p;
Rprice.push_back(p);
for(int j=0;j < h;j++){
cin >> a;
if(a==0) allowedH[i].insert(j);
}
}
for(int i=0;i < h;i++){
cin >> p;
Hprice.push_back(p);
for(int j=0;j < t;j++){
cin >> a;
if(a==0) allowedT[i].insert(j>;
}
}
int res = 1e8;
tuple < int,int,int> res2;
for(int i=0;i < t;i++)
for(int j=0;j < r;j++)
for(int k=0;k < h;k++)
if(allowedR[i].count(j) && allowedH[j].count(k) && allowedT[k].count(i)){
int price = Tprice[i]+Rprice[j]+Hprice[k];
if(price < res){
res = price;
res2 = make_tuple(i,j,k);
}
}
if(res == 1e8) printf("Don't get married!\n">;
else printf("%d %d %d:%d\n",get < 0>(res2),get<1>(res2),get<2>(res2),res);
}
}
Input
12 0 0
1 1 1
34 0 0
3 1 1
21 1 0
2 1 0
2 2 2
12 0 0
1 0 0
34 0 0
3 0 0
21 0 0
2 0 0
5 5 6
970 0 1 1 1 0
856 0 0 0 0 0,br> 1290 1 0 0 1 0
1361 0 0 1 0 0
82 0 0 0 0 1
1182 0 0 0 1 1 0
450 0 1 1 0 0 1
895 0 0 1 0 1 1
1865 0 1 0 0 1 1
183 1 1 1 1 1 0
252 1 1 1 0 1
1813 1 0 0 1 1
1429 0 0 1 0 0
1522 1 1 1 0 0
1762 0 0 1 0 1
1946 0 1 0 0 0
Output
1 1 1:6
4 1 3:2054
Demonstration
UVA Online Judge solution - 10662-The Wedding - UVA Online Judge solution in C,C++,java