266 - Stamping Out Stamps

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

Moderator: Board moderators

eduardojmc
New poster
Posts: 3
Joined: Wed Apr 19, 2006 11:20 pm

PE

Post by eduardojmc » Thu Apr 20, 2006 8:04 am

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Re: 266 please help~

Post by Dominik Michniewski » Thu Apr 21, 2011 2:14 pm

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 ??
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 266 - Stamping Out Stamps

Post by Repon kumar Roy » Sun Dec 28, 2014 4:24 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 266 - Stamping Out Stamps

Post by brianfry713 » Wed Jan 07, 2015 3:30 am

So the last line of stamp values in the output is followed by one blank line
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 2 (200-299)”