問題一覧 > ネタ問題

No.8113 How Many Liars Are There?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 5
作問者 : 👑 獅子座じゃない人 / テスター : 👑 seekworser
お気に入りにしたユーザー ProblemId : 10782 / 自分の提出
問題文最終更新日: 2024-04-01 22:10:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder April Fool Contest 2024 (順位表) の他の問題:

Problem Statement

There are $2N$ people, numbered as person $i\ (1\leq i\leq 2N)$.
Each person $i$ is either an honest person or a liar.

Each person $i\ (1\leq i\leq N)$ states whether person $P_i\ (1\leq P_i\leq N,\ i\neq P_i)$ is honest or a liar.
If person $i$ is honest, then they say "Person $P_i$ is honest" if person $P_i$ is honest, and "Person $P_i$ is a liar" if person $P_i$ is a liar.
On the other hand, if person $i$ is a liar, then they say "Person $P_i$ is a liar" if person $P_i$ is honest, and "Person $P_i$ is honest" if person $P_i$ is a liar.

Also, each person $(i+N)\ (1\leq i\leq N)$ states the content of what person $i$ said.
If person $(i+N)$ is honest, then they say "Person $i$ said 'Person $P_i$ is honest'" if person $i$ says "Person $P_i$ is honest", and "Person $i$ said 'Person $P_i$ is a liar'" if person $i$ says "Person $P_i$ is a liar".
On the other hand, if person $(i+N)$ is a liar, then they say "Person $i$ said 'Person $P_i$ is a liar'" if person $i$ says "Person $P_i$ is honest", and "Person $i$ said 'Person $P_i$ is honest'" if person $i$ says "Person $P_i$ is a liar".

Print Yes if it is possible to assign honest or liar to each person $i\ (\boldsymbol{1}\leq i\leq \boldsymbol{2N})$ so that both of the following conditions are satisfied, and print No if no assignment satisfies the conditions (that is, at least one of them is violated for every assignment).

  • For the given $A_i\ (1\leq i\leq N)$, the assignment is such that person $(i+N)$ says "Person $i$ said 'Person $P_i$ is honest'" if $A_i=0$, and person $(i+N)$ says "Person $i$ said 'Person $P_i$ is a liar'" if $A_i=1$.
  • For the given $K$, there are exactly $K$ liars among the people $i\ (\boldsymbol{1}\leq i\leq \boldsymbol{2N})$.

Input

$N\ K$
$P_1\ P_2\ P_3\ \ldots\ P_N$
$A_1\ A_2\ A_3\ \ldots\ A_N$

  • All inputs are integers.
  • $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)$

Output

Print Yes if it is possible to assign honest or liar so that the conditions are satisfied, and No otherwise, followed by a newline.

Sample

Sample 1
Input
3 5
2 3 1
0 0 1
Output
Yes

Consider the case where persons $1,3,4,5,6$ are liars.
Person $1$ says "Person $2$ is a liar", person $2$ says "Person $3$ is a liar", and person $3$ says "Person $1$ is honest".
Therefore, person $4$ says "Person $1$ said 'Person $2$ is honest'", person $5$ says "Person $2$ said 'Person $3$ is honest'", and person $6$ says "Person $3$ said 'Person $1$ is a liar'".
This assignment satisfies the conditions, so print Yes.

Note that $0\leq K\leq 2N$.

Sample 2
Input
2 0
2 1
0 1
Output
No

If everyone is honest, the condition $A_1=0,\ A_2=1$ can never be satisfied.

Sample 3
Input
10 16
2 3 1 5 4 7 8 6 6 8
0 1 0 1 0 1 0 1 0 1
Output
Yes

Sample 4
Input
10 17
2 3 1 5 4 7 8 6 6 8
0 1 0 1 0 1 0 1 0 1
Output
No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。