Skip to content

Instantly share code, notes, and snippets.

@eopXD
Last active Sep 21, 2020
Embed
What would you like to do?
Solution for https://pcs.cs.cloud.vt.edu/problems/277 (Canonical Coin System)
// see https://eopxd.com/2020/09/15/canonical-coin-system/ for some explaination
#include <cstdio>
#include <vector>
#define N 1000006
using namespace std;
int dp[2*N];
vector<int> coin;
int G ( int x ) {
int ret = 0;
for ( auto it=coin.rbegin(); it!= coin.rend(); ++it ) {
if ( x == 0 ) {
break;
}
ret += x / *it;
x %= *it;
}
return ret;
}
int main ()
{
int n;
scanf("%d", &n);
for ( int i=0; i<n; ++i ) {
int x;
scanf("%d", &x);
coin.push_back(x);
}
for ( int i=0; i<2*N; ++i ) {
dp[i] = i;
}
for ( auto &c: coin ) {
for ( int i=c; i<2*N; ++i ) {
dp[i] = min(dp[i], dp[i-c]+1);
}
}
bool canonical = true;
for ( int i=0; i<2*N; ++i ) {
if ( dp[i] != G(i) ) {
canonical = false;
}
}
printf("%s\n", canonical ? "canonical" : "non-canonical");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment