## 266 - Stamping Out Stamps

Moderator: Board moderators

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

### PE

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:

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

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

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!