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, and both players always move optimally.
  • Initially there are towers of various heights.
  • The players move in alternating turns. In each turn, a player can choose a tower of height and reduce its height to , where and evenly divides .
  • 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? If the first player wins, print ; otherwise, print .

Input Format

The first line contains an integer, , denoting the number of test cases.
Each of the subsequent lines defines a test case. Each test case is described over the following 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

Test Case 0:
Player reduces the second tower to height and subsequently wins.

Test Case 1:
There are two possible moves:

  1. Reduce the second tower to
  2. Reduce the third tower to .

Whichever move player makes, player will make the other move. Thus, player wins.

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[] spf = new int[maxH + 1];
        for (int i = 2; i <= maxH; i++) {
            if (spf[i] == 0) {
                spf[i] = i;
                if ((long) i * i <= maxH) {
                    for (int j = i * i; j <= maxH; j += i) {
                        if (spf[j] == 0) spf[j] = i;
                    }
                }
            }
        }

        int[] omega = new int[maxH + 1];
        omega[1] = 0;
        for (int x = 2; x <= maxH; x++) {
            int p = spf[x];
            omega[x] = omega[x / p] + 1;
        }

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

Scor obtinut: 1.0

Submission ID: 464615800

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

Tower Breakers, Revisited!