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;