[UVA][博弈] 11863 - Prime Game
|
E |
Prime Game Input: Standard Input Output: Standard Output |
|
Soha
and Tara have stopped playing the game ‘mouse and cheese’ which they invented
few months ago. One of the main reasons for discontinuing this game is that it
involves a mouse – (Tara is scared of
anything that has four legs and can move). Since Tara is fond of playing games, Soha came up with, yet,
another game that only involves a pen and a paper. This new game is called
‘Prime Game’. Initially Soha writes a
list of N integers on a piece of
paper. It’s a two player game where the players make moves alternately. Soha,
being player 1, goes first. The rules of this game are described below.
· In each move a player has to remove one or move contiguous numbers either from left or right from the list. In his/her turn a player can say ‘pass’ – which means he/she doesn’t have to remove any numbers in that move. However, a player can pass at most K times.
· The sum of these removed integers has to be a prime number. Prime numbers are positive integers that have exactly two distinct factors. So the first few prime numbers are 2 3 5 7 11 13..
· The number 42 is special and can take any value that the player chooses. For example, a player can remove the integers {4 10 42} in one move; if 42 is treated as 3, then sum equals to 17 – which is a prime number.
· If a player uses up all his/her ‘passes’ and doesn’t have any valid move, then he/she is declared as the loser.
If both the players play perfectly, who wins?
Input
The first line of input file is an integer, T(T < 100) that indicates the number of test cases. Each case starts with 2 integers N(0 < N < 100) and K(0 ≤ K < 1000). The meanings of these are mentioned above. The next line contains N space separated integers that Soha initially writes. Each of these integers will be in the range [-1000, 1000].
Output
For each case, output the case number first followed by the name of the player who wins. Look at the sample for exact format.
Sample Input Output for Sample Input
|
3 3 0 3 3 3 3 0 4 4 4 5 2 1 2 3 4 5 |
Case 1: Soha Case 2: Tara Case 3: Soha |
Problemsetter: Sohel Hafiz, Special Thanks: Jane Alam Jan
每次操作由左邊砍一段，或者由右邊砍一段，每次的一段總和必須是質數。
或者有 42 這個數字。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int N, K, A[105];
int dp[105][105];
#define maxL (262144>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
void sieve() {
register int i, j, k;
SET(0);
SET(1);
int n = 262144;
for(i = 2; i <= n; i++) {
if(!GET(i)) {
for(k = n/i, j = i*k; k >= i; k--, j -= i)
SET(j);
}
}
}
int isPrime(int val) {
if(val < 2) return 0;
return !GET(val);
}
int dfs(int l, int r) {
if(dp[l][r] != -1)
return dp[l][r];
int &ret = dp[l][r];
ret = 0;
for(int i = l; i <= r; i++)
if(A[i] == 42)
return ret = 1;
for(int i = l, sum = 0; i <= r; i++) {
sum += A[i];
if(isPrime(sum))
ret |= !dfs(i+1, r);
}
for(int i = r, sum = 0; i >= l; i--) {
sum += A[i];
if(isPrime(sum))
ret |= !dfs(l, i-1);
}
return ret;
}
int main() {
sieve();
int testcase, cases = 0;
int i, j;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &N, &K);
for(i = 0; i < N; i++)
scanf("%d", &A[i]);
memset(dp, -1, sizeof(dp));
int f = dfs(0, N-1);
printf("Case %d: %s\n", ++cases, f ? "Soha" : "Tara");
}
return 0;
}