266 - Stamping Out Stamps

[eduardojmc]

Im getting lots of PE ... someone accepted, plz, run this input and post the output, or give me a hint why my presentation presentation is not correct...

input:
7
2 7 14 17 22 63 98
72
86
143
5
0
6
16 7 6 5 4 3
18
0
3
5 6 7
12
0
6
16 7 6 5 4 3
18
0
0

my output:
STAMP VALUES 2 7 14 17 22 63 98

AMOUNT 72
STAMPS USED 63 7 2

AMOUNT 86
STAMPS USED 63 14 7 2

AMOUNT 143
STAMPS USED 63 63 17

AMOUNT 5
STAMPS USED 2 2 2

STAMP VALUES 3 4 5 6 7 16

AMOUNT 18
STAMPS USED 7 7 4

STAMP VALUES 5 6 7

AMOUNT 12
STAMPS USED 7 5

STAMP VALUES 3 4 5 6 7 16

AMOUNT 18
STAMPS USED 7 7 4

#end

Have tried lots of things, but got no luck =[

[Dominik Michniewski]

Hmm, I got the same output as you

But I got WA anyway ... so I don't know if your output is correct

Could anyone help me with this problem ??

I use following algorithm (DP):
for each stamp value (starting from highest value) I search for:
1. stamp with exact value => end
2. check every possibility such that value = i-th stamp value + DP(value minus i-th stamp value)
2.1. if length of sequence is less than previously found - update sequence with new one
2.2. if length of sequence is equal to current one - check if new one contains bigger values of stamps and if it contains, update sequence

It's kind of greedy algorithm I think. Could anyone post counterexample on which my algorithm fails ??

[Repon kumar Roy]

Getting WA's

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
#include <sstream>
#include <climits>
#include <list>
#include <string>
using namespace std;

/*------- Constants---- */
#define MX                      3005
#define ll                      long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define FOR(i,n)                for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define inf                     1<<30
/* -------Global Variables ------ */
ll euclid_x,euclid_y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
template <class T> inline T bigmod(T p,T e,T M){
        ll ret = 1;
        for(; e > 0; e >>= 1){
                if(e & 1) ret = (ret * p) % M;
                p = (p * p) % M;
        } return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

vector<int> coinval;

ii dp[MX];

int cmp ( int *a , int *b)
{
        if( *a > *b ) return -1;
        return 1;
}
int main()
{
        
        int N , q , ff = 0 ,a ;
        
        while (cin >> N  && N ) {
                
                for (int i = 0; i < N; i ++ ) {
                        cin >> a;
                        coinval.push_back(a);
                }
                if(ff )printf("\n");
                ff = 1;
                
                sort(coinval.begin(), coinval.end() );
                reverse(coinval.begin(), coinval.end());
                
                printf("STAMP VALUES");
                for( int i = N - 1 ; i >=0 ; i -- )
                {
                        printf(" %d",coinval[i]);
                }
                printf("\n");
                dp[0].first  = 0;
                
                for (int i  = 1; i < MX ; i ++ ) {
                        int t = MEM_VAL;
                        for (int j = 0; j < N ; j ++ ) {
                                int tmp = 10000000;
                                if(coinval[j] <=i ) tmp = dp[max(i - coinval[j] , 0 )].first  +1;
                                if( tmp < t) {
                                        t = tmp;
                                        dp[i].first = t;
                                        dp[i].second = coinval[j];
                                }
                        }
                }
                
                while (cin >> q && q ) {
                        printf("\n");
                        printf("AMOUNT %d\n",q);
                        
                        for( ; q  < MX ; q ++){
                                if( dp[q].first <=10 ) break;
                        }
                        vector<int> tmp;
                        while (q!=0 && q <3000 ) {
                                tmp.push_back(dp[q].second);
                                //printf(" %d",dp[q].second);
                                q = q - dp[q].second;
                        }
                        if( tmp.size() <=10 && tmp.size() > 0){
                                printf("STAMPS USED");
                                for (int i= 0; i < tmp.size(); i ++ ) {
                                        printf(" %d",tmp[i]);
                                }
                        }
                        else {
                                printf("NO SOLUTION EXISTS");
                        }
                        printf("\n");
                        
                }
                ms(dp, 0);
                coinval.clear();
                
        }
        return 0;
        
}

[brianfry713]

So the last line of stamp values in the output is followed by one blank line