Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2022-6e09e12f
この記事にトラックバックする(FC2ブログユーザー)

SRM504.5 DIV1 EASY/DIV2 MEDIUM - TheNumbersWithLuckyLastDigit (この記事を編集する[管理者用])

Source

TopCoder SRM504.5 DIV1 EASY (250pt)
TopCoder SRM504.5 DIV2 MEDIUM (500pt)
Problem Statement
SRM504.5 DIV1 自分の参加記録

問題概要

下1桁が4または7の正整数をラッキーな数字という.
N (1以上10^9以下) をラッキーな数字の和で書くとき,最小でいくつのラッキーな数字の和で書くことができるかを求める問題.

解法

10の倍数は自由に加えることができるので,基本的には下1桁のみで決まる.
ただし,数字が小さいうちは作れないこともある.
使う4の数や7の数は多く無いので,使う4の数,7の数で全探索する.
以下のコードは,DPで求めている.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000000

class TheNumbersWithLuckyLastDigit {
public:
int find(int n) {
  int i,j,k;
  int res = INF;
  int dp[1000];

  rep(i,1000) dp[i] = INF;
  dp[0] = 0;

  REP(i,4,1000) if(dp[i] > dp[i-4]+1) dp[i] = dp[i-4]+1;
  REP(i,7,1000) if(dp[i] > dp[i-7]+1) dp[i] = dp[i-7]+1;

  while(n>=2000) n-=1000;
  while(n>=1000) n-=10;
  while(n>0){
    if(res > dp[n]) res = dp[n];
    n -= 10;
  }
  if(res==INF) res = -1;

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2022-6e09e12f
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。