242 - Stamps and Envelope Size

[titid_gede]

are there any critical inputs or tricky input for this problem? i always got WA

[titid_gede]

got accepted finally. there is small mistake in my code.

[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...

[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?
-------------------------------------------------------------------

Code: Select all

[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

Output:

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.

[mistycheney]

Thanks Jan~~I found the mistake in my code using your test cases~~

[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

[porker2008]

Thanks to the God.

I get AC now!!!

[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");

[frank44]

Could someone with an AC answer my previous post? The problem is really vague when it comes to output...

[frank44]

omg stupid spambots are everywhere... is this forum officially dead? Are there any moderators left active?

[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");