안녕하세요 aim_higher입니다.
Code Force Round #804(Div. 2) 코드 검토 및 해결.
A. 세 번째 세 개의 숫자 문제
https://codeforces.com/contest/1699/problem/A
- 수학
문제의 핵심은 n이 입력되었을 때,
(a ⊕ b)+(b ⊕ c)+(a ⊕ c) = n이 되도록 a, b 및 c를 작성하십시오.
먼저 a, b 및 c의 마지막 비트에 주의를 기울여야 합니다.
즉, a, b 또는 c가 짝수인지 홀수인지에 따라 결과가 홀수인지 짝수인지 확인합니다.
i) 홀수가 0인 경우
(0 ⊕ 0)+(0 ⊕ 0)+(0 ⊕ 0) = 짝수ii) 홀수가 1인 경우
(1 ⊕ 0)+(0 ⊕ 0)+(1 ⊕ 0) = 짝수iii) 홀수가 2일 때
(1 ⊕ 1)+(1 ⊕ 0)+(1 ⊕ 0) = 짝수iv) 홀수가 3개인 경우
(1 ⊕ 1)+(1 ⊕ 1)+(1 ⊕ 1) = 짝수
결론은 모든 숫자가 짝수이기 때문에 홀수는 불가능하다는 것입니다.
처음으로 돌아가 문제에서 a, b, c를 찾으려면
우리는 XOR의 기본 법칙을 명확히 할 필요가 있습니다.
- 0^n = n : 0은 XOR 연산에서 n값에 영향을 주지 않으므로 n값을 그대로 출력한다.
- n^n = 0 : n과 n이 같으므로 차이가 필요한 XOR은 0이 됩니다.
a,b,c는 어차피 서로 잡아먹는 관계니까
공정하게 하기 위해 a = 0 및 b = c로 설정하겠습니다.
표현을 다시 정리하면 (0 ⊕ b) + (b ⊕ b) + (0 ⊕ b) = 2*(0 ⊕ b)
즉, 2*b = n을 만족하는 b를 찾으면 됩니다.
(a = 0, c = b)
위의 공식은 또한 n이 짝수임을 증명합니다.
따라서 정답은 a = 0, b = n/2, c = n/2입니다.
B. 거의 삼항 행렬
https://codeforces.com/contest/1699/problem/B
- 건설적인
각 사각형에 대해 자신의 타일과 다른 색상의 인접한 타일
요점은 정확히 두 가지 상태를 포함하는 방식으로 행렬을 구성하는 것입니다.
입력에 대한 추가 사양은 다음과 같습니다.
- n과 m은 짝수입니다.
그렇게 하면서 타일을 2×2 단계로 지켜봐야 합니다.
그리고 테스트 케이스는 다음과 같은 결과를 보여줍니다.
n=2, m=2일 때 아래와 같은 타일 패턴이 나타납니다.
