No.3230 Mutual Corresponding System
タグ : / 解いたユーザー数 32
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
Problem Statement
$N$ humans $H_1, \dots, H_N$ exchange $M$ letters with one another.
On day $T_n$, to all the others at once, each human $H_n$ sends their $1$st letter.
On the day the following conditions are satisfied, to all the others at once, each human $H_n$ sends their $m+1$-th letter ($m \geq 1$):
- $H_n$ has sent their $m$-th letter on or before that day
- the $m$-th letters from all the other humans $H_{n'} \ (n' \neq n)$ have arrived at $H_n$
For each $n = 1, \dots, N$, find the day on which the $M$-th letters from all the others arrive at human $H_n$.
Input
$N\ M$
$T_1 \ \dots \ T_N$
$A_{1, 1} \ A_{1, 2} \ \dots \ A_{1, N}$
$\vdots$
$A_{N, 1} \ A_{N, 2} \ \dots \ A_{N, N}$
$2 \leq N \leq 10^2,$
$2 \leq M \leq 10^{15},$
$0 \leq T_n \leq 10^3,$
$0 \leq A_{i, j} \leq 10^3,$
$A_{i, i} = 0$
All of the above are integers. $A_{i, i}$ is not used in the problem, but it is given for convenience to keep the input format simple. It is guaranteed that all answers are less than $2^{63}$.
Output
For each $n = 1, \dots, N$, output the day on which the $M$-th letters from all the others arrive at human $H_n$, separated by a single half-width space. Print a newline at the end.
Sample
Sample 1
Input
3 2 0 4 10 0 2 3 9 0 5 1 7 0
Output
26 17 22
The $1$st letter from $H_2$ arrives at $H_1$ on day $4 + 9 = 13$, and the $1$st letter from $H_3$ arrives on day $10 + 1 = 11$. Therefore, $H_1$ sends their $2$nd letter on day $13$.
The $1$st letter from $H_1$ arrives at $H_2$ on day $0 + 2 = 2\ $, and the $1$st letter from $H_3$ arrives on day $10 + 7 = 17$. Therefore, $H_2$ sends their $2$nd letter on day $17$.
The $1$st letter from $H_1$ arrives at $H_3$ on day $0 + 3 = 3\ $, and the $1$st letter from $H_2$ arrives on day $4 + 5 = 9\ $. Therefore, $H_3$ sends their $2$nd letter on day $10$ (note that until they have sent their own $1$st letter, they do not send their $2$nd letter).
The $2$nd letter sent by $H_1$ on day $13$ arrives at $H_2$ on day $13 + 2 = 15$ and arrives at $H_3$ on day $13 + 3 = 16$.
The $2$nd letter sent by $H_2$ on day $17$ arrives at $H_1$ on day $17 + 9 = 26$ and arrives at $H_3$ on day $17 + 5 = 22$.
The $2$nd letter sent by $H_3$ on day $10$ arrives at $H_1$ on day $10 + 1 = 11$ and arrives at $H_2$ on day $10 + 7 = 17$.
Therefore, the $2$nd letters from all the others arrive at $H_1, H_2, H_3$ on days $26, 17, 22$, respectively.
Sample 2
Input
3 3 2 8 9 0 0 0 0 0 0 0 0 0
Output
9 9 9
The $1$st letter from $H_2$ arrives at $H_1$ on day $8 + 0 = 8$, and the $1$st letter from $H_3$ arrives on day $9 + 0 = 9$. Therefore, $H_1$ sends their $2$nd letter on day $9$.
The $1$st letter from $H_1$ arrives at $H_2$ on day $2 + 0 = 2$, and the $1$st letter from $H_3$ arrives on day $9 + 0 = 9$. Therefore, $H_2$ sends their $2$nd letter on day $9$.
The $1$st letter from $H_1$ arrives at $H_3$ on day $2 + 0 = 2$, and the $1$st letter from $H_2$ arrives on day $8 + 0 = 8$. Therefore, $H_3$ sends their $2$nd letter on day $9$ (note that until they have sent their own $1$st letter, they do not send their $2$nd letter).
The $2$nd letter sent by $H_1$ on day $9$ arrives at $H_2$ on day $9 + 0 = 9$ and arrives at $H_3$ on day $9 + 0 = 9$.
The $2$nd letter sent by $H_2$ on day $9$ arrives at $H_1$ on day $9 + 0 = 9$ and arrives at $H_3$ on day $9 + 0 = 9$.
The $2$nd letter sent by $H_3$ on day $9$ arrives at $H_1$ on day $9 + 0$ and arrives at $H_2$ on day $9 + 0$.
The $2$nd letters that $H_1, H_2, H_3$ sent on day $9$ arrive at each of them on day $9$, they send their $3$rd letters on day $9$, and the $3$rd letters arrive at each of them on day $9$.
Note that multiple letters may be sent on the same day.
Sample 3
Input
4 3 2 8 9 13 0 81 72 13 18 0 91 73 89 26 0 42 44 43 29 0
Output
263 269 270 252
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。