2591 Set Definition

2591 Set Definition


1338 Ugly Numbersやったらhalwhiteが紹介してくれた類問。

1338は1500番目までのUgly Numbersを求めればよかったから、
Uglys[1500]に格納すれば良かったけど、今度は10,000,000までの
Sを求めなければならないから配列確保できるのか？という疑問が
あったが一応1338を書き換えて手元で実行。。。こあだんぷと。


でもmain関数で宣言してたS[10000000]をグローバルにしたら大丈夫だった。
なんで？

#include<cstdio>
#include<algorithm>

using namespace std;

int S[10000005];

int main() {
    S[0] = 1;
    for (int i = 1, i2 = 0, i3 = 0; i < 10000000; ++i) {
	S[i] = min(S[i2]*2+1, S[i3]*3+1);
	if (S[i] == S[i2]*2+1) ++i2;
	if (S[i] == S[i3]*3+1) ++i3;
    }
    int n;
    while (~scanf("%d", &n)) {
	printf("%d\n", S[n-1]);
    }
}