Solution for https://pcs.cs.cloud.vt.edu/problems/277 (Canonical Coin System)

coin.cpp

// 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;
}