ACM ICPC - Number theory
I have dealt with ACM ICPC past issues http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1030
I am unable to resolve this issue. I don't know how to do it in an efficient way within 3 seconds. I think this problem is based on number theory but don't know what to do. Thank!
+3
user1134599
source
to share
1 answer
So I believe that given:
(a1,b1,c1), (a2,b2,c2) ... (an,bn,cn)
You need to decide if non-negative coefficients exist:
X = (x1,x2,...,xn)
such that
x1*a1 + x2*a2 + ... + xn*an ==
x1*b1 + x2*b2 + ... + xn*bn ==
x1*c1 + x2*c2 + ... + xn*cn
A little linear algebra is all it takes.
Council . Try to plot the input with n == 4, so all 4 xis must be positive in order to solve the problem (and it cannot be solved with just 3). Is it possible?
0
source to share