Chessboard Game, Again!
Chessboard Game, Again!
+ 1 comment when will a player be unable to make a move...if it is said that a cell can have more than one coins
+ 0 comments I recommend doing the previous problems on this chapter before doing this one. Especially the first chessboard game. If you don't have an understanding of how solving a nim game works, you should read about it before trying this problem. You will need an understanding of how to use the sprague-grundy theorem to solve this.
+ 1 comment What is the meaning of "move optimally"?
+ 0 comments java solution, passes all test cases in O(k) time and O(1) space. First compute the nimber (e.g. Grundy number) for all 15 x 15=225 spots on the chess board. The nimber of a spot (x,y) is the smallest non-negative integer not equal to the grundy numbers of any of the up to four spots reachable from (x,y) in a single jump. This can be done in O(m^2) time, where m=15=O(1) in this problem, by filling in successive diagonals of the matrix of nimbers.
Once we have the nimbers of every spot on the chessboard, simply take cumulative XOR of all k nimbers. If 0, the first player loses, and if nonzero, the first player wins.
import java.util.Scanner; class Solution{ static int[][] nimbers(final int side){ int[][] nb=new int[side][side]; for(int j=2;j<2*side-1;++j){ int i=j<side?0:j-side+1; int k=j<side?j:side-1; while(i<=k){ boolean[] seen=new boolean[4+1]; if(i>1){ seen[nb[i-2][k-1]]=true; if(k!=side-1) seen[nb[i-2][k+1]]=true; } if(k>1){ if(i!=0) seen[nb[i-1][k-2]]=true; if(i!=side-1) seen[nb[i+1][k-2]]=true; } int l=0; while(seen[l]) ++l; nb[i][k]=l; nb[k][i]=l; ++i; --k; } } return nb; } static boolean win(int nCoin, Scanner sc, int[][] nb){ int nimSum=0; while(nCoin-- != 0){ int x=sc.nextInt(), y=sc.nextInt(); nimSum ^= nb[x-1][y-1]; } return nimSum!=0; } public static void main(String[] args){ Scanner sc=new Scanner(System.in); int nCase=sc.nextInt(), side=15; int[][] nb=nimbers(side); while(nCase-- != 0){ int nCoin=sc.nextInt(); System.out.println(win(nCoin,sc,nb)?"First":"Second"); } sc.close(); } }
+ 0 comments Too difficult for me
Sort 15 Discussions, By:
Please Login in order to post a comment