SRM 571 DIV1 Easy - FoxAndMp3

SRM 571 DIV1 Easy - FoxAndMp3

8:21

問題


http://community.topcoder.com/stat?c=problem_statement&pm=12436&rd=15491

１～Ｎまでの数字が付けられたN.mp3ファイルを昇順に並べる。
Ｎが５０を超える場合は、最初の５０個の昇順に並べられたファイル数を返す。

解き方


Ｎが１０＾９のため全てのファイルを出力してからソートしては求めることができない。
そのため規則性を見つける必要がある。

Ｎ＝１０１８のとき、
最初は１から始め，
１０，１００，１０００と「１０をかけ、Ｎ以下ならその数」になる。
次は１００１、１００２、１００９、１０１と「１を足していき、１０で割ってＮ以下ならその数」となる。
また、１０１０、、、１０１８、１０２とＮを超えた場合は「１０で割って１を足し、Ｎ以下ならその数」になる。
最後に、１９１、、１９９、２、と１０で割りつづけられるなら割り続ける必要がある。
つまり、
①１０をかけ、Ｎ以下ならその数
②Ｎより大きい場合、１を足して１０の倍数もしくはＮと等しいなら、１０で割れなくなるまで割り続けた数に１を足した数なる。

これを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;
}

};

Share this

Google Facebook Twitter More

Related Posts

Next
« Prev Post
Previous
Next Post »