Cerinta completa

Two players (numbered and ) are playing a game of Tower Breakers! The rules of the game are as follows:

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

Given the value of 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 ; otherwise, print .

Input Format

The first line contains an integer, , denoting the number of test cases.
The subsequent lines define the test cases. Each test case is described by two lines:

  1. An integer, , denoting the number of towers.
  2. space-separated integers, , where each describes the height of tower .

Constraints

Output Format

For each test case, print a single integer denoting the winner (i.e., either or ) 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 into two towers of height and wins.

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

  • Break the second tower into towers of height .
  • Break the third tower into towers of height .

Whichever move player makes, player 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!