## 11480 - Jimmy's Balls

Moderator: Board moderators

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

### 11480 - Jimmy's Balls

can somebody tell me how to solve this problem?

i think it is a Combinatorics problem, what we want to solve is there are how many a,b,c such that a+b+c=n and a<b<c.

but it is out of my ability.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### Re: 11480 - Jimmy's Balls

I think you can run a brute force method to find the valu
and you can find the formular f[n] = f[n-1] ... (just think yourself )
electron

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

### Re: 11480 - Jimmy's Balls

wahaha,
There is O(1) solution. If it is hard for you, then you can try O(n) solution.

Just iterate over number of red balls, for k red balls, try to find out kmax, and kmin,
here kmax = maximum number of blue ball you can have when number of red ball is k
and kmin = minimum number of blue ball you can have when number of red ball is k

then just add kmax-kmin, for every k.

thanks.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11480 - Jimmy's Balls

f74956227 wrote:you can find the formular f[n] = f[n-1] ... (just think yourself )
Are you saying there is a recurrence relation? Could you please explain that?

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

### Re: 11480 - Jimmy's Balls

emotional blind wrote:wahaha,
There is O(1) solution. If it is hard for you, then you can try O(n) solution.

Just iterate over number of red balls, for k red balls, try to find out kmax, and kmin,
here kmax = maximum number of blue ball you can have when number of red ball is k
and kmin = minimum number of blue ball you can have when number of red ball is k

then just add kmax-kmin, for every k.

thanks.

thx a lot , i got AC .

what i think before is doubt that O(n) will get tle, and i didn't write it.
it seems that there are too little test cases.

i want to know the O(1) solution.

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

### Re: 11480 - Jimmy's Balls

During the contest I used an O(n lg n) solution using binary search and it ran in less than a second
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

### Re: 11480 - Jimmy's Balls

i think the answer for n is round((n-3)^2/12)
if it's spoiler tell me to delete it?

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 11480 - Jimmy's Balls

hamedv wrote
i think the answer for n is round((n-3)^2/12)
if it's spoiler tell me to delete it?
i dont think ur method could work.I just wrote and saw the output is simply different when n=100,,I didnt check for other values.
wahaha wrote
i want to know the O(1) solution.
I looked deeply and finally got the O(1) solution. its easy.if u look over the sample input and output u can urself find it.
here it is.
let p=n/6; //n is the number of balls
m=n%6
if(!m)num=((sum of 1 to p-1)*6+1)
else num==((sum of 1 to p-1)*6+1)+(m-1)*p+(p-1)//if m>0
and now num is the number of combination.
I got AC by this method.Its cool.
Last edited by kbr_iut on Thu Aug 14, 2008 7:27 pm, edited 3 times in total.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

rajib_sust
New poster
Posts: 16
Joined: Sun Mar 02, 2008 10:34 am

### Re: 11480 - Jimmy's Balls

you can apply brute force process. just see the figure think about loop.
than try to understand the process

you will find good soution.

life is beautiful like coding

rajib_sust
New poster
Posts: 16
Joined: Sun Mar 02, 2008 10:34 am

### Re: 11480 - Jimmy's Balls

wahaha wrote:can somebody tell me how to solve this problem?

i think it is a Combinatorics problem, what we want to solve is there are how many a,b,c such that a+b+c=n and a<b<c.

but it is out of my ability.

u can solve it using looping. if u using 2 loop it will take TLE
so i us one loop and reduce other in equational form
it more efficient and run time near 0.010

Rajib , sust
life is beautiful like coding

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 11480 - Jimmy's Balls

Why why why????????
m wa!!!!

Code: Select all

``Thanks it's really a cool problem!``
Last edited by Obaida on Sun Dec 21, 2008 7:14 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 11480 - Jimmy's Balls

the output for n=1000010 is

Code: Select all

``````Case 1: 83334500004
``````
which cant be covered within the range of long
try to use long long.
surely u will get AC.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 11480 - Jimmy's Balls

by kbr_iut » Thu Aug 14, 2008 10:15 am
hamedv wrote
i think the answer for n is round((n-3)^2/12)
if it's spoiler tell me to delete it?
i dont think ur method could work.I just wrote and saw the output is simply different when n=100,,I didnt check for other values.
Well...that actually works...@kbr_iut if your output is different when n = 100, then you must be mistaken and not him.
But I agree this was really a super cool fun problem.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson