Linear-Feedback Shift Register
면접 대비시간 제한1.5초메모리 제한256 MB
36비트 LFSR의 피드백 계수와 최대 64개의 출력 비트가 주어질 때, 이를 만들어 내는 초기 상태가 있는지 판정하고 사전순으로 가장 앞선 초기 상태를 출력한다.
문제
LFSR(Linear-Feedback Shift Register)을 알고 있는가? LFSR은 의사 난수 값을 생성하는 데에도 쓰인다. 여기서는 LFSR의 자세한 설명은 생략하고, 수식으로 간단히 정의한다. 이 문제에서 다루는 LFSR은 36-bit LFSR이다.
LFSR은 초기값 r0 ~ r35(ri = 0 or 1)와, 다음 Output이 어떤 값들의 XOR로 이루어지는지 정의하는 값 a0 ~ a35(ai = 0 or 1)로 정의된다. LFSR의 Output들은 r36부터의 r 값들이다. r36 이후의 r 값들은 다음과 같이 정의된다. (k는 0 이상의 정수)
rk+36 = (a35 · rk+35) ⊗ (a34 · rk+34) ⊗ ... ⊗ (a0 · rk)
(Bitwise AND는 ·, Bitwise XOR은 ⊗로 표기했다.)
이 문제에서 묻는 것은 a0 ~ a35가 주어져 있을 때, N개의 Output, 즉 r36부터 r35+N까지의 값을 보고 이를 만족하는 초기값 r0 ~ r35이 있는지 답하는 것이다.
입력
첫 번째 줄에 a0 ~ a35가 띄어쓰기를 사이에 두고 주어진다.
두 번째 줄에 입력으로 들어올 Output의 개수 N(1 ≤ N ≤ 64)이 주어진다.
세 번째 줄에 r36 ~ r35+N이 띄어쓰기를 사이에 두고 주어진다.
출력
첫 번째 줄에 가능한 r0 ~ r35가 존재하는지의 여부를 YES 혹은 NO로 출력한다. YES라면 두 번째 줄에 가능한 r0 ~ r35 조합 중 r0r1r2...r35가 사전순으로 가장 빠른 조합을 r0, r1, ... , r35 순서대로 띄어쓰기를 사이에 두고 출력한다. 000...000이 가장 사전 순으로 빠르며, 111...111이 가장 사전 순으로 느리다.
힌트
첫 번째 예제는 r36 = r35 ⊗ r34 ⊗ r33 = 1, r37 = r36 ⊗ r35 ⊗ r34 = 0, r38 = r37 ⊗ r36 ⊗ r35 = 1로 풀어서 쓸 수 있다. 이를 만족하는 r33, r34, r35는 0, 1, 0 뿐이다. r0 ~r32은 어떠한 값이 와도 상관 없다. 그러나 이 중 사전순으로 가장 빠르려면 r0, r1, ... , r32 = 0이어야 한다.
두 번째 예제는 모든 ai 값이 0이기 때문에 가능한 Output은 0뿐이다. 그러나 1이 왔으므로 답은 NO이다.