Submission #623952

#	Time	Username	Problem	Language	Result	Execution time	Memory
623952		jophyyjh	Packing Biscuits (IOI20_biscuits)	C++14	9 / 100	1088 ms	1208 KiB

biscuits

/**
 * Binary. Hmm, interesting. I started with [S2], which I solved with recursion in
 * O(kq). The basic idea is to treat two 2^i biscuits in the bag as one 2^(i+1).
 * 
 * A few greedy observations:
 * (1)  Given x, can we determine if it's possible? Well, we can simply iterate i
 *      from large to small. If the additional tastiness x we still need for a
 *      certain bag satisfies x >= 2^i, put a biscuit 2^i in the bag if there's one.
 * (2)  Biscuits of the same type can be distributed as evenly as possible, i.e.
 *      there is an optimal partition s.t. for every i
 *              |#2^i_biscuits_in_bag_1 - #2^i_biscuits_in_big_2| <= 1.
 * (3)  Unlike (1), (2), we consider from small to large. If x is odd, each bag needs
 *      at least 1 2^0 biscuit. After that, every 2 2^O biscuits can be grouped to
 *      form 1 2^1 biscuit, so we can add this num to the original num of 2^1
 *      biscuits. Well, let's write this recursively:
 *           def find():
 *               total = 0
 *               if #2^0 >= x:
 *                   add floor((#2^0 - x) / 2) to #2^1 and recurse downdwards
 *               add floor(#2^0 / 2) to 2^1 and recurse downwards
 *               ...
 * 
 * Time Complexity: (unknown yet)
 * Implementation 0.9           (Just for testing correctness)
*/

#include <bits/stdc++.h>
#include "biscuits.h"

typedef long long	ll;


ll search(ll x, std::vector<ll> a) {
    if (a.size() == 1)
        return a[0] / x + 1;
    ll zeroes = a[0], total = 0;
    if (zeroes >= x) {
        std::vector<ll> new_a = a;
        new_a.erase(new_a.begin());
        new_a[0] += (zeroes - x) / 2;
        total += search(x, new_a);
    }
    a.erase(a.begin());
    a[0] += zeroes / 2;
    total += search(x, a);
    return total;
}

ll count_tastiness(ll x, std::vector<ll> a) { 
    return search(x, a);
}

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