Description
There are some water, milk and wine in your kitchen. Your naughty little sister made some strange drinks by mixing them together, and then adds some sugar! She wants to know whether they taste good, but she doesn't want to try them herself. She needs your help.
Your sister knows that you don't want to drink them either (anyone wants to?), so she gives you a chance to escape: if you can guess the price of a special drink, she gives you freedom. Warning: she loves her special drink so much that you should never under-estimate its cost! That is, you're to find the most expensive possible price of it.
The price of each drink equals to its cost. If the amounts of water, milk, wine and sugar used in the drink are a1, a2, a3 and a4 respectively, and the unit costs of water, milk, wine and sugar are (c_1, c_2, c_3) and (c_4) respectively, then the drink costs (a_1c_1 + a_2c_2 + a_3c_3 + a_4c_4) . To give you some hope to win, she told you the costs of exactly (n) ordinary drinks. Furthermore, she promised that the total cost of sugar a4c4 is always a real number in the interval ([L, R]) , in any drink.
Sadly, you don't know the exact price of anything (you're a programmer, not a housewife!), but you know that water is the cheapest; wine is the most expensive, i.e., (0 le c_1 le c_2 le c_3) . Then the best thing you can do is to assume units costs can be any real numbers satisfying this inequality.
Write a program to find the highest possible price of the special drink.
Input
The input contains several test cases. The first line of each test case contains three positive integers (n, L, R) ((1 le n le 100, 0 le L le R le 100)) . The next (n) lines each contain four non-negative integer (a_1, a_2, a_3 , p) ((0 le a_1,a_2,a_3 le 100, 0 le p le 10000)) , the amount of water, milk and wine, and the price. The last line of the case contains three integers (a1, a2, a3 (0 le a1,a2,a3 le 100)) , the drink to be estimated. The last test case is followed by a single zero, which should not be processed.
Output
For each test case, print the case number and the highest possible price to four decimal places. If the input is selfcontradictory, output ``Inconsistent data". If the price can be arbitrarily large, output "Too expensive!".
Sample Input
1 3 5
1 2 3 10
2 4 6
1 2 4
1 1 1 1
1 1 1
1 3 8
0 1 0 17
0 0 1
3 1 2
2 1 3 14
1 5 1 15
7 3 2 21
4 1 6
2 0 2
45 31 53 4087
30 16 1 1251
11 51 34
0
Sample Output
Case 1: 19.0000
Case 2: Inconsistent data
Case 3: Too expensive!
Case 4: 26.2338
Case 5: 3440.3088
其实就是一个线性规划裸题。
首先有(c_1-c_2le0,c_2-c_3le0)
之后对于第(i)条限制，我们可得(P-R le a_{i1}c_1+a_{i2}c_2+a_{i3}c3 le P-L)。我们可以把他化成两个限制(a_{i1}c_1+a_{i2}c_2+a_{i3}c3 le P-L,-a_{i1}c_1-a_{i2}c_2-a_{i3}c3 le R-P)。最大化(a_1c_1+a_2c_2+a_3c_3+R)。直接上单纯形就行了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define maxn (210)
#define eps (1e-8)
int cnt,tot,T,N,L,R,idx[maxn],idy[maxn],q[maxn]; double lim[maxn][5];
inline void pivot(int x,int y)
{
swap(idy[x],idx[y]);
double tmp = lim[x][y]; lim[x][y] = 1/lim[x][y];
for (int i = 0;i <= 3;++i) if (y != i) lim[x][i] /= tmp;
cnt = 0; for (int i = 0;i <= 3;++i) if (i != y&&(lim[x][i] > eps||lim[x][i] < -eps)) q[++cnt] = i;
for (int i = 0;i <= tot;++i)
{
if ((x == i)||(lim[i][y] < eps&&lim[i][y] > -eps)) continue;
for (int j = 1;j <= cnt;++j) lim[i][q[j]] -= lim[x][q[j]]*lim[i][y];
lim[i][y] = -lim[i][y] / tmp;
}
}
inline bool work()
{
while (true)
{
int x = 0,y = 0;
for (int i = 1;i <= tot;++i) if (lim[i][0] < -eps&&((!x)||(rand()&1))) x = i; if (!x) break;
for (int i = 1;i <= 3;++i) if (lim[x][i] < -eps&&((!y)||(rand()&1))) y = i; if (!y) return puts("Inconsistent data"),false;
pivot(x,y);
}
while (true)
{
int x = 0,y = 0; double mn = 1e60;
for (int i = 1;i <= 3;++i) if (lim[0][i] > eps) { y = i; break; } if (!y) break;
for (int i = 1;i <= tot;++i) if (lim[i][y] > eps&&lim[i][0]/lim[i][y] < mn) mn = lim[i][0]/lim[i][y],x = i; if (!x) return puts("Too expensive!"),false;
pivot(x,y);
}
return true;
}
int main()
{
//freopen("1903.in","r",stdin);
//freopen("1903.out","w",stdout);
srand(233);
while (++T)
{
scanf("%d %d %d",&N,&L,&R); if (!N) break;
printf("Case %d: ",T); tot = 0; memset(lim,0,sizeof(lim));
for (int i = 1;i <= N;++i)
{
for (int j = 1;j <= 3;++j) scanf("%lf",lim[tot+1]+j);
scanf("%lf",lim[++tot]+0); lim[tot+1][0] = -lim[tot][0]+R; ++tot; lim[tot-1][0] -= L;
for (int j = 1;j <= 3;++j) lim[tot][j] = -lim[tot-1][j];
}
lim[++tot][1] = 1; lim[tot][2] = -1;
lim[++tot][2] = 1; lim[tot][3] = -1;
for (int i = 1;i <= 3;++i) scanf("%lf",lim[0]+i);
for (int i = 1;i <= 3;++i) idx[i] = i;
for (int i = 1;i <= tot;++i) idy[i] = i+3;
if (work()) printf("%.4lf
",-lim[0][0]+R);
}
//fclose(stdin); fclose(stdout);
return 0;
}