10819 - Trouble of 13-Dots

Larry · Post by **Larry** » Mon Feb 14, 2005 11:13 pm

I've submitted a few times, with a few variation, but all WA..

It seems like a trivial 0-1 Knapsack.. are there any tricks?

I tried both >= 2000 and > 2000.. is there any cases in which we can't take advantage of the 200$ rebate other than not being able to afford it? Thanks.

Adrian Kuegel · Post by **Adrian Kuegel** » Mon Feb 14, 2005 11:44 pm

Try:
1801 3
901 2
901 2
200 1

Output should be 3.

erdos · Post by **erdos** » Tue Feb 15, 2005 1:06 am

Hi,

Could you please post more sample input with output ?
I had a WA and my solutions give correct output for some examples I created.
With the question of the bonus..
Is there any problem doing this

if(m>2000)
m+=BONUS;

(It's > and not >=, right?)

Regards,

Jose Santos

Adrian Kuegel · Post by **Adrian Kuegel** » Tue Feb 15, 2005 1:16 am

Ok, here a test case where you fail:
1801 1
2001 1

output: 1

I guess you didn't understand the problem right. Since she uses a credit card, she doesn't have to own all the money she spends, so she can spend 2001 even when she has only 1801, since after the month she gets the 200 dollar refund.

erdos · Post by **erdos** » Tue Feb 15, 2005 3:30 am

You are right!
I don't know why I didn't remember that :-|

Anyway, my submission still received WA

So, I must have other problems...
Can you give more input, please ?

Regards,

Jose Santos

Adrian Kuegel · Post by **Adrian Kuegel** » Tue Feb 15, 2005 3:40 am

1900 3
2000 5
1950 1
101 1

output:
2

liulike · Post by **liulike** » Tue Feb 15, 2005 10:50 am

Some more testdata plz?
I still got WA..

Here is my code:

Code: Select all

AC now:)

erdos · Post by **erdos** » Tue Feb 15, 2005 12:47 pm

Hi,

1900 3
2000 5
1950 1
101 1

output:
2

Why is output 2 in this case and not 5 ?
If she has 1900 she can spend up to 2100.
(since it's a credit card she can spend more than she has and at the end of the month she'll get the 200$ refund).
What's the catch ?

.. · Post by .. » Tue Feb 15, 2005 1:21 pm

1900 3
2000 5
1950 1
101 1

In this case, if she buy "2000 5", the total will NOT exceed 2000,
not possible to get 200 refund.

erdos · Post by **erdos** » Tue Feb 15, 2005 1:29 pm

You are right...
I didn't consider that case because in reality it wouldn't make much sense. (I would certainly find a way to spend 1 dollar to get extra 200).

But it makes sense for the problem and I'll have to revise my source code.

Thanks:-)

Jose Santos

Observer · Post by **Observer** » Tue Feb 15, 2005 1:59 pm

erdos wrote:I didn't consider that case because in reality it wouldn't make much sense. (I would certainly find a way to spend 1 dollar to get extra 200).

Are you sure you can always make a $1 transaction using a credit card? Imagine that you say to the shopkeeper of a boutique (say Dior), 'Please, get me something that cost exactly 1 dollar.'....

(You may simply ignore this comment!

)

Larry · Post by **Larry** » Tue Feb 15, 2005 2:03 pm

Thanks Adrian for:

Code: Select all

That was my problem!

technobug · Post by **technobug** » Wed Feb 16, 2005 5:20 am

i got 9 wa

before ac during the contest

erdos · Post by **erdos** » Fri Feb 18, 2005 3:38 am

I think I've fixed thar bug but I still get WA

Can someone post more problematic input, please ?

Regards,

Jose Santos

salamander · Post by **salamander** » Wed Mar 02, 2005 7:47 am

Should I sort the "price of the item" OR "favour index"?

But I think that those of them is not work....

How could do it?

OJ Board