The idea of the game of taking a ball is clear, that is, to traverse all possible situations of two people, and finally to see the number of odd balls in two hands.Depth-first search can be used when traversing
But direct depth-first searches are definitely not possible, because if you have 1,000 balls, you have three choices at a time, totaling about three hundred times.This is an astronomical number.(
Memory storage is required to save previously calculated data.But it is unrealistic to save all the data, because we need to save the result when there are n balls left, m balls for ourselves and K balls for others.Then you need a three-dimensional array a[n][m][k], while n,m,k can be as large as 1000, which requires about 1000M of memory.(
What shall I do?Let's also look at the title requirements to determine the parity of the last two people's balls. That is to say, we only have to deal with parity. That is, when there are 300 balls left, three of our own, eight of the others are the same as when there are 300 balls left, five of our own and two of the others are the same.Because more balls are odd, less balls are even, and the total number of balls is the same, so the eventual parity is the same, as is winning and losing.
Ball-taking Game
Two people play a game to get the ball.
There are N balls in total, each taking turns to get the ball, each time any number of {n1,n2,n3} in the set can be taken.
If you can't continue to get the ball, the game is over.
At this point, the odd-numbered side wins.
If both of them are odd, they are drawn.
Assuming the smartest approach is taken by both parties,
Is the first person to win the game sure?
Try programming to solve this problem.
Input format:
The first row has three positive integers, n1 n2 n3, separated by spaces, indicating the number of preferable values at a time (0 < n1, n2, N3 < 100)
The second row has five positive integers X1 x2... X5, separated by spaces, representing the initial number of balls in five rounds (0 < Xi < 1000)
Output format:
Five characters on a line with separate spaces.Indicates whether the person who gets the ball first in each round will win or not.
If you win, output +,
Secondly, if you can draw your opponent, output 0,
In any case, the output-
For example, enter:
1 2 3
1 2 3 4 5
The program should output:
+ 0 + 0 -
For example, enter:
1 4 5
10 11 12 13 15
The program should output:
0 - 0 + +
For example, enter:
2 3 5
7 8 9 10 11
The program should output:
+ 0 0 0 0
Resource conventions:
Peak memory consumption (including virtual machines) < 256M
CPU consumption < 3000ms
First we write out the basic depth-first search code, regardless of memory issues.At least on small data.Below is a depth-first search without memory.
public class SelectBall { public static int[] a; public static int min; public static int[][] cash = new int[1001][1001]; public static int f(int rest, int havenum, int othernum) { if (rest < min) { if (havenum % 2 != 0 && othernum % 2 == 0) return 2; if (havenum % 2 != 0 && othernum % 2 != 0) return 1; if (havenum % 2 == 0 && othernum % 2 == 0) return 1; return 0; } boolean equalflag = false; for (int sel : a) { if (sel > rest) continue; // f(1,0,1) int result = f(rest - sel, othernum, havenum + sel); if (result == 0) return 2; if (result == 1) equalflag = true; } if (equalflag) return 1; else return 0; } public static void main(String[] args) { int[] b = { 1, 2, 3, 4, 5 }; a = new int[] { 1, 2, 3 }; min = 1; for (int total : b) System.out.println(f(total, 0, 0)); } }
Here is the code for memory saving:
public class SelectBall { public static int[] a; public static int min; public static int[][][] cash = new int[1001][2][2]; public static int f(int rest, int havenum, int othernum) { if (rest < min) { if (havenum % 2 != 0 && othernum % 2 == 0) return 2; if (havenum % 2 != 0 && othernum % 2 != 0) return 1; if (havenum % 2 == 0 && othernum % 2 == 0) return 1; return -1; } boolean equalflag = false; for (int sel : a) { if (sel > rest) continue; int result; if (cash[rest - sel][othernum % 2][(havenum + sel) % 2] != 0) result = cash[rest - sel][othernum % 2][(havenum + sel) % 2]; else { result = f(rest - sel, othernum, havenum + sel); cash[rest - sel][othernum % 2][(havenum + sel) % 2] = result; } if (result == -1) return 2; if (result == 1) equalflag = true; } if (equalflag) return 1; else return -1; } public static void main(String[] args) { int[] b = { 1, 2, 3, 4, 5, 900 }; a = new int[] { 1, 2, 3 }; min = 1; for (int total : b) { char ch = 0; switch (f(total, 0, 0)) { case -1: ch = '-'; break; case 1: ch = '0'; break; case 2: ch = '+'; break; } System.out.print(ch); } } }