1305. Who’s Winner?Constraints
Time Limit: 1 secs, Memory Limit: 32 MB
Description
Nic and Susan play the game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Nic always starts with p=1, does his multiplication. Then Susan multiplies the number, then Nic and so on. Before a game starts, they draw an integer 1≤n<4,294,967,295 and the winner is who first reaches p≥n.
Input
Each line of input contains one integer number n.
Output
For each line of input output one line either
Nic wins.
or
Susan wins.
Assume that both of them play perfectly.
Sample Input1621734012226Sample OutputNic wins.Susan wins.Nic wins.Problem Source
ZSUACM Team Member
这题在编程书上看到了好高深的解法。。0.03s：
// Problem#: 1305// Submission#: 2777051// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License// URI: // All Copyright reserved by Informatic Lab of Sun Yat-sen University#include <stdio.h>#include <string.h>long long power2[33], power3[22], power5[15], power7[13];void make_power() {int i;for (power2[0] = 1, i = 1; i < 33; power2[i] = 2 * power2[i – 1], i++);for (power3[0] = 1, i = 1; i < 22; power3[i] = 3 * power3[i – 1], i++);for (power5[0] = 1, i = 1; i < 15; power5[i] = 5 * power5[i – 1], i++);for (power7[0] = 1, i = 1; i < 13; power7[i] = 7 * power7[i – 1], i++);}bool a[34][23][16][14]; //判断输赢//下面的循环是设立一个待定者，这个待定者在大于等于target的时候是输的，，那么由此推出只要在使得数字大于等于target的上一步就是赢的，然后由此往前推，推到第一个位置int main() {make_power();long long target;while (~scanf("%lld", &target)) {if (target == 1) {printf("Nic wins.\n");continue;}memset(a, false, sizeof(a));int p2, p3, p5, p7;for (p2 = 32; p2 >= 0; p2–) {for (p3 = 21; p3 >= 0; p3–) {for (p5 = 14; p5 >= 0; p5–) {for (p7 = 12; p7 >= 0; p7–) {if (power2[p2] * power3[p3] * power5[p5] * power7[p7] < target) {if (p2 < 32 && a[p2 + 1][p3][p5][p7] == false) { //乘2之后是输的，那么这一步就是赢的a[p2][p3][p5][p7] = true;continue;}if (p3 < 21 && a[p2][p3 + 1][p5][p7] == false) {a[p2][p3][p5][p7] = true;continue;}if (p2 < 31 && a[p2 + 2][p3][p5][p7] == false) {a[p2][p3][p5][p7] = true;continue;}if (p5 < 14 && a[p2][p3][p5 + 1][p7] == false) {a[p2][p3][p5][p7] = true;continue;}if (p2 < 32 && p3 < 21 && a[p2 + 1][p3 + 1][p5][p7] == false) {a[p2][p3][p5][p7] = true;continue;}if (p7 < 12 && a[p2][p3][p5][p7 + 1] == false) {a[p2][p3][p5][p7] = true;continue;}if (p2 < 30 && a[p2 + 3][p3][p5][p7] == false) {a[p2][p3][p5][p7] = true;continue;}if (p3 < 20 && a[p2][p3 + 2][p5][p7] == false) {a[p2][p3][p5][p7] = true;continue;}}}}}}if (a[0][0][0][0]) {printf("Nic wins.\n");} else {printf("Susan wins.\n");}}return 0;}
结果找规律：
假如Susan赢，那么Nic肯定要尽量拖慢她，就尽量乘2，相反，假如Nic赢，Nic肯定尽量乘9；
赢的人：
1 N
2~9 (1 * 9) N
10~18 (1 * 9 * 2) S
19~162 (1 * 9 * 2 * 9) N
163~324 (1 * 9 * 2 * 9 * 2) S
说明乘二之后大于等于目标的就是S赢，乘9后大于等于目标的N赢：0s：
#include <stdio.h>int main() {long long n;while (~scanf("%lld", &n)) {if (n == 1) {printf("Nic wins.\n");continue;}long long temp = 1;while (1) {temp *= 9;if (temp >= n) {printf("Nic wins.\n");break;}temp *= 2;if (temp >= n) {printf("Susan wins.\n");break;}}}return 0;}
当世界给草籽重压时，它总会用自己的方法破土而出。
