11296 - Counting Solutions to an Integral Equation

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

11296 - Counting Solutions to an Integral Equation

Post by darkos32 » Mon Oct 01, 2007 3:45 am

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

thanks..

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Oct 01, 2007 4:03 am

Input:

Code: Select all

0
1000000
Output:

Code: Select all

1
125000750001

darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

asd

Post by darkos32 » Mon Oct 01, 2007 5:52 am

accepted now...thanks..

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

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

Post by sapnil » Mon Oct 01, 2007 6:03 am

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.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Sat Jan 19, 2008 7:56 pm

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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Jan 19, 2008 8:18 pm

Hint.

Code: Select all

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

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Sat Jan 19, 2008 11:35 pm

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

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11296 - Counting Solutions to an Integral Equation

Post by kbr_iut » Thu Jul 10, 2008 9:45 am

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

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11296 - Counting Solutions to an Integral Equation

Post by mak(cse_DU) » Mon Dec 22, 2008 9:10 am

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

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11296 - Counting Solutions to an Integral Equation

Post by kbr_iut » Sun Dec 28, 2008 8:42 pm

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

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

Re: 11296 - Counting Solutions to an Integral Equation

Post by sh415 » Mon Nov 15, 2010 12:42 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11296 - Counting Solutions to an Integral Equation

Post by brianfry713 » Mon Feb 23, 2015 10:17 pm

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 112 (11200-11299)”