F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 1274. -- [BeiJingWc2008]Equation

1274: [BeiJingWc2008]Equation

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 64  Solved: 10
[Submit][Status][Discuss]

Description

给定3*N个正整数
A1,A2...An
B2,B2...Bn
C1,C2...Cn
另给定M对正整数Si,Ti对于每一对Si,Ti
求下列方程组的一组非负实数解
A1*X1+A2*X2+...+AnXn=Si
B1*X1+B2*X2+...+BnXn=Ti
使得C1*X1+C2*X2+...+CnXn最大

Input

第一行两个整数代表N,M 
接下来N行每行三个正整数Ai,Bi,Ci
1<=Ai,Bi,Ci,Si,Ti<=1000000

Output

输出为M行,第i行代表Si,Ti
如果方程无解输出IMPOSSIBLE
否则输出一个实数保留五位小数,代表对应的最大值。

Sample Input

1 2
100 100 10
3 3
99 100

Sample Output

0.30000
IMPOSSIBLE

HINT

Source

[Submit][Status][Discuss]

HOME Back