問題
http://community.topcoder.com/stat?c=problem_statement&pm=12436&rd=15491
1~Nまでの数字が付けられたN.mp3ファイルを昇順に並べる。
Nが50を超える場合は、最初の50個の昇順に並べられたファイル数を返す。
解き方
Nが10^9のため全てのファイルを出力してからソートしては求めることができない。
そのため規則性を見つける必要がある。
N=1018のとき、
最初は1から始め,
10,100,1000と「10をかけ、N以下ならその数」になる。
次は1001、1002、1009、101と「1を足していき、10で割ってN以下ならその数」となる。
また、1010、、、1018、102とNを超えた場合は「10で割って1を足し、N以下ならその数」になる。
最後に、191、、199、2、と10で割りつづけられるなら割り続ける必要がある。
つまり、
①10をかけ、N以下ならその数
②Nより大きい場合、1を足して10の倍数もしくはNと等しいなら、10で割れなくなるまで割り続けた数に1を足した数なる。
これをmin(N,50)まで操作してあげたものが答えになる。
コード
class FoxAndMp3 {
public: vector<string> playList(int n) {
long long cur=1,num=1;
vector<string> ans(min(n,50));
FORE(num,0,min(50,n)){
stringstream out;
out<<cur<<".mp3";
ans[num]=out.str();
if(cur*10<=n)cur*=10;
else{
while(cur%10==9 || cur==n)cur/=10;
cur++;
}
}
return ans;
}
};
public: vector<string> playList(int n) {
long long cur=1,num=1;
vector<string> ans(min(n,50));
FORE(num,0,min(50,n)){
stringstream out;
out<<cur<<".mp3";
ans[num]=out.str();
if(cur*10<=n)cur*=10;
else{
while(cur%10==9 || cur==n)cur/=10;
cur++;
}
}
return ans;
}
};