34214번 - Souvenirs 서브태스크다국어언어 제한함수 구현

문제

Amaru is buying souvenirs in a foreign shop. There are $N$ types of souvenirs. There are infinitely many souvenirs of each type available in the shop.

Each type of souvenir has a fixed price. Namely, a souvenir of type $i$ (0ドル \leq i < N$) has a price of $P[i]$ coins, where $P[i]$ is a positive integer.

Amaru knows that souvenir types are sorted in decreasing order by price, and that the souvenir prices are distinct. Specifically, $P[0] > P[1] > \cdots > P[N-1] > 0$. Moreover, he was able to learn the value of $P[0]$. Unfortunately, Amaru does not have any other information about the prices of the souvenirs.

To buy some souvenirs, Amaru will perform a number of transactions with the seller.

Each transaction consists of the following steps:

1. Amaru hands some (positive) number of coins to the seller.
2. The seller puts these coins in a pile on the table in the back room, where Amaru cannot see them.
3. The seller considers each souvenir type 0,ドル 1, \ldots, N-1$ in that order, one by one. Each type is considered exactly onceper transaction.
   • When considering souvenir type $i,ドル if the current number of coins in the pile is at least $P[i],ドル then
     • the seller removes $P[i]$ coins from the pile, and
     • the seller puts one souvenir of type $i$ on the table.
4. The seller gives Amaru all the coins remaining in the pile and all souvenirs on the table.

Note that there are no coins or souvenirs on the table before a transaction begins.

Your task is to instruct Amaru to perform some number of transactions, so that:

• in each transaction he buys at least one souvenir, and
• overall he buys exactly $i$ souvenirs of type $i,ドル for each $i$ such that 0ドル \leq i < N$. Note that this means that Amaru should not buy any souvenir of type 0ドル$.

Amaru does not have to minimize the number of transactions and has an unlimited supply of coins.

구현 상세

You should implement the following procedure.

void buy_souvenirs(int N, long long P0)

• $N$: the number of souvenir types.
• $P0$: the value of $P[0]$.
• This procedure is called exactly once for each test case.

The above procedure can make calls to the following procedure to instruct Amaru to perform a transaction:

std::pair<std::vector<int>, long long> transaction(long long M)

• $M$: the number of coins handed to the seller by Amaru.
• The procedure returns a pair. The first element of the pair is an array $L,ドル containing the types of souvenirs that have been bought (in increasing order). The second element is an integer $R,ドル the number of coins returned to Amaru after the transaction.
• It is required that $P[0] > M \geq P[N-1]$. The condition $P[0] > M$ ensures that Amaru does not buy any souvenir of type 0ドル,ドル and $M \geq P[N-1]$ ensures that Amaru buys at least one souvenir. If these conditions are not met, your solution will receive the verdict Output isn't correct: Invalid argument. Note that contrary to $P[0],ドル the value of $P[N-1]$ is not provided in the input.
• The procedure can be called at most 5000ドル$ times in each test case.

The behavior of the grader is not adaptive. This means that the sequence of prices $P$ is fixed before buy_souvenirs is called.

입력

출력

제한

• 2ドル \leq N \leq 100$
• 1ドル \leq P[i] \leq 10^{15}$ for each $i$ such that 0ドル \leq i < N$.
• $P[i] > P[i+1]$ for each $i$ such that 0ドル \leq i < N - 1$.

서브태스크

힌트

예제

Consider the following call.

buy_souvenirs(3, 4)

There are $N = 3$ types of souvenirs and $P[0] = 4$. Observe that there are only three possible sequences of prices $P$: $[4, 3, 2],ドル $[4, 3, 1],ドル and $[4, 2, 1]$.

Assume that buy_souvenirs calls transaction(2). Suppose the call returns $([2], 1),ドル meaning that Amaru bought one souvenir of type 2ドル$ and the seller gave him back 1ドル$ coin. Observe that this allows us to deduce that $P = [4, 3, 1],ドル since:

• For $P = [4, 3, 2],ドル transaction(2) would have returned $([2], 0)$.
• For $P = [4, 2, 1],ドル transaction(2) would have returned $([1], 0)$.

Then buy_souvenirs can call transaction(3), which returns $([1], 0),ドル meaning that Amaru bought one souvenir of type 1ドル$ and the seller gave him back 0ドル$ coins. So far, in total, he has bought one souvenir of type 1ドル$ and one souvenir of type 2ドル$.

Finally, buy_souvenirs can call transaction(1), which returns $([2], 0),ドル meaning that Amaru bought one souvenir of type 2ドル$. Note that we could have also used transaction(2) here. At this point, in total Amaru has one souvenir of type 1ドル$ and two souvenirs of type 2ドル,ドル as required.

샘플 그레이더

Input format:

N
P[0] P[1] ... P[N-1]

Output format:

Q[0] Q[1] ... Q[N-1]

Here $Q[i]$ is the number of souvenirs of type $i$ bought in total for each $i$ such that 0ドル \leq i < N$.

첨부

• souvenirs.zip