Page 2 of 2
PE
Posted: Thu Apr 20, 2006 8:04 am
by 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 =[
Re: 266 please help~
Posted: Thu Apr 21, 2011 2:14 pm
by 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 ??
Re: 266 - Stamping Out Stamps
Posted: Sun Dec 28, 2014 4:24 pm
by 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;
}
Re: 266 - Stamping Out Stamps
Posted: Wed Jan 07, 2015 3:30 am
by brianfry713
So the last line of stamp values in the output is followed by one blank line