## 266 - Stamping Out Stamps

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### 266 - Stamping Out Stamps

Yeah I know the acceptance rate of this task is low... But...

The thing that I'm most unsure about is the output format. For this input,

Code: Select all

``````7
2 7 14 17 22 63 98
5
0
7
2 7 14 17 22 63 98
86
2999
143
0
0``````
My WA program gives:

Code: Select all

``````STAMP VALUES 2 7 14 17 22 63 98

AMOUNT 5
STAMPS USED 2 2 2

STAMP VALUES 2 7 14 17 22 63 98

AMOUNT 86
STAMPS USED 63 14 7 2

AMOUNT 2999
NO SOLUTION EXISTS

AMOUNT 143
STAMPS USED 63 63 17

``````
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Yes, that output is correct.

Since I made the testset and the accept rate is indeed very low, I would be interested in your WA solution. Could you PM it to me?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I think the low acceptance rate is because of this:
"If there's still a tie, choose the stamps as expensive as possible."
It is not clear how exactly we should choose expensive stamps. Should the stamp with the maximum value be as expensive as possible, or should the stamp with the minimum value be as expensive as possible?
So, what should be the output for:
3
5 6 7
12
0

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hmm. I see. I never thought of it otherwise than meaning your first interpretation (7 5 in your example). But now I see it can be ambiguous. What would be the right formulation?
Also for:
6
16 7 6 5 4 3
18
0
0
You should choose 7 7 4, and not 7 6 5 or 6 6 6 (or 16 3, but that is clear enough I would think).

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I never thought of it otherwise than meaning your first interpretation (7 5 in your example).
That was also my first thought. However, I got WA with that.
I guess it is sufficient to include one sample test case that shows the difference.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Well, it seems I made a stupid mistake while producing the testset. Please forgive me and don't submit until the new files are updated to the judge. Old submissions will be rejudged, of course.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Hi I guess you don't need my code anymore~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
little joey wrote:Well, it seems I made a stupid mistake while producing the testset. Please forgive me and don't submit until the new files are updated to the judge. Old submissions will be rejudged, of course.
Oh yeah~~We are making the same mistake
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Haha yeah I get Accepted now~ Thanks everyone!!!

P.S. What exactly was the flaw in the I/O?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Good for you!
Saying what the flaw was, would be too big a hint. Let's just say I payed not enough attention to detail... and implemented an algo I thought I knew well enough.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Yes, after I read the problem, I just do the following:
1. implement the dp
3. AC XD

Surely I have overlook something that is not obvious~
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Oh the rank of my submission has slipped down to 2nd...... Weep

Never mind... hope I would know how to optimize the I/O process in PASCAL.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Well.....
I haven't done optimization on IO now.....
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I keep getting WA for this, and I think I got the boundary conditions.. does anyone have a test case? Thanks.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Nevermind, I misspelled something. Thanks!