Sicily 1305. Who’s Winner?

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 Input

162
17
34012226
      

Sample Output

Nic 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: http://creativecommons.org/licenses/by-nc-sa/3.0/
// 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;
}