[CodeVs]谁是赢家

Description

[CodeVs]谁是赢家

Solution

一道博弈，能在考场上推出正确公式我也很吃惊
很难解释，大概是
首先，每步都是最优解，所以不可能有(God!)
如果我要先手赢，所以我要我出很大你出很小的情况时最后一次我出一个(2~9)我就大于(n)，而且我出很大你也出很大时你不能使结果大于(n)
如果我要后手赢，所以我要你出很小时我出(2~9)我就大于n，而且我出很大是你也出很大你不能结果大于(n)
然后大概是
(9*2*9)
(2*9*2*9)
这样下去

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
ll t, n;
ll a[20], b[20];
inline ll read() {
	ll s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}
int main() {
	t = 1;
	for (register ll i = 1; i <= 15; i++) {
		a[i] = b[i - 1] + 1;
		if (i % 2 == 1)
			b[i] = t * 9, t *= 9;
		else
			b[i] = t * 2, t *= 2;
	}
	n = read();
	for (register ll i = 1; i <= 15; i++)
		if (a[i] <= n && n <= b[i])
			if (i % 2 == 1)
				printf("Nic");
			else
				printf("Susan");
	return 0;
}