SRM 504.5 easy TheNumbersWithLuckyLastDigit

topcoder

問題概要

4と7で終わる数字はラッキーナンバー。
数字nが与えられた時、nをラッキーナンバー何個の和で表すことができるか。
できないなら-1, できるなら最小何個の和で表すことができるか。
n <=1,000,000,000

解法

n <=1,000,000,000だから、事前にすべて求めるのは無理。

ここで、あるnに対してn-10がラッキーナンバーの和で表せるとき、n-10のときの
最小の和を構成するラッキーナンバーの数がnのときも最小であるならば、
n-10を構成する組み合わせ存在するとき、nに対して、すべての答えが下一桁さえみればよいことになる。

n-10のときの組み合わせの数が、nのとき最小でないとする。

つまり、n-10は表現できないのに、nは表現できる組み合わせが存在すると仮定し、
かつ、その組み合わせより多い要素の数でn-10が表現できると仮定する。
このとき、nを構成する組み合わせの要素が10以上のとき、その要素を10引けばn-10を表現できるので、nを構成する要素はすべて10以下。
よって4と7の組み合わせだけでnを表現しなければならない。
7を2回使うと4を一回で表現できるため、7は2回以上使う意味がない。
4も同じ理由から6回以上使う意味がない。
その場合、とりうるnは、
4, 8, 12, 16, 20,
11, 15, 19, 23, 27
である。
n-10は
-6, -2, 2, 6, 10,
1, 5, 9, 13, 17
しかない。
しかし、n-10を表せる組み合わせがあるという仮定と矛盾。
よって、n-10の組み合わせが存在するときその最小の組み合わせの数が、
nでも答えとなる。
各下一桁について、表現できる最小の値をもとめ、その値を表現する最小の組み合わせの要素の数を求めればよい。

ソース

const int mini[] ={20, 11, 12, 23, 4, 15, 16, 7, 8, 19};
const int num[] = {5, 2, 3, 5, 1, 3, 4, 1, 2, 4};
class TheNumbersWithLuckyLastDigit {
public:
  int find(int n) {
    int last = n%10;
    if(mini[last] > n)return -1;
    else return num[last];
  }
};