Page 1 of 5

10819 - Trouble of 13-Dots

Posted: Mon Feb 14, 2005 11:13 pm
by Larry
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.

Posted: Mon Feb 14, 2005 11:44 pm
by Adrian Kuegel
Try:
1801 3
901 2
901 2
200 1

Output should be 3.

More input please

Posted: Tue Feb 15, 2005 1:06 am
by erdos
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

Posted: Tue Feb 15, 2005 1:16 am
by Adrian Kuegel
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.

Posted: Tue Feb 15, 2005 3:30 am
by erdos
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

Posted: Tue Feb 15, 2005 3:40 am
by Adrian Kuegel
1900 3
2000 5
1950 1
101 1

output:
2

Posted: Tue Feb 15, 2005 10:50 am
by liulike
Some more testdata plz?
I still got WA..

Here is my code:

Code: Select all

AC now:)

Posted: Tue Feb 15, 2005 12:47 pm
by erdos
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 ?

Posted: Tue Feb 15, 2005 1:21 pm
by ..
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.

Posted: Tue Feb 15, 2005 1:29 pm
by erdos
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

Posted: Tue Feb 15, 2005 1:59 pm
by Observer
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.'.... :P

(You may simply ignore this comment! :wink: )

Posted: Tue Feb 15, 2005 2:03 pm
by Larry
Thanks Adrian for:

Code: Select all

1900 3 
2000 5 
1950 1 
101 1
That was my problem!

Posted: Wed Feb 16, 2005 5:20 am
by technobug
i got 9 wa :) before ac during the contest

Posted: Fri Feb 18, 2005 3:38 am
by erdos
I think I've fixed thar bug but I still get WA :oops:
Can someone post more problematic input, please ?

Regards,

Jose Santos

10819 - Trouble of 13-Dots

Posted: Wed Mar 02, 2005 7:47 am
by salamander
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?

:cry: