11296  Counting Solutions to an Integral Equation
Moderator: Board moderators
11296  Counting Solutions to an Integral Equation
I got WA with my code...can anyone give me some testcase please ?
thanks..
thanks..
Input:
Output:
Code: Select all
0
1000000
Code: Select all
1
125000750001
asd
accepted now...thanks..
im so stupid..it's very easy problems..
im so stupid..it's very easy problems..
I can't see how to solve this problem.
Any hint?
Any hint?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
Hint.

Rio
Code: Select all
x+2*y+2*z = x+2*(y+z)
Rio
Thanks Rio.
Your hint was very useful to me. I've solved the problem.
Your hint was very useful to me. I've solved the problem.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com

 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, DHAKA, BANGLADESH
 Contact:
Re: 11296  Counting Solutions to an Integral Equation
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
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
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
It is more tough to become a good person.
I am trying both...............................

 Learning poster
 Posts: 72
 Joined: Tue May 30, 2006 5:57 pm
 Location: bangladesh
Re: 11296  Counting Solutions to an Integral Equation
x+2y+2z=n.
Lets simplify this equation.
2*(y+z)=nx
We can realized that:
The value of right side of equation will be 0 to n.
// let nx=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.
Lets simplify this equation.
2*(y+z)=nx
We can realized that:
The value of right side of equation will be 0 to n.
// let nx=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.
Mak
Help me PLZ!!
Help me PLZ!!

 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, DHAKA, BANGLADESH
 Contact:
Re: 11296  Counting Solutions to an Integral Equation
thanx mak(cse_DU) for ur explanation.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
It is more tough to become a good person.
I am trying both...............................
Re: 11296  Counting Solutions to an Integral Equation
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;
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;

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11296  Counting Solutions to an Integral Equation
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.
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.
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)
Check input and AC output for thousands of problems on uDebug!