UVa1189

UVa1189

メモ化する
memo[ 余り ][ 長さ ]

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <sstream>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;

using namespace std;

const int N = 200 + 1;
const int LEN = 100 + 5;

int memo[N][LEN];
int path[N][LEN];

int rec(int rem, int len, int N)
{
  int &ret = memo[rem][len];
  if (ret != -1) return ret;
  if (len && rem == 0) return ret = 1;
  if (100 <= len) return ret = -2;

  int n;

  n = rem * 10 + 1;
  if (0 <= rec(n % N, len + 1, N)) {
    path[rem][len] = n % N;
    return ret = 1;
  }

  n = rem * 10 + 0;
  if (len && 0 <= rec(n % N, len + 1, N)) {
    path[rem][len] = n % N;
    return ret = 0;
  }

  return ret = -2;
}

int main(int argc, char *argv[])
{
  int n;
  while (cin >> n && n) {
    fill(&memo[0][0], &memo[N - 1][LEN], -1);
    fill(&path[0][0], &path[N - 1][LEN], -1);
    rec(0, 0, n);

    int m = 0;
    for (int i = 0; path[m][i] != -1; ++i) {
      cout << memo[m][i];
      m = path[m][i];
    }
    cout << endl;
  }
  return 0;
}