Cerinta completa

Consider the following game:

  • There are two players, First and Second, sitting in front of a pile of stones. First always plays first.
  • There is a set, , of distinct integers defined as .
  • The players move in alternating turns. During each turn, a player chooses some and splits one of the piles into exactly smaller piles of equal size. If no exists that will split one of the available piles into exactly equal smaller piles, the player loses.
  • Both players always play optimally.

Given , , and the contents of , find and print the winner of the game. If First wins, print First; otherwise, print Second.

Input Format

The first line contains two space-separated integers describing the respective values of (the size of the initial pile) and (the size of the set).
The second line contains distinct space-separated integers describing the respective values of .

Constraints

Output Format

Print First if the First player wins the game; otherwise, print Second.

Sample Input 0

15 3
5 2 3

Sample Output 0

Second

Explanation 0

The initial pile has stones, and . During First‘s initial turn, they have two options:

  1. Split the initial pile into equal piles, which forces them to lose after the following sequence of turns:
    stone-division.png
  2. Split the initial pile into equal piles, which forces them to lose after the following sequence of turns:
    stone-division-2.png

Because First never has any possible move that puts them on the path to winning, we print Second as our answer.

Limbajul de programare folosit: java8

Cod:

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

public class Solution {
    static long[] S;
    static HashMap<Long, Boolean> memo;

    static boolean win(long n) {
        Boolean got = memo.get(n);
        if (got != null) return got;

        for (long s : S) {
            if (s > n) continue;
            if (n % s != 0) continue;

            if ((s & 1L) == 0L) {
                memo.put(n, true);
                return true;
            }

            long child = n / s;
            if (!win(child)) {
                memo.put(n, true);
                return true;
            }
        }

        memo.put(n, false);
        return false;
    }

    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++];
        }
        long nextLong() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            long val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return sign == 1 ? val : -val;
        }
        int nextInt() throws IOException { return (int) nextLong(); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        long n = fs.nextLong();
        int m = fs.nextInt();
        S = new long[m];
        for (int i = 0; i < m; i++) S[i] = fs.nextLong();

        Arrays.sort(S);
        memo = new HashMap<>();
        boolean firstWins = win(n);
        System.out.println(firstWins ? "First" : "Second");
    }
}

Scor obtinut: 1.0

Submission ID: 464617024

Link challenge: https://www.hackerrank.com/challenges/stone-division/problem

Stone Division