No.8113 How Many Liars Are There?
タグ : / 解いたユーザー数 5
作問者 : 👑 獅子座じゃない人 / テスター : 👑 seekworser
問題文
$2N$ 人の人がいて、順に人 $i\ (1\leq i\leq 2N)$ とします。
人 $i$ は、それぞれ正直者と嘘つきのどちらかです。
人 $i\ (1\leq i\leq N)$ は、それぞれ人 $P_i\ (1\leq P_i\leq N,\ i\neq P_i)$ が正直者か嘘つきかどうかを言います。
人 $i$ が正直者の場合、人 $P_i$ が正直者であれば「人 $P_i$ は正直者である」と言い、人 $P_i$ が嘘つきであれば「人 $P_i$ は嘘つきである」と言います。
一方、人 $i$ が嘘つきの場合、人 $P_i$ が正直者であれば「人 $P_i$ は嘘つきである」と言い、人 $P_i$ が嘘つきであれば「人 $P_i$ は正直者である」と言います。
また、人 $(i+N)\ (1\leq i\leq N)$ は、それぞれ人 $i$ の発言の内容を言います。
人 $(i+N)$ が正直者の場合、人 $i$ が「人 $P_i$ は正直者である」と言えば「人 $i$ は『人 $P_i$ は正直者である』と言った」と言い、人 $i$ が「人 $P_i$ は嘘つきである」と言えば「人 $i$ は『人 $P_i$ は嘘つきである』と言った」と言います。
一方、人 $(i+N)$ が嘘つきの場合、人 $i$ が「人 $P_i$ は正直者である」と言えば「人 $i$ は『人 $P_i$ は嘘つきである』と言った」と言い、人 $i$ が「人 $P_i$ は嘘つきである」と言えば「人 $i$ は『人 $P_i$ は正直者である』と言った」と言います。
以下の条件をともに満たすように、それぞれの人 $i\ (\boldsymbol{1}\leq i\leq \boldsymbol{2N})$ に正直者であるか嘘つきであるかを割り当てられるならばYes
を、どのように割り当てても条件(の少なくとも片方)を満たさないならばNo
を出力してください。
- 与えられる $A_i\ (1\leq i\leq N)$ について、 $A_i=0$ ならば人 $(i+N)$ が「人 $i$ は『人 $P_i$ は正直者である』と言った」と言うように、 $A_i=1$ ならば人 $(i+N)$ が「人 $i$ は『人 $P_i$ は嘘つきである』と言った」と言うように割り当てられている。
- 与えられる $K$ について、人 $i\ (\boldsymbol{1}\leq i\leq \boldsymbol{2N})$ のなかに嘘つきはちょうど $K$ 人いる。
入力
$N\ K$ $P_1\ P_2\ P_3\ \ldots\ P_N$ $A_1\ A_2\ A_3\ \ldots\ A_N$
- 入力は全て整数
- $2\leq N\leq 1000$
- $0\leq K\leq 2N$
- $1\leq P_i\leq N\ (1\leq i\leq N)$
- $i\neq P_i\ (1\leq i\leq N)$
- $A_i\in\{0,1\}\ (1\leq i\leq N)$
出力
条件を満たすように正直者であるか嘘つきであるかを割り当てられるならばYes
を、割り当てられないならばNo
を出力し、最後に改行してください。
サンプル
サンプル1
入力
3 5 2 3 1 0 0 1
出力
Yes
人 $1,3,4,5,6$ が嘘つきである場合を考えます。
人 $1$ は「人 $2$ は嘘つきである」と言い、人 $2$ は「人 $3$ は嘘つきである」と言い、人 $3$ は「人 $1$ は正直者である」と言います。
したがって、人 $4$ は「人 $1$ は『人 $2$ は正直者である』と言った」と言い、人 $5$ は「人 $2$ は『人 $3$ は正直者である』と言った」と言い、人 $6$ は「人 $3$ は『人 $1$ は嘘つきである』と言った」と言います。
これは条件を満たす割り当て方となっているため、Yes
を出力します。
$0\leq K\leq 2N$ に注意してください。
サンプル2
入力
2 0 2 1 0 1
出力
No
全ての人が正直者である場合、 $A_1=0,\ A_2=1$ の条件を満たすことはありません。
サンプル3
入力
10 16 2 3 1 5 4 7 8 6 6 8 0 1 0 1 0 1 0 1 0 1
出力
Yes
サンプル4
入力
10 17 2 3 1 5 4 7 8 6 6 8 0 1 0 1 0 1 0 1 0 1
出力
No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。