srm 504.5 mid TheNumbersWithLuckyLastDigit

program topcoder

問題

http://www.topcoder.com/stat?c=problem_statement&pm=11096&rd=14514

  • 下1桁が 4 or 7 の正の自然数を lucky number と呼ぶ
  • 正の自然数 n を lucky number の和で表したい。この時、なるべく summand の数を少なくしたい。いくつの数が必要か？

方針

  • f(i, j) := 4i + 7j とする。
  • 「n >= f(i, j) 且つ n - f(i, j) が10の倍数」...(1)なら、n は i + j 個の lucky numberの和として書ける。
  • 逆に、 n が a 個の luchy number の和として書けるなら、i+j = a 且つ (1)の条件を満たすi, jが存在する。
  • よって、この条件を満たすような i, j で i + j が最小になるものを見つければ良い。
  • iが10以上で(1)を満たすなら、iをi-10に置き換えても(1)が満たされるはず。jについても同様。よって、i, j=0,...,9の範囲を調べれば良い。

回答

#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class TheNumbersWithLuckyLastDigit{
public:
  int find(int n){
    int ret = n;
    for(int i = 0; i < 10; i++){
      for(int j = 0; j < 10; j++){
	int x = i * 4 + j * 7;
	if(n % 10 == x % 10 && x <= n && x > 0){
	  ret = min(ret, i + j);
	}
      }
    }
    if(ret == n) ret = -1;
    return ret;
  }



};