| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 57 | 18 | 15 | 28.302% |
Adrian owns a stock that he previously purchased, and wants to sell that stock. Currently, at day $0$, the price of the stock is $P_0$. As a robot, Morgan can predict the future. Morgan tells Adrian that the price changes will repeat every $N$ days.
Formally, suppose that the price change from day $i$ to day $i + 1$ for $0 ≤ i ≤ N - 1$ is $D_i$. The price change from day $i$ to $i + 1$ for $i ≥ N$ is $D_i = D_{i \bmod N}$. The price of the stock at day $i$ for $i > 0$ is $P_i = P_{i-1} + D_{i-1}$. It is possible for a price to be negative.
Moreover, Morgan also knows that the price is on a downward trend. That is, the sum of all $D_i$ is negative.
The following table is the stock price of each day if $N = 6$, $P_0 = 20$, and $D_{0..5} = [4, -6, -1, 4, -9, -2]$.
| Day | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ | $16$ | $17$ | $\dots$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Price | $20$ | $24$ | $18$ | $17$ | $21$ | $12$ | $10$ | $14$ | $8$ | $7$ | $11$ | $2$ | $0$ | $4$ | $-2$ | $-3$ | $1$ | $-8$ | $\dots$ |
Adrian can only sell the stock when the price is at least $X$, the price when he purchased the stock, to avoid any losses. As a thrill seeker, Adrian also would like to sell his stock at the lowest price possible while still being at least $X$.
Help Adrian to determine the lowest price of the stock that is not lower than $X$, or tell him if it is impossible. Note that Adrian can sell his stock at day $0$, if $P_0 ≥ X$.
Input begins with three integers $N$ $P_0$ $X$ ($1 ≤ N ≤ 100\, 000$; $1 ≤ P_0, X ≤ 10^9$) representing the number of days in a cycle, the price at day $0$, and the price when Adrian purchased the stock, respectively. The next line contains $N$ integers $D_i$ ($-10^9 ≤ D_i ≤ 10^9$) representing the price changes that repeat every $N$ days. It is guaranteed that the sum of all $D_i$ is negative.
If a price not lower than $X$ exists, output an integer in a single line representing the lowest price of the stock that is not lower than $X$. Otherwise, output -1 in a single line.
6 20 5 4 -6 -1 4 -9 -2
7
The table in the description represents this example. The lowest price of the stock that is not lower than $5$ is $P_9 = 7$.
6 20 1 4 -6 -1 4 -9 -2
1
The lowest price of the stock that is not lower than $1$ is $P_{16} = 1$.
1 3 4 -1
-1
The current price, $P_0$, is $3$ and for any subsequent day, the price will never go up. Thus, it is impossible for the price to reach at least $X = 4$.
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2022 F번
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2023 연습 세션 PC번