SRM504.5 Div1 Easy

250

下1桁だけに注目すればいい。
与えられた数と同じ下1桁を持つ数を4と7から作る。

class TheNumbersWithLuckyLastDigit {
public:
  int find(int m)
  {
    const int inf = 1 << 25;
    const int N = 10;
    pair<int, int> n[N];
    fill(n, n + 10, make_pair(inf, inf));
    n[4] = make_pair(1, 4);
    n[7] = make_pair(1, 7);

    for (int loop = 100; loop--; ) {
      for (int i = 0; i < (int)N; ++i) {
        pair<int, int> p;
        int j;

        j = (i + 4) % N;
        p = make_pair(n[i].first + 1, n[i].second + 4);
        n[j] = min(n[j], p);       

        j = (i + 7) % N;
        p = make_pair(n[i].first + 1, n[i].second + 7);
        n[j] = min(n[j], p);       
      }
    }   
   
    int x = m % 10;
    if (m < n[x].second) return -1;
    return n[x].first;
  }
};