11480 - Jimmy's Balls

[wahaha]

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]

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 )

[emotional blind]

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.

Hope this idea will help you.
thanks.

[sohel]

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]

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.

Hope this idea will help you.
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]

During the contest I used an O(n lg n) solution using binary search and it ran in less than a second

[hamedv]

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

[kbr_iut]

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.

[rajib_sust]

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

you will find good soution.

[rajib_sust]

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

[Obaida]

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

Code: Select all

Thanks it's really a cool problem!

[kbr_iut]

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.

[plamplam]

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.