Submission #1756097

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n - 1); i >= 0; --i)
#define mod 1000000007
#define INF 93193111451418101
#define MIN -93193111451418101
//#define INF 931931114518101
using namespace std;
typedef pair<ll, ll> P;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
  for (auto &i : arr) {
    fill_all(i, v);
  }
}
#define yo 100001
//------------------変数-----------------------//
ll d, n, m;
map<P, ll> dp;
string str[100];
//-------------------関数----------------------//
ll mintime = INF;
ll DP(ll L, ll num, ll kaisuu) {
  if (num == n) {
    mintime = min(mintime, kaisuu);
    return 0;
  }
  if ((n - num) % L) {
    return INF;
  }
  if (kaisuu >= mintime) {
    return INF;
  }
  if (dp[P(L, num)]) {
    return dp[P(L, num)];
  }
  ll cnt = INF;
  for (ll i = 36; i >= 0; i--) {
    if (to_string(L).size() + str[i].size() < 19) {
      ll izryt = L * stoll(str[i]);
      if (num + izryt <= n) {
        cnt = min(cnt, DP(izryt, num + izryt, kaisuu + 1) + 1);
      }
      if (izryt <= n && izryt != L) {
        cnt = min(cnt, DP(izryt, num, kaisuu));
      }
    }
  }
  return dp[P(L, num)] = cnt;
}

int main() {
  cin >> n;
  str[0] = '1';
  str[1].push_back('2');
  str[2].push_back('5');
  FOR(i, 3, 37) {
    auto a = stoll(str[i - 2]) % 10;
    if (a == 5) {
      str[i] = str[i - 2] + "2";
    } else {
      str[i] = str[i - 2] + "5";
    }
  }
  cout << DP(1, 0, 0) << endl;
  return 0;
}

Submission Info

Judge Result