No.2698 Many Asakatsu
タグ : / 解いたユーザー数 16
作問者 :
KowerKoint2010
timi
hibit_at
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$.
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$ |
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 6He 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もしくは右上の雲マークをクリックしてアカウントを作成してください。