問題一覧 > 通常問題

No.2698 Many Asakatsu

レベル : / AI推定難易度 : 2325 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 16
作問者 : karinohito / テスター : KowerKoint2010 timi hibit_at
お気に入りにしたユーザー ProblemId : 10767 / 自分の提出
問題文最終更新日: 2024-03-23 03:08:02
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
yukicoder contest 423 (Asakatsu Presents 3) (順位表) の他の問題:

Problem Statement

The Discord server "Asakatsu" holds $N$ virtual contests of different difficulties to meet diverse demands.
Each contest consists of $M$ problems, and the difficulty of the $j$-th problem of the $i$-th contest is $D_{i,j}$.
Here, it is guaranteed that the following hold for $D_{i,j}$.

  • $D_{i,j}\le D_{i,j+1}$ $(1\le i\le N,\ 1\le j\lt M)$
  • $D_{i,j}\le D_{i+1,j}$ $(1\le i\lt N,\ 1\le j\le M)$
  • For each $i$ $(1\le i\le N)$, $D_{i,1},D_{i,2},\dots,D_{i,M}$ form an arithmetic progression in this order

Note that the input gives only the first term $A_i$ and the common difference $B_i$ of $D_{i}$; the values of $D_{i,j}$ are not given explicitly.

hibit has decided to participate in these contests a total of $Q$ times.
hibit's rating before his $1$-st participation is $X$, and each time he participates in the $i$-th contest, his rating increases by $C_i$.

Each time, hibit participates in the contest with the smallest sum of differences between his rating just before that participation and the difficulties of the problems.
More specifically, let $R$ be hibit's rating before his $q$-th participation, let $d(i)=\sum_{j=1}^{M}|D_{i,j}-R|$, and let $m$ be the minimum value of $d(i)$. Then the $i$ such that $d(i)=m$ is the number of the contest hibit participates in for the $q$-th time.
If there are multiple $i$ such that $d(i)=m$, the smallest of them is the number of the contest he participates in.

For $q=1,2,\dots,Q$, output the number of the contest hibit participates in for the $q$-th time.

Input

$N$ $M$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
$\vdots$
$A_{N}$ $B_{N}$ 
$Q$ $X$
$C_1$ $C_2$ $\dots$ $C_N$

  • All inputs are integers.
  • $2 \leq N\leq 10^5$
  • $2 \leq M\leq 10^9$
  • $1 \leq Q \leq 2\times 10^5$
  • $0 \leq X \leq 10^9$
  • Letting $D_{i,j}=A_{i}+(j-1)B_{i}$, the following hold:
    • $0 \leq D_{i,j} \leq 10^9$ $(1\le i\le N,1\le j\le M)$
    • $D_{i,j}\le D_{i,j+1}$ $(1\le i\le N,\ 1\le j\lt M)$
    • $D_{i,j}\le D_{i+1,j}$ $(1\le i\lt N,\ 1\le j\le M)$
  • $0 \leq C_i \leq 10^9$ $(1\le i\le N)$

Output

Output the answers for $q=1,2,\dots,Q$, separated by spaces.

Sample

Sample 1
Input
3 3
1 2
6 0
7 1
2 4
3 1 4
Output
1 2

The difficulties of the problems in each contest are as follows.

Problem $1$ Problem $2$ Problem $3$
Contest $1$ $1$ $3$ $5$
Contest $2$ $6$ $6$ $6$
Contest $3$ $7$ $8$ $9$
For the $1$-st participation, the sum of differences between the difficulties of the $1$-st contest and the rating is $|1-4|+|3-4|+|5-4|=5$. Similarly, the sums of differences between the difficulties and the rating for the contests $2,3$ are $6$, $12$. The minimum is $5$ for the $1$-st contest, so he participates in the $1$-st contest.
After the $1$-st participation, hibit's rating becomes $4+C_{1}=4+3=7$.
For the $2$-nd participation, the sums of differences between the difficulties and the rating for the contests $1,2,3$ are $12,3,3$, respectively. The minimum is $3$ for the contests $2,3$, so he participates in contest $2$, which has the smaller number.
Sample 2
Input
6 4
0 5
0 6
1 7
6 6
6 10
9 9
5 11
1 12 13 11 25 14
Output
1 1 4 4 6
He may participate in the same contest multiple times, and his rating increases each time even in that case.
Sample 3
Input
4 4
0 0
1 1
3 3
5 5
4 4229
1 10 100 1000
Output
4 4 4 4

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。