Submission #305857

#	Time	Username	Problem	Language	Result	Execution time	Memory
305857		llaki	Packing Biscuits (IOI20_biscuits)	Java	9 / 100	1200 ms	103616 KiB

biscuits

import java.util.HashMap;

public class biscuits {
    long count_tastiness(long x, long[] a) {
        if (x == 1) {
            return solveXIsOne(a);
        }
        return countNaive(x, a);
    }

    // How many diff. sums can we get by  (n[i] * 2^i, where 0 <= n[i] <= a[i]).
    long solveXIsOne(long[] a) {
        return recursiveXIsOne(0, a[0], a);
    }

    HashMap<String, Long> map = new HashMap<>();

    String toKey(int pos, long first) {
        return pos + "." + first;
    }

    long recursiveXIsOne(int pos, long first, long[] a) {
        if (pos == a.length - 1) {
            return first + 1;
        }
        String key = toKey(pos, first);
        if (map.containsKey(key)) map.get(key);
        long res = recursiveXIsOne(pos + 1, a[pos + 1] + first / 2, a);
        if (first > 0) {
            res += recursiveXIsOne(pos + 1, a[pos + 1] + (first - 1) / 2, a);
        }
        map.put(key, res);
        return res;
    }

    long countNaive(long x, long[] a) {
        return countRec(x, a, 0);
    }

    long countRec(long x, long[] a, int index) {
        if (index == a.length - 1) {
            return a[a.length - 1] / x + 1;
        }
        long temp = a[index + 1];
        a[index + 1] = a[index + 1] + a[index] / 2;
        long answer = countRec(x, a, index + 1);
        if (a[index] >= x) {
            a[index + 1] = temp + (a[index] - x) / 2;
            answer += countRec(x, a, index + 1);
            a[index + 1] = temp;
        }
        a[index + 1] = temp;
        return answer;
    }

}
// (s[k-1] - i * X) / (2^(k-1)), 0 <= i < 2^(k - 1).
// For which i is this state valid?
// If for each position b s.t. b-th bit is set in i, (s[b+1] - (2^b + prev(i,b))X) / 2^(b+1) >= X.

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23