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

  • Problemă: Tower Breakers, Again!

Cerinta completa

Two players (numbered [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată]) are playing a game of Tower Breakers! The rules of the game are as follows:

  • Player [Expresie matematică indisponibilă în copia arhivată] always moves first.
  • Initially there are [Expresie matematică indisponibilă în copia arhivată] towers of various heights.
  • The players move in alternating turns. In each turn, a player must choose a tower of height [Expresie matematică indisponibilă în copia arhivată] and break it down into [Expresie matematică indisponibilă în copia arhivată] towers, each of height [Expresie matematică indisponibilă în copia arhivată]. The numbers [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] must satisfy [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].
  • If the current player is unable to make any move, they lose the game.

Given the value of [Expresie matematică indisponibilă în copia arhivată] and the respective height values for all towers, can you determine who will win, assuming both players always move optimally? If the first player wins, print [Expresie matematică indisponibilă în copia arhivată]; otherwise, print [Expresie matematică indisponibilă în copia arhivată].

Input Format

The first line contains an integer, [Expresie matematică indisponibilă în copia arhivată], denoting the number of test cases.
The [Expresie matematică indisponibilă în copia arhivată] subsequent lines define the test cases. Each test case is described by two lines:

  1. An integer, [Expresie matematică indisponibilă în copia arhivată], denoting the number of towers.
  2. [Expresie matematică indisponibilă în copia arhivată] space-separated integers, [Expresie matematică indisponibilă în copia arhivată], where each [Expresie matematică indisponibilă în copia arhivată] describes the height of tower [Expresie matematică indisponibilă în copia arhivată].

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

Output Format

For each test case, print a single integer denoting the winner (i.e., either [Expresie matematică indisponibilă în copia arhivată] or [Expresie matematică indisponibilă în copia arhivată]) on a new line.

Sample Input

2
2 
1 2
3 
1 2 3

Sample Output

1
2

Explanation

In the first test case, the first player simply breaks down the second tower of height [Expresie matematică indisponibilă în copia arhivată] into two towers of height [Expresie matematică indisponibilă în copia arhivată] and wins.

In the second test case, there are only two possible moves:

  • Break the second tower into [Expresie matematică indisponibilă în copia arhivată] towers of height [Expresie matematică indisponibilă în copia arhivată].
  • Break the third tower into [Expresie matematică indisponibilă în copia arhivată] towers of height [Expresie matematică indisponibilă în copia arhivată].

Whichever move player [Expresie matematică indisponibilă în copia arhivată] makes, player [Expresie matematică indisponibilă în copia arhivată] can make the other move and win the game.

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 {
        FastScanner fs = new FastScanner(System.in);
        int t = fs.nextInt();

        int[][] tests = new int[t][];
        int maxH = 1;
        for (int tc = 0; tc < t; tc++) {
            int n = fs.nextInt();
            tests[tc] = new int[n];
            for (int i = 0; i < n; i++) {
                int h = fs.nextInt();
                tests[tc][i] = h;
                if (h > maxH) maxH = h;
            }
        }

        int[] g = new int[maxH + 1];
        int[] seen = new int[256];
        int stamp = 1;

        g[1] = 0;
        for (int x = 2; x <= maxH; x++) {
            stamp++;
            int lim = (int) Math.sqrt(x);
            for (int d = 1; d <= lim; d++) {
                if (x % d != 0) continue;

                int z1 = d;
                int y1 = x / z1;
                if (z1 < x) {
                    int val = (y1 % 2 == 0) ? 0 : g[z1];
                    if (val >= seen.length) seen = Arrays.copyOf(seen, val + 64);
                    seen[val] = stamp;
                }

                int z2 = x / d;
                if (z2 != z1 && z2 < x) {
                    int y2 = x / z2;
                    int val = (y2 % 2 == 0) ? 0 : g[z2];
                    if (val >= seen.length) seen = Arrays.copyOf(seen, val + 64);
                    seen[val] = stamp;
                }
            }

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

        StringBuilder out = new StringBuilder();
        for (int[] arr : tests) {
            int nim = 0;
            for (int h : arr) nim ^= g[h];
            out.append(nim != 0 ? 1 : 2).append('\n');
        }

        System.out.print(out);
    }
}

Scor obtinut: 1.0

Submission ID: 464615880

Link challenge: https://www.hackerrank.com/challenges/tower-breakers-again-1/problem

Tower Breakers, Again!