스위치와 램프
플래티넘 IV의견: 0
\(N\)개의 스위치가 있으며 각각 ON 또는 OFF로 둘 수 있다. \(M\)개의 램프가 있고, 각 램프는 두 조건 중 적어도 하나가 충족되면 켜진다. 램프 하나는 s1 v1 s2 v2로 주어지며, 스위치 \(s1\)이 상태 \(v1\)이거나, 스위치 \(s2\)가 상태 \(v2\)이면 켜진다(\(v\)는 \(0=\)OFF, \(1=\)ON).
모든 램프를 켜는 스위치 배정이 존재하면 가능, 없으면 불가능을 출력한다.
\(1 \le N \le 100{,}000\)
\(0 \le M \le 200{,}000\)
\(1 \le s_1, s_2 \le N\), \(v_1, v_2 \in \{0,1\}\)
첫 줄에 \(N\), \(M\).
이후 \(M\)줄에 s1 v1 s2 v2 (\(1 \le s \le N\), \(v \in \{0,1\}\)).
가능 또는 불가능을 출력한다.
3 2
1 1 2 1
3 0 1 0
가능스위치 3개, 램프 2개. (1=ON 또는 2=ON), (1=OFF 또는 3=OFF). 스위치1=ON, 스위치3=OFF로 두면 두 램프 모두 켜짐 → 가능.
1 2
1 1 1 1
1 0 1 0
불가능스위치 1개, 램프 2개. (1=ON 또는 1=ON) 즉 1=ON 필요, (1=OFF 또는 1=OFF) 즉 1=OFF 필요. 모순 → 불가능.
riseoj 작성
출처 Original
평가 및 의견
스위치와 램프
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
스위치와 램프