Page 1 of 1
242 - Stamps and Envelope Size
Posted: Tue Apr 22, 2003 4:56 pm
by titid_gede
are there any critical inputs or tricky input for this problem? i always got WA
Posted: Sat Apr 26, 2003 4:25 pm
by titid_gede
got accepted finally. there is small mistake in my code.
242 - WA
Posted: Wed Apr 19, 2006 11:31 pm
by eduardojmc
I dont know whats wrong wiht my problem: here's the input i tested:
5
1
2 1 3
5
2
4 1 4 12 21
4 1 5 12 28
10
2
5 1 7 16 31 88
5 1 15 52 67 99
6
2
3 1 5 8
4 1 5 7 8
0
my output:
max coverage = 13 : 1 3
max coverage = 71 : 1 4 12 21
max coverage = 409 : 1 7 16 31 88
max coverage = 48 : 1 5 7 8
Is there anything on the problem i missed? im using DP for counting the minimun number of coins for each value, given a stamp set:
static int solve(int[] stamps, int maxStamps) {
int[] stampsNeeded = new int[(stamps[stamps.length-1]*maxStamps )+1];
for (int i = 1; i < stampsNeeded.length; i++) {
stampsNeeded = Integer.MAX_VALUE;
}
stampsNeeded[0] = 0;
for (int i = 0; i < stamps.length; i++) {
for (int j = stamps; j <= stamps*maxStamps; j++) {
stampsNeeded[j] = Math.min( stampsNeeded[j], stampsNeeded[j-stamps] + 1);
}
}
int cover = findMaxCover(stampsNeeded, maxStamps);
return cover;
}
//*******************
than i find the maximum gap by:
static int findMaxCover(int[] numStampsNeeded, int k) {
int cover = 0;
for (int i = 1; i < numStampsNeeded.length; i++) {
if( numStampsNeeded > k ){
break;
}
cover = i;
}
return cover;
}
//********************
than i print the max gap with max set... I know this may be slow, but i can't see the mistake, and I am getting WA...
Posted: Tue Oct 09, 2007 5:52 pm
by mistycheney
can't see why I keeps getting WA on 242~ I think I've tried every possible tricky input~~
is that the problem of output format? actually I have aligned them as the sample output~~
Now where the error is gonna be?
-------------------------------------------------------------------
Posted: Wed Oct 10, 2007 1:16 am
by Jan
Try the cases...
Input:
Code: Select all
3
2
10 3 21 24 32 49 54 70 75 79 83
10 4 5 9 14 20 46 72 82 86 93
3
2
10 1 6 40 54 64 77 82 88 91 94
10 1 22 23 27 40 69 84 94 96 99
0
Code: Select all
max coverage = 0 : 3 21 24 32 49 54 70 75 79 83
max coverage = 3 : 1 6 40 54 64 77 82 88 91 94
Hope these help.
Posted: Fri Oct 12, 2007 7:27 am
by mistycheney
Thanks Jan~~I found the mistake in my code using your test cases~~
Re: 242 - WA
Posted: Wed Oct 08, 2008 8:58 pm
by porker2008
I also get WA. I don't know what's wrong with my program.
The case given above I give the correct answer.
So can somebody give me more cases so that I can check my codes.
By the way, if the value of one stamp reach 100, so what is the out put format?
Should it be like this?
max coverage = ** : 1 ** ** ** ** 88100
or
max coverage = ** : 1 ** ** ** ** 88 100
Re: 242 - WA
Posted: Thu Oct 09, 2008 7:18 am
by porker2008
Thanks to the God.
I get AC now!!!
242 - Stamps and Envelope Size (PE)
Posted: Thu Dec 31, 2009 6:29 pm
by frank44
Hello, I feel like this problem isn't really clear on the output specifications, could someone point me in the right direction I keep getting PE?
Here is the sample output:
Code: Select all
max coverage = 71 : 1 4 12 21
max coverage = 409 : 1 7 16 31 88
max coverage = 48 : 1 5 7 8
Here is how I print my output:
Code: Select all
printf("max coverage = %3d :", max_cover);
for (int i=0; i<best.size(); i++)
if (best[i]!=100) printf("%3d", best[i]);
else printf(" 100");
printf("\n");
Re: 242 - Stamps and Envelope Size (PE)
Posted: Sat Jan 02, 2010 3:53 am
by frank44
Could someone with an AC answer my previous post? The problem is really vague when it comes to output...
Re: 242 - Stamps and Envelope Size (PE)
Posted: Fri Jan 15, 2010 11:28 am
by frank44
omg stupid spambots are everywhere... is this forum officially dead? Are there any moderators left active?
Re: 242 - Stamps and Envelope Size (PE)
Posted: Wed Oct 24, 2012 11:27 am
by TPuser
I got AC by
Code: Select all
printf("max coverage =%4d :",max);
for(i=0;i<stamp[ans].n;i++){
printf("%3d",stamp[ans].price[i]);
}
printf("\n");