問題
http://community.topcoder.com/stat?c=problem_statement&pm=11096&rd=14514
下１桁が４または７である数はラッキーナンバーとなる。
ある整数Nが与えられたとき、その数をラッキーナンバーの和で表したい。
ラッキーナンバーの数で表すことができれば必要な最小のラッキーナンバーの
数を返す。
表すことができなければー１を返す。
解き方
チャレンジされやすそうな問題。
小さい数で試してみると、２１以上の数はすべてラッキーナンバーの和で
表すことができることがわかる。
またラッキーナンバーの和で表すことができる場合、下２桁以外の数は
いくらであっても必要な数は変わらない。
よって作ることのできるすべての下３桁の数について試し、
その最小のものが答えになる。
単純に下２桁をMOD１００でとると１０２０のような場合にー１となってしまうので
２桁の数で下１桁が４と７の数を引いたときの下２桁を求めれば
すべての場合で確かめることができる。
条件分岐のIF文をできるだけ少なくすることがシステムテストで落ちないためのコツ。
コード
class TheNumbersWithLuckyLastDigit {
public: int find(int n) {
int dp[100];
FORE(i,0,100)dp[i]=1e+9;
FORE(i,1,100){
if(i%10==4||i%10==7)dp[i]=1;
for(int j=4;i+j<100;j+=10)dp[i+j]=min(dp[i+j],dp[i]+1);
for(int j=7;i+j<100;j+=10)dp[i+j]=min(dp[i+j],dp[i]+1);
}
int ret=1e+9;
ret=min(ret,dp[n%100]);
for(int i=4;i<100&&n-i>=0;i+=10)ret=min(ret,dp[(n-i)%100]+1);
for(int i=7;i<100&&n-i>=0;i+=10)ret=min(ret,dp[(n-i)%100]+1);
return ret==1e+9 ? -1 : ret;
}
};
public: int find(int n) {
int dp[100];
FORE(i,0,100)dp[i]=1e+9;
FORE(i,1,100){
if(i%10==4||i%10==7)dp[i]=1;
for(int j=4;i+j<100;j+=10)dp[i+j]=min(dp[i+j],dp[i]+1);
for(int j=7;i+j<100;j+=10)dp[i+j]=min(dp[i+j],dp[i]+1);
}
int ret=1e+9;
ret=min(ret,dp[n%100]);
for(int i=4;i<100&&n-i>=0;i+=10)ret=min(ret,dp[(n-i)%100]+1);
for(int i=7;i<100&&n-i>=0;i+=10)ret=min(ret,dp[(n-i)%100]+1);
return ret==1e+9 ? -1 : ret;
}
};
Share this
Related Posts
SRM 551 DIV1 Easy - ColorfulChocolates
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12137&rd=15173
解き方
各アルファベットごとに最大の連続数を考え、最- SRM 542 DIV1 Easy - PatrolRoute
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11934&rd=14734
解き方
３点を選んだ時、そのｘ座標の最小値と最大値の
- SRM 387 DIV1 Easy - FoxesOfTheRoundTable
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8527&rd=11121
解き方
全てのjoker boxの選び方について全探索
- SRM 670 DIV1 Easy - DoubleOrOneEasy
問題
https://community.topcoder.com/stat?c=problem_statement&pm=14059&rd=16550
解き方
文字列長がnのとき、条件を満たすLCSは必