Cerinta completa

You have a pile of stones that you want to split into multiple piles, as well as a set, , of distinct integers. We define a move as follows:

  • First, choose a pile of stones. Let’s say that the chosen pile contains stones.
  • Next, look for some such that and is divisible by (i.e., is a factor of ); if such an exists, you can split the pile into equal smaller piles.

You are given queries where each query consists of and . For each query, calculate the maximum possible number of moves you can perform and print it on a new line.

Input Format

The first line contains an integer, , denoting the number of queries. The subsequent lines describe each query in the following format:

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

Constraints

Subtask

  • for of the maximum score.

Output Format

For each query, calculate the maximum possible number of moves you can perform and print it on a new line.

Sample Input 0

1
12 3
2 3 4

Sample Output 0

4

Explanation 0

Initially there is a pile with stones:

image

You can make a maximal moves, described below:

  • Select from and split it into equal piles of size to get:
    image

  • Select from and split a pile of size into equal piles of size to get:
    image

  • Repeat the previous move again on another pile of size to get:
    image

  • Repeat the move again on the last pile of size to get:
    image

As there are no more available moves, we print (the number of moves) on a new line.

Limbajul de programare folosit: java8

Cod:

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

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

    static long solve(long y) {
        Long got = memo.get(y);
        if (got != null) return got;

        long best = 0;
        for (long x : S) {
            if (x >= y) break;
            if (y % x != 0) continue;
            long pieces = y / x;
            long cand = 1 + pieces * solve(x);
            if (cand > best) best = cand;
        }

        memo.put(y, best);
        return best;
    }

    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);
        int q = fs.nextInt();
        StringBuilder out = new StringBuilder();

        while (q-- > 0) {
            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);

            // deduplicate
            int sz = 0;
            for (int i = 0; i < m; i++) {
                if (i == 0 || S[i] != S[i - 1]) S[sz++] = S[i];
            }
            S = Arrays.copyOf(S, sz);

            memo = new HashMap<>();
            memo.put(1L, 0L);
            out.append(solve(n)).append('\n');
        }

        System.out.print(out);
    }
}

Scor obtinut: 1.0

Submission ID: 464617090

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

Stone Division, Revisited