ABC 101 D Snuke Numbers
問題概要
正整数nに対して、nを10進法表記したときの各桁の和をS(n)とし、関数gをg(n)=nS(n)と定義する。
そして任意の正整数m>nに対してg(n)≤g(m)が成立するようなnを「すぬけ数」と呼ぶことにする。
このとき、すぬけ数を小さい方から順にK個出力せよ。
K≥1
K番目のすぬけ数は10の15乗以下である。
感想
19,29,39...199,299..みたいに右側が99..となる集合なのかなと思った。その通りに実装したら..なんとTLE。実力不足。
また、右側が99..となる集合でもないらしい。難しい..
WAコード
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; int diget(int num) { string str = to_string(num); int num1 = str.length(); if (num1 == 1) return true; for (int i = 1; i < num1; i++) { if (str[i] - '0' != 9) { return false; } } return true; } int main() { int K = 0; cin >> K; int count = 0; int i = 1; while (1) { bool can1 = diget(i); if (can1) { cout << i << endl; count++; } if (count == K) { break; } i++; } }
解説を見る
参考にさせて頂いたサイト
ARC099(ABC101) 解説 - Mister雑記
理解した後の感想
まずこのすぬけ数、プログラムで扱えるものではないらしい。n<10の15乗という条件があって初めて求められるものとなる。
すべてアルゴリズムでゴリ押すのではなく、この時はどうだろう..と検証していくことがこの問題の肝であると考える。
んー..これは流石に実力不足が過ぎるのでこの問題はスルーするのがよさそう