最省納智捷1年新車83萬起工程師靠存股年領百萬股息輕忽小中風,當心變殘障買太多也不���!7500...
2014-02-17 20:56:36 人氣(4) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][Nim] 11859 - Division Game

0
收藏
0
推薦

A

Division Game

Input: Standard Input

Output: Standard Output

 

Division game is a 2-player game. In this game, there is a matrix of positive integers with N rows and M columns. Players make their moves in turns. In each step, the current player selects a row. If the row contains all 1s, the player looses. Otherwise, the player can select any number of integers (but at least 1 and each of them should be greater than 1) from that row and then divides each of the selected integers with any divisor other than 1.  For example, 6 can be divided by 2, 3 and 6, but cannot be divided by 1, 4 and 5. The player who first makes the matrix all 1s wins. In other words, if in his/her move, player gets the matrix with all 1s, then he/she looses. Given the matrix, your task is to determine whether the first player wins or not. Assume that both of the players will play perfectly to win.

 

Input

The first line has a positive integer T, T <= 50, denoting the number of test cases. This is followed by each test case per line.

Each test case starts with a line containing 2 integers N and M representing the number of rows and columns respectively. Both N and M are between 1 and 50 inclusive. Each of the next N line each contains M integers. All these integers are between 2 and 10000 inclusive.

 

Output

For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is “YES” when the first player has a winning strategy  and “NO” otherwise.

 

Sample Input                              Output for Sample Input

5

2 2

2 3

2 3

2 2

4 9

8 5

3 3

2 3 5

3 9 2

8 8 3

3 3

3 4 5

4 5 6

5 6 7

2 3

4 5 6

7 8 9

Case #1: NO

Case #2: NO

Case #3: NO

Case #4: YES

Case #5: YES

 


Problemsetter: Abdullah-al-Mahmud, Special Thanks: Manzurur Rahman Khan

題目描述:

每次從一個 row 中挑出一個數字,並且將這個數字除以他的其中一個因數。

如果怎麼挑都是 1,則玩家輸了。

題目解法:

每一個 row 就是一堆,而每堆的個數即質因數分解的指數總合。

#include <stdio.h>
#define maxL (50000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int p[5500], pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            p[pt++] = i;
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
        }
    }
}
int divisor(int n) {
    int ret = 0;
    for(int i = 0; i < pt && p[i]*p[i] <= n; i++) {
        while(n%p[i] == 0)
            n /= p[i], ret++;
    }
    if(n != 1)
        ret++;
    return ret;
}
int main() {
    sieve();
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        int n, m, x, i, j;
        int s = 0;
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++) {
            int cnt = 0;
            for(j = 0; j < m; j++)
                scanf("%d", &x), cnt += divisor(x);
            s ^= cnt;
        }
        printf("Case #%d: ", ++cases);
        if(s)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

11859Division GameNim
台長:Morris
人氣(4) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 11841 - Y-game
此分類上一篇:[UVA][博弈] 11863 - Prime Game

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文