7053번 - 시프트 레지스터 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 73 | 18 | 12 | 24.490% |
문제
레지스터는 계산을 하기 위해서 N비트를 저장한다. 시프트 레지스터는 레지스터의 특수한 형태로, 모든 비트를 한 자리씩 시프트 시킬 수 있다.
시프트 레지스터의 결과를 이용해 다음과 같이 바이너리 유사난수를 얻을 수 있다. 크기가 N인 시프트 레지스터에 a1, a2, ..., aN이 저장되어 있다. 클럭틱마다 레지스터는 가장 오른쪽 비트 aN을 출력한다. 다른 비트는 모두 오른쪽으로 한 칸 이동하게 된다. 첫 번째 비트 a′1은 다음과 같은 방법으로 구할 수 있다.
레지스터의 모든 비트는 아래 그림과 같이 스위치를 통해 XOR 게이트와 연결되어 있다. 각각의 비트 i마다 스위치 si(1 또는 0)가 존재하며, 스위치는 ai를 XOR 게이트로 보낼지 말지를 결정하게 된다. ki = si·ai라고 했을 때, a′1은 XOR게이트의 출력값 XOR(k1, ..., kN)이 된다. (k1, ..., kN에서 1의 개수가 홀수개이면 XOR(k1, ..., kN) = 1이고, 아니면 0이다)
- a′1 = XOR(k1, ..., kN)
- a′i = ai-1 for 2 ≤ i ≤ N
- output = aN
위의 예제에서 틱 1에서 a1은 다음과 같이 XOR(1·1, 0·0, 1·1, 1·1, 0·0, 1·0, 1·1) = 0
시프트 레지스터의 결과 중 처음 2N개가 주어진다. 이때, 스위치 값 si를 결정하는 프로그램을 작성하시오.
입력
첫째 줄에 시프트 레지스터의 크기 N이 주어진다. (1 ≤ N ≤ 750) 둘째 줄에는 시프트 레지스터의 결과중 처음 2N개가 주어지며, 0 또는 1이다.
출력
입력으로 주어진 레지스터 출력 결과를 갖는 스위치 세팅이 존재하는 경우에는 si를 공백으로 구분해서 출력하고, 존재하지 않는 경우에는 -1을 출력한다.
가능한 스위치 세팅이 여러 가지인 경우에는 아무거나 출력한다.
예제 입력 1
7 1 0 0 1 1 0 1 0 1 1 0 0 1 1
예제 출력 1
1 0 1 1 0 1 1
출처
Olympiad > Central European Olympiad in Informatics > CEOI 2003 > Day 2 5번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호