11296 - Counting Solutions to an Integral Equation

[darkos32]

I got WA with my code...can anyone give me some testcase please ?

thanks..

[sclo]

Input:

Code: Select all

0
1000000

Output:

Code: Select all

1
125000750001

[darkos32]

accepted now...thanks..

im so stupid..it's very easy problems..

[sapnil]

Input:

1000
25
16
15
64
35
12

Output of my acc code:

125751
91
45
36
561
171
28

thanks
keep posting
sapnil cse sust.

[andmej]

I can't see how to solve this problem.

Any hint?

[rio]

Hint.

Code: Select all

x+2*y+2*z = x+2*(y+z)

-----
Rio

[andmej]

Thanks Rio.

Your hint was very useful to me. I've solved the problem.

[kbr_iut]

my group partner discovered the solution.the solution will be n=n/2+1 and then the sum from 1 up to n,,,,,n*(n+1)/2
he simulated some test cases generated by "diophantine equation ".....and produce this.
but actually i dont understand.and the time limit for this problem is 6 sec!!!!!!!!.can anyone help me explaining how it comes.
Thanx in advance

[mak(cse_DU)]

x+2y+2z=n.

Lets simplify this equation.
2*(y+z)=n-x

We can realized that:
The value of right side of equation will be 0 to n.
// let n-x=k;
=> 2*(y+z)=k..........//k is 0 to n.
=> y+z=k/2.
Ok..........
calculate how many number from 0 to n are divisible by 2.
That means how many number are valid in right side.
that is n/2+1.
Now again in equation.
y+z=s...........//Value of s is 0 to n/2+1
now how many solution of that equation.
That is s*(s+1)/2.

[kbr_iut]

thanx mak(cse_DU) for ur explanation.

[sh415]

if u just precalculate for 1st few n such as for 2:
2 0 0 | 0 1 0 | 0 0 1 so total solution 3
for :3 1 1 0 |1 0 1 | 3 0 0 so total solution 3
its 4 : 2 1 0 | 2 0 1 | 0 1 1 | 4 0 0 | 0 2 0 | 0 0 2 | total is 6
for 5 :
for every x there will be x+1; and total is also 6

so solution is simple :
cut half of n and then sum up 1 to n/2+1;

[brianfry713]

A technique useful for solving problems like this is to write a brute force solver O(n * n) and look for a pattern for small n.

Code: Select all

x = 0, y = 0, z = 0
n = 0 has 1 solution(s)
x = 1, y = 0, z = 0
n = 1 has 1 solution(s)
x = 0, y = 0, z = 1
x = 0, y = 1, z = 0
x = 2, y = 0, z = 0
n = 2 has 3 solution(s)
x = 1, y = 0, z = 1
x = 1, y = 1, z = 0
x = 3, y = 0, z = 0
n = 3 has 3 solution(s)
x = 0, y = 0, z = 2
x = 0, y = 1, z = 1
x = 0, y = 2, z = 0
x = 2, y = 0, z = 1
x = 2, y = 1, z = 0
x = 4, y = 0, z = 0
n = 4 has 6 solution(s)
x = 1, y = 0, z = 2
x = 1, y = 1, z = 1
x = 1, y = 2, z = 0
x = 3, y = 0, z = 1
x = 3, y = 1, z = 0
x = 5, y = 0, z = 0
n = 5 has 6 solution(s)
x = 0, y = 0, z = 3
x = 0, y = 1, z = 2
x = 0, y = 2, z = 1
x = 0, y = 3, z = 0
x = 2, y = 0, z = 2
x = 2, y = 1, z = 1
x = 2, y = 2, z = 0
x = 4, y = 0, z = 1
x = 4, y = 1, z = 0
x = 6, y = 0, z = 0
n = 6 has 10 solution(s)
x = 1, y = 0, z = 3
x = 1, y = 1, z = 2
x = 1, y = 2, z = 1
x = 1, y = 3, z = 0
x = 3, y = 0, z = 2
x = 3, y = 1, z = 1
x = 3, y = 2, z = 0
x = 5, y = 0, z = 1
x = 5, y = 1, z = 0
x = 7, y = 0, z = 0
n = 7 has 10 solution(s)
x = 0, y = 0, z = 4
x = 0, y = 1, z = 3
x = 0, y = 2, z = 2
x = 0, y = 3, z = 1
x = 0, y = 4, z = 0
x = 2, y = 0, z = 3
x = 2, y = 1, z = 2
x = 2, y = 2, z = 1
x = 2, y = 3, z = 0
x = 4, y = 0, z = 2
x = 4, y = 1, z = 1
x = 4, y = 2, z = 0
x = 6, y = 0, z = 1
x = 6, y = 1, z = 0
x = 8, y = 0, z = 0
n = 8 has 15 solution(s)
x = 1, y = 0, z = 4
x = 1, y = 1, z = 3
x = 1, y = 2, z = 2
x = 1, y = 3, z = 1
x = 1, y = 4, z = 0
x = 3, y = 0, z = 3
x = 3, y = 1, z = 2
x = 3, y = 2, z = 1
x = 3, y = 3, z = 0
x = 5, y = 0, z = 2
x = 5, y = 1, z = 1
x = 5, y = 2, z = 0
x = 7, y = 0, z = 1
x = 7, y = 1, z = 0
x = 9, y = 0, z = 0
n = 9 has 15 solution(s)
x = 0, y = 0, z = 5
x = 0, y = 1, z = 4
x = 0, y = 2, z = 3
x = 0, y = 3, z = 2
x = 0, y = 4, z = 1
x = 0, y = 5, z = 0
x = 2, y = 0, z = 4
x = 2, y = 1, z = 3
x = 2, y = 2, z = 2
x = 2, y = 3, z = 1
x = 2, y = 4, z = 0
x = 4, y = 0, z = 3
x = 4, y = 1, z = 2
x = 4, y = 2, z = 1
x = 4, y = 3, z = 0
x = 6, y = 0, z = 2
x = 6, y = 1, z = 1
x = 6, y = 2, z = 0
x = 8, y = 0, z = 1
x = 8, y = 1, z = 0
x = 10, y = 0, z = 0
n = 10 has 21 solution(s)

This would probably TLE on the judge, but you can find the pattern and using 64 bit integers print (n / 2 + 1) * (n / 2 + 2) / 2.