OJ Board

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.

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 )

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.

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?

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.

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.

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

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

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.

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

you will find good soution.

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

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

the output for n=1000010 is which cant be covered within the range of long
try to use long long.
surely u will get AC.

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.