Digits Square Board – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Cerinta completa

Two HackerRank staffers found a secret room with a mysterious square board and decided to play a game with it. The game has the following rules:

At the beginning of the game, the players write a single digit (given as input) ranging from to in each cell composing the square board.
The players move in alternating turns. In each move, the current player performs the following actions:
1. Chooses a board that has at least one non-prime number written on it and has more than one cell (i.e., dimensions ).
2. Cuts the chosen board into smaller boards by breaking it along any horizontal or vertical line at the edge of a cell.
Note: Although the game starts with one board, that board is split in two during each move. At the beginning of the move, a player can choose any one of the pieces of the original board (as long as it can have a legal move performed on it).
The game ends when there are no more cuttable boards (i.e., there are boards, or all boards have only prime numbers written on them). The first player who is unable to make a move loses.

Given the value of and the respective numbers written in each cell of the board, determine whether the person who wins the game is the first or second person to move. Assume both players move optimally.

Time Limit

Python: 18 seconds
Pypy2: 5 seconds

For other languages, the time limit is standard.

Input Format

The first line contains an integer, , denoting the number of test cases.
Each test case is defined as follows over the subsequent lines:

An integer, , denoting the length of each of the board’s sides.
Each line of the subsequent lines contains space-separated integers describing , where each describes the number written in cell of the board.

Constraints

Output Format

For each test case, print the name of the player with the winning strategy on a new line (i.e., either or ).

Sample Input

Sample Output

Second
First

Explanation

We’ll refer to the two players as and .

Test Case 0:
All cells contain prime numbers, so there are no valid moves available to . As wins by default, we print on a new line.

Test Case 1:
In this test case, the two players perform the following sequence of moves:

makes a horizontal cut, splitting the board into two boards. This is demonstrated in the following diagram:
now chooses one of the two rectangles and cuts it vertically, splitting it into two squares.
chooses remaining rectangle and cuts it vertically, splitting it into two squares.

After the above moves take place, the board is split into four squares and no more moves are available for to make. Thus, wins and we print on a new line.

Limbajul de programare folosit: python3

Cod:

#!/bin/python3

import math
import os
import random
import re
import sys


# document globals
N = None    # board size 
B = None    # board in 0/1 (is prime?)
G = None    # grundy
RINT = None # rows in B as Int
CINT = None # columns in B as Int

#
# Complete the 'squareBoard' function below.
#
# The function is expected to return a STRING.
# The function accepts 2D_INTEGER_ARRAY board as parameter.
#
def squareBoard(board):
    analyze(board)
    return 'First' if G[0][N-1][0][N-1] else 'Second'

def analyze(board):
    global N, B, G, RINT, CINT
    N = len(board)
    primes = {2,3,5,7}
    B = [[int(n not in primes) for n in row] for row in board]
    RINT = [ int(''.join(str(d) for d in reversed(row)),2) for row in B]
    CINT = [ int(''.join(str(d) for d in reversed(row)),2) for row in zip(*B)]
    G = [[[[0] * N for i2 in range(N)] for i3 in range(N)] for i4 in range(N)]
    GT = [[[[0] * N for i2 in range(N)] for i3 in range(N)] for i4 in range(N)]
    if not any(rint for rint in RINT):
        G[0][N-1][0][N-1] = 0
        return
    # fill in grundy numbers for all rectangles [rlo,rhi] x [clo,chi]
    # grundy is ...
    #   0 if rectangle is size 1 or doesn't contain any nonprime,
    #   else mex of all (cut into two pieces and xor them)
    for rsize in range(1,N +1):
        for csize in range(1,N +1):
            if rsize==1==csize: continue
            for rlo in range(N-rsize +1):
                rhi = rlo + rsize -1
                for clo in range(N-csize +1):
                    chi = clo + csize -1
                    # look for nonprime
                    if rsize < csize:
                        mask = get_mask(clo,chi)
                        if not any(RINT[ri] & mask for ri in range(rlo,rhi+1)):
                            continue
                    else:
                        mask = get_mask(rlo,rhi)
                        if not any(CINT[ci] & mask for ci in range(clo,chi+1)):
                            continue
                    # okay, there is some nonprime, so must do cuts ...
                    grundy = [0] * 40
                    #   ... by row [rlo,rcut] + [rcut+1,rhi]
                    GT_slice = GT[clo][chi]
                    for rcut in range(rlo,rhi):
                        grundy[GT_slice[rlo][rcut] ^ GT_slice[rcut+1][rhi]] = 1
                    #   ... by col [clo,ccut] + [ccut+1,chi]
                    G_slice = G[rlo][rhi]
                    for ccut in range(clo,chi):
                        grundy[G_slice[clo][ccut] ^ G_slice[ccut+1][chi]] = 1
                    mex = grundy.index(0)
                    G_slice[clo][chi] = mex
                    GT_slice[rlo][rhi] = mex
                    
    
def get_mask(i,j):
    return (1<<j+1) - (1<<i)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        n = int(input().strip())

        board = []

        for _ in range(n):
            board.append(list(map(int, input().rstrip().split())))

        result = squareBoard(board)

        fptr.write(result + '\n')

    fptr.close()

Scor obtinut: 1.0

Submission ID: 464669070

Link challenge: https://www.hackerrank.com/challenges/digits-square-board-1/problem

Digits Square Board