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..
darkos32
New poster

Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia

Input:
Code: Select all
`01000000`

Output:
Code: Select all
`1125000750001`
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm

asd

accepted now...thanks..

im so stupid..it's very easy problems..
darkos32
New poster

Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia

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.
sapnil
Experienced poster

Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST

I can't see how to solve this problem.

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

andmej
Experienced poster

Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Hint.
Code: Select all
`x+2*y+2*z = x+2*(y+z)`

-----
Rio

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Thanks Rio.

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

andmej
Experienced poster

Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

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.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

kbr_iut
Experienced poster

Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm

Re: 11296 - Counting Solutions to an Integral Equation

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.
Mak
Help me PLZ!!
mak(cse_DU)
Learning poster

Posts: 72
Joined: Tue May 30, 2006 5:57 pm

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...............................

kbr_iut
Experienced poster

Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm

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;
sh415
New poster

Posts: 13
Joined: Fri Nov 13, 2009 9:31 am
Location: JU