Soluție HackerRank pentru Chessboard Game, Again!. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Chessboard Game, Again!

Cerinta completa

Two players are playing a game on a [Expresie matematică indisponibilă în copia arhivată] chessboard. The rules of the game are as follows:

  • The game starts with [Expresie matematică indisponibilă în copia arhivată] coins located at one or more [Expresie matematică indisponibilă în copia arhivată] coordinates on the board (a single cell may contain more than one coin). The coordinate of the upper left cell is [Expresie matematică indisponibilă în copia arhivată], and the coordinate of the lower right cell is [Expresie matematică indisponibilă în copia arhivată].

  • In each move, a player must move a single coin from some cell [Expresie matematică indisponibilă în copia arhivată] to one of the following locations:

    1. [Expresie matematică indisponibilă în copia arhivată]
    2. [Expresie matematică indisponibilă în copia arhivată]
    3. [Expresie matematică indisponibilă în copia arhivată]
    4. [Expresie matematică indisponibilă în copia arhivată].

    Note: The coin must remain inside the confines of the board.

  • The players move in alternating turns. The first player who is unable to make a move loses the game.

The figure below shows all four possible moves:

chess

Note: While the figure shows a [Expresie matematică indisponibilă în copia arhivată] board, this game is played on a [Expresie matematică indisponibilă în copia arhivată] board.

Given the value of [Expresie matematică indisponibilă în copia arhivată] and the initial coordinate(s) of [Expresie matematică indisponibilă în copia arhivată] coins, determine which player will win the game. Assume both players always move optimally.

Input Format

The first line contains an integer, [Expresie matematică indisponibilă în copia arhivată], denoting the number of test cases.
Each test case is defined as follows over the subsequent lines:

  1. The first line contains an integer, [Expresie matematică indisponibilă în copia arhivată], denoting the number of coins on the board.
  2. Each line [Expresie matematică indisponibilă în copia arhivată] (where [Expresie matematică indisponibilă în copia arhivată]) of the [Expresie matematică indisponibilă în copia arhivată] subsequent lines contains [Expresie matematică indisponibilă în copia arhivată] space-separated integers describing the respective values of [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] of the coordinate where coin [Expresie matematică indisponibilă în copia arhivată] is located.

Note: Recall that a cell can have more than one coin (i.e., any cell can have [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată] coins in it at any given time).

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată], where [Expresie matematică indisponibilă în copia arhivată].

Output Format

On a new line for each test case, print [Expresie matematică indisponibilă în copia arhivată] if the first player is the winner; otherwise, print [Expresie matematică indisponibilă în copia arhivată].

Sample Input

2
3
5 4
5 8
8 2
6
7 1
7 2
7 3
7 4
7 4
7 4

Sample Output

First
Second

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        int[][] moves = {{-2, 1}, {-2, -1}, {1, -2}, {-1, -2}};
        int[][] g = new int[16][16]; // 1..15

        for (int s = 2; s <= 30; s++) {
            for (int x = 1; x <= 15; x++) {
                int y = s - x;
                if (y < 1 || y > 15) continue;

                boolean[] seen = new boolean[8];
                for (int[] mv : moves) {
                    int nx = x + mv[0];
                    int ny = y + mv[1];
                    if (nx >= 1 && nx <= 15 && ny >= 1 && ny <= 15) {
                        int val = g[nx][ny];
                        if (val < seen.length) seen[val] = true;
                    }
                }

                int mex = 0;
                while (mex < seen.length && seen[mex]) mex++;
                g[x][y] = mex;
            }
        }

        FastScanner fs = new FastScanner(System.in);
        int t = fs.nextInt();
        StringBuilder out = new StringBuilder();

        while (t-- > 0) {
            int k = fs.nextInt();
            int nim = 0;
            for (int i = 0; i < k; i++) {
                int x = fs.nextInt();
                int y = fs.nextInt();
                nim ^= g[x][y];
            }
            out.append(nim != 0 ? "First" : "Second").append('\n');
        }

        System.out.print(out);
    }
}

Scor obtinut: 1.0

Submission ID: 464615945

Link challenge: https://www.hackerrank.com/challenges/chessboard-game-again-1/problem

Chessboard Game, Again!