SRM571 Div1 Easy - FoxAndMp3
問題
mp3プレイヤーにn曲の曲が入っており、i曲目の名前は "i.mp3" である
このプレイヤーは曲名を数字の昇順ではなく文字列の昇順にソートする
このプレイヤーの表示順に、
1) n<=50のときは全曲の曲名
2) そうでないときは最初の50曲の曲名
を書け
1 <= n <= 10^9
解法
2桁以下は全部試す
3桁以上は先頭50個だけ試せば十分
それでも1万文字も行かないから計算量もメモリも大丈夫
class FoxAndMp3 { public: vector<string> playList(int n) { vector<string> res, x; reps(i,1,min(n,99)+1) x.push_back(to_string(i) + ".mp3"); ll t = 100; rep(d,10) { rep(i,55) if (t+i<=n) x.push_back(to_string(t+i) + ".mp3"); t *= 10; } sort(all(x)); rep(i,min(n,50)) res.push_back(x[i]); return res; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12436&rd=15491