OJ Board

can anybody give me a case where this fails, or help me
find the bug?

I'm pretty sure my algorithm is correct. however, what's the output
for n=0 supposed to be? (i tried 0 and 1, but got WA both times. )

Thanks for any help.

long is not enough, use long long. Ofcourse u may have other mistakes

I just wonder how the program can work less than 2 seconds. My program work 29.530 seconds and get Accepted. But I have no idea how to optimaze it. Can anyone give me a hint to make a good fast program?

P.S. I use DP. My algorithm is O(n^3). May be exist a algorithm O(n^2 (log n))?

well, what i did was this.

say you want to sum to 10 with 4 coins.
you can do it this way: (1,1,1,7), (1,1,2,6),(1,2,2,5),(2,2,2,4),(2,2,3,3).
every other way is just a permutation of the above. (from the
example given in the problem i assumed we don't count permutations).
so in this case there are 5 ways to do it.

my code above simulates this by noting that if we add 1 to all the
coins except the last in turn, while subtracting 1 from the last coin each time, we've subtracted numberofcoins-1 from the last coin, and have gone
though numberofcoins-1 permutations.
The example above illustrates this.
To actually implement it, we just keep track of the last 2 coins.
we subtract numberofcoins-1 from the last and add 1 to the
second last until the
difference between the 2nd last and last coin is small
(ie, < numberofcoins -1), then we figure out how many are
actually left.

i think this is correct, but I keep getting WA.
one reply above implied that the number of ways is too large for an int. The largest number my code generates is ~40000.
Maybe somebody who got there's accepted could post some
cases with the correct output?

The code runs in 0.5 seconds.

If my algorithm is wrong, somebody please tell me now.

any input would be appreciated. I feel like i've made a really
dumb mistake...

Your algorithm seems quite correct to me, but I think there are some critical points:

In how many ways can 0$ be made up by 0 coins? 0 or 1?
In how many ways can more than 0$ be made up by 0 coins? 0 or 1?

I'm not sure (haven't solve this problem yet) but I think that broderic's algorithm is wrong. For this input:
100 10 10

Broderic's programs outputs:
82

But I think that correct output must be 2977866...

Ok.I posted some correct test cases (as I and Judge think )
InPut OutPut

hehe, well, i'm obviously wrong.
not only that, i'm apparently waaay wrong.

could anybody give me a hint as to how i should
go about this problem?

(for some reason, that 2977866 looks like a really familiar number.
I can't remember where i've seen it before though )

2Revenger: Can you recheck your output? I've got same results as yours except fourth case, my (rejected) solution outputs 2347163627458 but yours 1147203119198. I can't understand is this my bug or just your mistype?

i think Ivan Golubev is right about the '200 30 75'
input: output:

It's my mistake... sorry

Revenger wrote:I just wonder how the program can work less than 2 seconds. My program work 29.530 seconds and get Accepted. But I have no idea how to optimaze it. Can anyone give me a hint to make a good fast program?

P.S. I use DP. My algorithm is O(n^3). May be exist a algorithm O(n^2 (log n))?

If your algorithm is really O(n^3) then you must be doing something inefficiently, because 300^3 is only 27 million, which should easily run in way less than 30s if each of the 27m operations are simple enough.

But, you can solve it in O(n^2)... you only need to fill a 300x300 array, where A[j] is the # of ways of getting $i total dollars where all the coins are of value at most j.

heh, i don't know what i was thinking earlier.
the algorithm i posted above misses all sorts of possible ways...
for instance: (1,1,1,10),(1,1,2,9),(1,2,2,8),(2,2,2,7)...but this misses (1,1,3,8),(1,1,4,7),... doh!

anyway, i know how to do it now.

Sheesh, seems like i've been making a lot of mistakes like this lately. :)

Broderick

Joe, are you sure you solve it in O(n^2)? Because I thought my algorithm is O(n^3), but my program is faster than your program. Did you also sum up the values of the matrix and store them?