시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 86 26 24 30.380%

문제

Aunty Khong is organising a competition with $x$ participants, and wants to give each participant a bag of biscuits. There are $k$ different types of biscuits, numbered from $0$ to $k-1$. Each biscuit of type $i$ ($0 \leq i \leq k-1$) has a tastiness value of $2^i$. Aunty Khong has $a[i]$ (possibly zero) biscuits of type $i$ 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 $i$ in all the bags must not exceed $a[i]$. 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 $y$ exist, such that it is possible to pack $x$ bags of biscuits, each having total tastiness equal to $y$. 

구현

You should implement the following proceedure:

int64 count_tastiness(int64 x, int64[] a)
  • $x$: the number of bags of biscuits to pack.
  • $a$: an array of length $k$. For $0 \leq i \leq k-1$, $a[i]$ denotes the number of biscuits of type $i$ in the pantry.
  • The procedure should return the number of different values of $y$, such that Aunty can pack $x$ bags of biscuits, each one having a total tastiness of $y$.
  • The procedure is called a total of $q$ times (see Constraints and Subtasks sections for the allowed values of $q$). Each of these calls should be treated as a separate scenario.

제한

  • $1 \leq k \leq 60$
  • $1 \leq q \leq 1000$
  • $1 \leq x \leq 10^{18}$
  • $0 \leq a[i] \leq 10^{18}$ (for all $0 \leq i \leq k-1$)
  • For each call to count_tastiness, the sum of tastiness values of all biscuits in the pantry does not exceed $10^{18}$.

예시 1

Consider the following call:

count_tastiness(3, [5, 2, 1])

This means that Aunty wants to pack $3$ bags, and there are $3$ types of biscuits in the shop:

  • $5$ biscuits of type $0$, each having a tastiness value $1$,
  • $2$ biscuits of type $1$, each having a tastiness value $2$,
  • $1$ biscuit of type $2$, each having a tastiness value $4$.

The possible values of $y$ are $[0, 1, 2, 3, 4]$. For instance, in order to pack $3$ bags of total tastiness $3$, Aunty can pack:

  • one bag containing three biscuits of type $0$, and
  • two bags, each containing one biscuit of type $0$ and one biscuit of type $1$. 

Since there are $5$ possible values of $y$, the procedure should return $5$.

예시 2

Consider the following call:

count_tastiness(2, [2, 1, 2])

This means that Aunty wants to pack $2$ bags, and there are $3$ types of biscuits in the shop:

  • $2$ biscuits of type $0$, each having a tastiness value $1$,
  • $1$ biscuits of type $1$, each having a tastiness value $2$,
  • $2$ biscuits of type $2$, each having a tastiness value $4$.

The possible values of $y$ are $[0,1,2,4,5,6]$. Since there are $6$ possible values of $y$, the procedure should return $6$.

서브태스크

번호 배점 제한
1 9

$q \leq 10$, and for each call to count_tastiness, the sum of tastiness values of all biscuits in the pantry does not exceed $100\;000$.

2 12

$x = 1$, $q \leq 10$

3 21

$x \leq 10\;000$, $q \leq 10$

4 35

The correct return value of each call to count_tastiness does not exceed $200\;000$.

5 23

No additional constraints.

첨부

출처

Olympiad > International Olympiad in Informatics > IOI 2020 > Day 2 4번

  • 문제를 만든 사람: Mikhail Tikhomirov

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.