10819 - Trouble of 13-Dots

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

10819 - Trouble of 13-Dots

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

More input please

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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

1900 3
2000 5
1950 1
101 1

output:
2

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

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:)
Last edited by liulike on Tue Feb 15, 2005 2:55 pm, edited 1 time in total.

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

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 ?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

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.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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.'.... :P

(You may simply ignore this comment! :wink: )
Last edited by Observer on Tue Feb 15, 2005 2:21 pm, edited 2 times in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

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

Thanks Adrian for:

Code: Select all

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

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

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

i got 9 wa :) before ac during the contest

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

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

I think I've fixed thar bug but I still get WA :oops:
Can someone post more problematic input, please ?

Regards,

Jose Santos

salamander
New poster
Posts: 9
Joined: Fri Jan 21, 2005 6:46 pm

10819 - Trouble of 13-Dots

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?

:cry:

Post Reply

Return to “Volume 108 (10800-10899)”