11128 - Faulty Computer

[sunny]

i tried 2 do it with backtrack(with some pruning) but getin TLE.
does it have mathematical solution?

[sclo]

You have to do pruning properly to avoid getting TLE. The idea is this, consider that we've found x[0],x[1],x[2],...,x
if abs(x[0]+x[1]*sqrt(a[1])+x[2]*sqrt(a[2])+...+x*sqrt(a)) - 9*(sqrt(a[i+1])+ ...+ sqrt(a[7])) >= 1e-4, then we know that it can't lead to a valid solution, so we can prune. Another way to prune is to sort the a in nonincreasing order first.

[sunny]

actually i was getin TLE bcuz of calling the sqrt() at each level.
anyway, thanx 4 the reply.

[tryit1]

I tried for various combinations of values for a1,a2..a6 but never get No Solution. Btw why are bounds on a1,a2,..a6 important ?

Can you give me cases where it is No Solution ?

Got AC after precision.

Code: Select all

16
1 1 1 1 1 1
1 2 3 4 5 6
6 5 4 33 0 0
3 2 1 4 5 6
81 81 81 81 81 81
4 5 2 4 3 2
7 8 9 11 12 13
9 10 12 13 14 15
90 89 88 87 86 85
9 8 7 6 5 4
6 5 4 3 2 1
90 1 0 1 90 99
99 95 99 3 34 35
34 35 36 68 69 70
99 98 97 1  2 3
88 87 32 33 66 63

Code: Select all

Case 1: -9 -9 -9 0 9 9 9
Case 2: -9 -9 0 0 9 0 0
Case 3: -9 -1 2 -8 4 -4 -5
Case 4: -9 -8 6 -9 7 2 2
Case 5: -9 -9 -9 -8 9 9 9
Case 6: -9 -9 3 -2 0 6 9
Case 7: -9 -8 5 4 1 -5 5
Case 8: -9 -8 5 6 -3 4 -2
Case 9: -9 6 -4 -8 -1 8 0
Case 10: -9 -8 3 -7 7 8 4
Case 11: -9 -2 -2 2 8 -6 9
Case 12: -9 -9 0 0 9 9 0
Case 13: -4 -9 9 -2 5 8 -5
Case 14: -9 -9 0 2 3 6 -3
Case 15: -9 0 -1 0 9 7 0
Case 16: -9 -9 5 -6 3 0 8