2247 Humble Numbers

2247 Humble Numbers

2, 3, 5, 7しか素因数をもたない数をhumble numberと呼ぶ。ただし1はhumble numberである。
入力n (1 <= n <= 5842)に対して、n番目のhumble numberを返す問題。

…のはずが！

この問題を解くにあたって参考にしたサイト → 英語の数字の読み方・書き方　基数・序数編

なぜか？それは後ほど。

この問題。まず単純に書こうとすると、ある数についてhumble numberであるか判定して、humble numberであればvector humblesにでも格納していけばよい。

判定は例えば以下のように書ける。

int c_target = target;
for (int i = 2; i <= 7; ++i) {
    while (target % i == 0) {
	target /= i;
    }
    if (target == 1) break;
 }
if (target == 1) humbles.push_back(c_target);

始めにこれで書いてみた。

そして手元で試してみた。

明らかにTLE…orz

そもそもhumble numberかどうかという判定を行うことが、ダメなのだろう。

そこで次のことに気づく（以前にも似たような問題があったような…）

あるhumble numberはそれより小さいhumble numberの2または3または5または7倍の数である。

つまり、humble numberだけを5842番目までひたすら生成することが可能！

手元でもばっちり動いていざsubmit！

WA…orz

きっと何かのまちがいだと思い再submit！

再WA…orz

なんでなんで！？ってなってサンプル出力との差分をとってみた。
すると。。。

じぶんの：The 11st humble number is 12.

サンプル：The 11th humble number is 12.

わかるかぁっ！

この他にも12が12nd、13が13rdになっていたので直して再々submit！

再々WA…orz

ぬわぁぁぁぁっ！ってなって先程の参考URLで英語について学んだら次のように書いてあった。

111  a (one) hundred (and) eleven 

…。

無事ACとなりました。

#include<cstdio>
#include<vector>
#include<cmath>

using namespace std;

int min4(int a, int b, int c, int d) {
    return min(a, min(b, min(c, d)));
}

int main() {
    vector<int> humbles;
    int i2 = 0, i3 = 0, i5 = 0, i7 = 0;

    humbles.push_back(1);
    while (humbles.size() <= 5842) {
	int hn2 = 2 * humbles[i2];
	int hn3 = 3 * humbles[i3];
	int hn5 = 5 * humbles[i5];
	int hn7 = 7 * humbles[i7];
	humbles.push_back(min4(hn2, hn3, hn5, hn7));
	
	int newhn = *(humbles.end()-1);
	if (newhn == hn2) ++i2;
	if (newhn == hn3) ++i3;
	if (newhn == hn5) ++i5;
	if (newhn == hn7) ++i7;
    }
    int n;
    while (scanf("%d", &n), n) {
	if (n % 100 == 11 || n % 100 == 12 || n % 100 == 13) {
	    printf("The %dth humble number is %d.\n", n, humbles[n-1]);
	    continue;
	}
	switch (n % 10) {
	case 1:
	    printf("The %dst humble number is %d.\n", n, humbles[n-1]);
	    break;
	case 2:
	    printf("The %dnd humble number is %d.\n", n, humbles[n-1]);
	    break;
	case 3:
	    printf("The %drd humble number is %d.\n", n, humbles[n-1]);
	    break;
	default:
	    printf("The %dth humble number is %d.\n", n, humbles[n-1]);
	}
    }
}