Biscuits

Packing Biscuits (biscuits)

Aunty Khong is organising a competition with participants, and wants to give each participant a

bag of biscuits. There are different types of biscuits, numbered from to

. Each biscuit of

type (

) has a tastiness value of

. Aunty Khong has

(possibly zero) biscuits of

type in her pantry.

Each of Aunty Khong's bags will contain zero or more biscuits of each type. The total number of

biscuits of type in all the bags must not exceed

. The sum of tastiness values of all biscuits in a

bag is called the total tastiness of the bag.

Help Aunty Khong find out how many different values of exist, such that it is possible to pack

bags of biscuits, each having total tastiness equal to .

Implementation Details

You should implement the following procedure:

int64 count_tastiness(int64 x, int64[] a)

the number of bags of biscuits to pack.

an array of length . For
,
denotes the number of biscuits of type in the
pantry.
The procedure should return the number of different values of , such that Aunty can pack
bags of biscuits, each one having a total tastiness of .
The procedure is called a total of times (see Constraints and Subtasks sections for the
allowed values of ). Each of these calls should be treated as a separate scenario.
Examples
Example 1
Consider the following call:
count_tastiness(3, [5, 2, 1])
This means that Aunty wants to pack bags, and there are types of biscuits in the pantry:
biscuits of type , each having a tastiness value ,
Biscuits (1 of 3)

biscuits of type , each having a tastiness value ,
biscuit of type , having a tastiness value .
The possible values of are
. For instance, in order to pack bags of total tastiness ,
Aunty can pack:
one bag containing three biscuits of type , and
two bags, each containing one biscuit of type and one biscuit of type .
Since there are possible values of , the procedure should return .
Example 2
Consider the following call:
count_tastiness(2, [2, 1, 2])
This means that Aunty wants to pack bags, and there are types of biscuits in the pantry:
biscuits of type , each having a tastiness value ,
biscuit of type , having a tastiness value ,
biscuits of type , each having a tastiness value .
The possible values of are
. Since there are possible values of , the procedure
should return .
Constraints
(for all
)
Biscuits (2 of 3)

For each call to count_tastiness, the sum of tastiness values of all biscuits in the pantry
does not exceed
.
Subtasks
1. (9 points)
, and for each call to count_tastiness, the sum of tastiness values of all
biscuits in the pantry does not exceed
.
2. (12 points)
,
3. (21 points)
,
4. (35 points) The correct return value of each call to count_tastiness does not exceed
.
5. (23 points) No additional constraints.
Sample grader
The sample grader reads the input in the following format. The first line contains an integer . After
that, pairs of lines follow, and each pair describes a single scenario in the following format:
line :
line :
The output of the sample grader is in the following format:
line (
): return value of count_tastiness for the -th scenario in the input.
Biscuits (3 of 3)

Input / Output on this judge

This is the IOI function-implementation task biscuits adapted to standard input / output. Instead of implementing the function, read its arguments from standard input and print the returned value(s) to standard output, exactly as the official grader below does (its internal anti-cheat checks have been removed). You may also simply submit the grader together with your own implementation of the function.

Function signature (biscuits.h):

#include <vector>

long long count_tastiness(long long x, std::vector<long long> a);

Reference I/O driver (official grader, sanitized):

#include "biscuits.h"
#include <cassert>
#include <cstdio>

using namespace std;

int main() {
    int q;
    assert(scanf("%d", &q) == 1);
    vector<int> k(q);
    vector<long long> x(q);
    vector<vector<long long>> a(q);
    vector<long long> results(q);
    for (int t = 0; t < q; t++) {
        assert(scanf("%d%lld", &k[t], &x[t]) == 2);
        a[t] = vector<long long>(k[t]);
        for (int i = 0; i < k[t]; i++) {
            assert(scanf("%lld", &a[t][i]) == 1);
        }
    }
    fclose(stdin);

    for (int t = 0; t < q; t++) {
        results[t] = count_tastiness(x[t], a[t]);
    }
    for (int t = 0; t < q; t++) {
        printf("%lld\n", results[t]);
    }
    fclose(stdout);
    return 0;
}

rip 작성

출처 IOI 2020