No.1568 Sushi
タグ : / 解いたユーザー数 4
作問者 :
KoD
PCTprobability
Problem Statement
Sushi-Toruna-kun runs a conveyor belt sushi restaurant, where sushi is delivered to customers by a circular lane.
The length of the lane is $L$, and it rotates at a speed of length $1$ per $1$ second.
Initially, the lane rotates counterclockwise, but there are $N$ moments at which its direction of movement is reversed.
The $i \, (1 \leq i \leq N)$-th reversal occurs at time $A_i$.
Also, $L$ chairs are arranged at equal intervals around the lane, numbered $0, 1, 2, \dots, L - 1$ in counterclockwise order.
As training for responding quickly to customers' orders, Sushi-Toruna-kun has decided to conduct a thought experiment consisting of $Q$ rounds.
In the $i \, (1 \leq i \leq Q)$-th thought experiment, a customer arrives in front of chair $x_i$ at time $t_i$.
At any time at or after time $t_i$ (the very moment the customer arrives is also allowed), Sushi-Toruna-kun can place the ordered sushi on the lane in front of chair $0$.
The customer can take the sushi at the moment it comes right in front of them. This may be the very moment the customer arrives, or the very moment Sushi-Toruna-kun places the sushi.
Sushi-Toruna-kun wants to find the minimum time from the customer's arrival until the customer takes the sushi, when he places the sushi at the optimal time.
However, the input does not give the values of $x_i, t_i$ directly. Instead, integers $B_i, C_i$ for computing these values are given, so determine $x_i, t_i$ as follows.
(Original idea: harady)
Input
$L\, N\, Q$ $A_1 \, A_2 \, A_3 \, \dots \, A_N$ $B_1 \, C_1$ $B_2 \, C_2$ $\vdots$ $B_Q \, C_Q$
Output
Output $Q$ lines in total. On the $i \,\, (1\leq i \leq Q)$-th line, output the answer to the $i$-th thought experiment. Print a newline at the end.
Sample
Sample 1
Input
10 3 3 1 5 16 8 0 2 5 3 9
Output
3 5 4
First, in the $1$-st thought experiment, $x=8,t=0$. In this case, placing the sushi at time $1$ makes it reach the customer at time $3$, and this is optimal. Therefore, output $3$.
In the $2$-nd thought experiment, $x=5,t=8$. In this case, placing the sushi at time $8$ makes it reach the customer at time $13$, and this is optimal. Therefore, output $5$.
In the $3$-rd thought experiment, $x=8,t=14$. In this case, placing the sushi at time $16$ makes it reach the customer at time $18$, and this is optimal. Therefore, output $4$.
Sample 2
Input
20 2 1 5 6 7 0
Output
9
It is optimal to place the sushi at time $0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。