No.3580 二成分の和
タグ : / 解いたユーザー数 10
作問者 : 👑
p-adic
問題文
最初に $3$ 個の正整数 $N, M, B$ が与えられます。
$1 \leq i,j \leq N$ かつ $0 \leq c < B$ を満たす整数 $i,j,c$ を用いて
- $X_i + X_j \equiv c \pmod{B}$ である。
と表される条件が $M$ 個与えられるので、各成分が $B$ 未満である長さ $N$ の非負整数列 $X$ であって $M$ 個全ての条件を満たすものが存在するか否かを判定し、存在する場合は $1$ つ求めてください。
ただし $N$ 以下の正整数 $i$ に対し、$X_i$ で $X$ の $i$ 個目の成分を表します。
入力
$M$ 以下の各正整数 $m$ に対し、$m$ 個目の条件に現れる整数 $i,j,c$ を $i_m,j_m,c_m$ と置きます。
この時、入力は以下の形式で標準入力から $1 + M$ 行で与えられます：
- $1$ 行目に $N, M, B$ が半角空白区切りで与えられます。
- $M$ 以下の各正整数 $m$ に対し、$1 + m$ 行目に $i_m,j_m,c_m$ が半角空白区切りで与えられます。
$N$ $M$ $B$ $i_1$ $j_1$ $c_1$ $\vdots$ $i_M$ $j_M$ $c_M$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^3$ を満たす整数である。
- $M$ は $1 \leq M \leq 10^3$ を満たす整数である。
- $B$ は $1 \leq B \leq 10^3$ を満たす整数である。
- $M$ 以下の任意の正整数 $m$ に対し、
- $i_m$ は $1 \leq i_m \leq N$ を満たす整数である。
- $j_m$ は $1 \leq j_m \leq N$ を満たす整数である。
- $c_m$ は $0 \leq c_m < B$ を満たす整数である。
出力
条件を満たす $X$ が存在しない場合はNoと出力してください。
No
存在する場合はそのような $X$ を $1$ つ求め、$1$ 行目にYesと出力して $2$ 行目に $N$ 以下の各正整数 $i$ に対する $X_i$ を $i$ の小さい順に半角空白区切りで出力してください。
Yes $X_1$ $\cdots$ $X_N$
最後に改行してください。
この問題はスペシャルジャッジ問題です。正解が複数ある場合はどれを出力しても構いません。
ただし出力は上述した形式に厳格に従ってください。例えば余計な空白がある場合のジャッジの挙動は保証されません。
サンプル
サンプル1
入力
1 1 1 1 1 0
出力
Yes 0
長さ $N = 1$ の整数列 $X = (X_1)$ が満たすべき条件は
$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 1 \\ X_1 & + & X_1 & \equiv & 0 \pmod {1} \end{array} \right. $
です。$X = (0)$ は確かにこれらの条件を全て満たします。
サンプル2
入力
1 1 2 1 1 1
出力
No
長さ $N = 1$ の整数列 $X = (X_1)$ が満たすべき条件は
$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 2 \\ X_1 & + & X_1 & \equiv & 1 \pmod {2} \end{array} \right. $
です。これらの条件を全て満たす $X$ は存在しません。
サンプル3
入力
2 1 3 1 2 0
出力
Yes 0 0
長さ $N = 2$ の整数列 $X = (X_1,X_2)$ が満たすべき条件は
$\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)$ は確かにこれらの条件を全て満たします。この他に
Yes 1 2
なども正解となります。
サンプル4
入力
2 2 4 1 2 0 1 2 1
出力
No
長さ $N = 2$ の整数列 $X = (X_1,X_2)$ が満たすべき条件は
$\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. $
です。これらの条件を全て満たす $X$ は存在しません。
サンプル5
入力
3 3 5 1 2 1 2 3 3 3 1 4
出力
Yes 1 0 3
長さ $N = 3$ の整数列 $X = (X_1,X_2,X_3)$ が満たすべき条件は
$\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)$ は確かにこれらの条件を全て満たします。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。