Cerinta completa

Alice and Bob invented the following silly game:

  • The game starts with an integer, , that’s used to build a of distinct integers in the inclusive range from to (i.e., ).
  • Alice always plays first, and the two players move in alternating turns.
  • During each move, the current player chooses a prime number, , from . The player then removes and all of its multiples from .
  • The first player to be unable to make a move loses the game.

Alice and Bob play games. Given the value of for each game, print the name of the game’s winner on a new line. If Alice wins, print Alice; otherwise, print Bob.

Note: Each player always plays optimally, meaning they will not make a move that causes them to lose the game if some better, winning move exists.

Input Format

The first line contains an integer, , denoting the number of games Alice and Bob play.
Each line of the subsequent lines contains a single integer, , describing a game.

Constraints

Subtasks

  • for of the maximum score

Output Format

For each game, print the name of the winner on a new line. If Alice wins, print Alice; otherwise, print Bob.

Sample Input 0

3
1
2
5

Sample Output 0

Bob
Alice
Alice

Explanation 0

Alice and Bob play the following games:

  1. We are given , so . Because Alice has no valid moves (there are no prime numbers in the set), she loses the game. Thus, we print Bob on a new line.
  2. We are given , so . Alice chooses the prime number and deletes it from the set, which becomes . Because Bob has no valid moves (there are no prime numbers in the set), he loses the game. Thus, we print Alice on a new line.
  3. We are given , so . Alice chooses the prime number and deletes the numbers and from the set, which becomes . Now there are two primes left, and . Bob can remove either prime from the set, and then Alice can remove the remaining prime. Because Bob is left without a final move, Alice will always win. Thus, we print Alice on a new line.

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 g = fs.nextInt();
        int[] nVals = new int[g];
        int maxN = 0;
        for (int i = 0; i < g; i++) {
            nVals[i] = fs.nextInt();
            if (nVals[i] > maxN) maxN = nVals[i];
        }

        boolean[] isPrime = new boolean[maxN + 1];
        Arrays.fill(isPrime, true);
        if (maxN >= 0) isPrime[0] = false;
        if (maxN >= 1) isPrime[1] = false;
        for (int i = 2; i * i <= maxN; i++) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j <= maxN; j += i) isPrime[j] = false;
        }

        int[] primeCount = new int[maxN + 1];
        for (int i = 1; i <= maxN; i++) {
            primeCount[i] = primeCount[i - 1] + (isPrime[i] ? 1 : 0);
        }

        StringBuilder out = new StringBuilder();
        for (int n : nVals) {
            out.append((primeCount[n] % 2 == 1) ? "Alice" : "Bob").append('\n');
        }
        System.out.print(out);
    }
}

Scor obtinut: 1.0

Submission ID: 464615746

Link challenge: https://www.hackerrank.com/challenges/alice-and-bobs-silly-game/problem

Alice and Bob’s Silly Game