問題一覧 > 通常問題

No.1568 Sushi

レベル : / AI推定難易度 : 2325 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 4
作問者 : blackyuki / テスター : KoD PCTprobability
お気に入りにしたユーザー ProblemId : 6306 / 自分の提出
問題文最終更新日: 2021-04-21 09:52:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
灘校文化祭コンテスト 2021 day1 (順位表) の他の問題:

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.

  • For the $1$-st thought experiment, let $x_i = B_i, t_i = C_i$.
  • For the $2$-nd and subsequent thought experiments, let $D$ be the answer to the $i-1$-th thought experiment (it can be proved that this is an integer under the constraints of the problem), and let $x_i = (B_i + D) \bmod L, t_i = (C_i + D) \bmod 10^{15}$.

  • (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$
    
  • All inputs are integers.
  • $1\leq L \leq 10^{15}$
  • $1\leq N \leq 2 \times 10^5$
  • $1\leq Q \leq 2 \times 10^5$
  • $1\leq A_i \leq 10^{15}\ ( 1\leq i \leq N)$
  • $A_i < A_{i+1} \, (1\leq i \leq N-1)$
  • $0 \leq B_i < L \, (1\leq i \leq Q)$
  • $0 \leq C_i < 10^{15} \, (1\leq i \leq 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もしくは右上の雲マークをクリックしてアカウントを作成してください。