No.3580 Sum of Two Components
タグ : / 解いたユーザー数 14
作問者 : 👑
Problem Statement
First, $3$ positive integers $N, M, B$ are given.
You are given $M$ conditions, each expressed in the following form using integers $i,j,c$ satisfying $1 \leq i,j \leq N$ and $0 \leq c < B$:
- $X_i + X_j \equiv c \pmod{B}$.
Determine whether there exists a sequence $X$ of non-negative integers of length $N$, with each element less than $B$, that satisfies all $M$ conditions, and if one exists, find $1$ such sequence.
Here, for each positive integer $i$ not exceeding $N$, $X_i$ denotes the $i$-th element of $X$.
Input
For each positive integer $m$ not exceeding $M$, let $i_m,j_m,c_m$ denote the integers $i,j,c$ appearing in the $m$-th condition.
The input is given from standard input in $1 + M$ lines in the following format:
- Line $1$ contains $N, M, B$, separated by single-byte spaces.
- For each positive integer $m$ not exceeding $M$, line $1 + m$ contains $i_m,j_m,c_m$, separated by single-byte spaces.
$N$ $M$ $B$ $i_1$ $j_1$ $c_1$ $\vdots$ $i_M$ $j_M$ $c_M$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^3$.
- $M$ is an integer satisfying $1 \leq M \leq 10^3$.
- $B$ is an integer satisfying $1 \leq B \leq 10^3$.
- For every positive integer $m$ not exceeding $M$:
- $i_m$ is an integer satisfying $1 \leq i_m \leq N$.
- $j_m$ is an integer satisfying $1 \leq j_m \leq N$.
- $c_m$ is an integer satisfying $0 \leq c_m < B$.
Output
If no $X$ satisfying the conditions exists, print No.
No
If one exists, find $1$ such $X$, print Yes on line $1$, and on line $2$ print $X_i$ for each positive integer $i$ not exceeding $N$, in ascending order of $i$, separated by single-byte spaces.
Yes $X_1$ $\cdots$ $X_N$
Print a newline at the end.
This problem uses a special judge. If there are multiple correct answers, you may print any of them.
However, your output must strictly follow the format described above. For example, the behavior of the judge is not guaranteed if there is extra whitespace.
Sample
Sample 1
Input
1 1 1 1 1 0
Output
Yes 0
The conditions that the integer sequence $X = (X_1)$ of length $N = 1$ must satisfy are
$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 1 \\ X_1 & + & X_1 & \equiv & 0 \pmod {1} \end{array} \right. $
. $X = (0)$ indeed satisfies all of these conditions.
Sample 2
Input
1 1 2 1 1 1
Output
No
The conditions that the integer sequence $X = (X_1)$ of length $N = 1$ must satisfy are
$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 2 \\ X_1 & + & X_1 & \equiv & 1 \pmod {2} \end{array} \right. $
. No $X$ satisfies all of these conditions.
Sample 3
Input
2 1 3 1 2 0
Output
Yes 0 0
The conditions that the integer sequence $X = (X_1,X_2)$ of length $N = 2$ must satisfy are
$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 3 \\ 0 & \leq & X_2 & < & 3 \\ X_1 & + & X_2 & \equiv & 0 \pmod {3} \end{array} \right. $
. $X = (0,0)$ indeed satisfies all of these conditions. Besides this,
Yes 1 2
and others are also accepted as correct.
Sample 4
Input
2 2 4 1 2 0 1 2 1
Output
No
The conditions that the integer sequence $X = (X_1,X_2)$ of length $N = 2$ must satisfy are
$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 4 \\ 0 & \leq & X_2 & < & 4 \\ X_1 & + & X_2 & \equiv & 0 \pmod {4} \\ X_1 & + & X_2 & \equiv & 1 \pmod {4} \end{array} \right. $
. No $X$ satisfies all of these conditions.
Sample 5
Input
3 3 5 1 2 1 2 3 3 3 1 4
Output
Yes 1 0 3
The conditions that the integer sequence $X = (X_1,X_2,X_3)$ of length $N = 3$ must satisfy are
$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 5 \\ 0 & \leq & X_2 & < & 5 \\ 0 & \leq & X_3 & < & 5 \\ X_1 & + & X_2 & \equiv & 1 \pmod {5} \\ X_2 & + & X_3 & \equiv & 3 \pmod {5} \\ X_3 & + & X_1 & \equiv & 4 \pmod {5} \end{array} \right. $
. $X = (1,0,3)$ indeed satisfies all of these conditions.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。