시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 256 MB 3 1 1 100.000%

문제

LFSR(Linear-Feedback Shift Register)에 대해서 알고 있는가? LFSR는 의사 난수 값을 생성하는 데 쓰이기도 한다. 이에 대해서 자세히 공부하는 것은 생략하도록 하고, 대신 문제에서는 수식으로 간단하게 정의를 하고자 한다. 문제의 LFSR은 36-bit LFSR이다.

초기값 r0r35(ri = 0 or 1)와, 다음 Output이 어떤 값들의 XOR로 이루어지는지 정의하는 값 a0a35(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은 ⊗로 표기했다.)

이 문제에서 묻고 싶은 것은 a0a35이 주어져 있을 때 N개의 Output들, 즉 r36부터 r35+N 까지의 값들을 보고 이를 만족하는 초기값 r0r35이 있는지 답하는 것이다.

입력

첫 번째 줄에 a0a35가 띄어쓰기를 사이에 두고 주어진다.

두 번째 줄에 입력으로 들어올 Output의 개수 N(1 ≤ N ≤ 64)이 주어진다.

세 번째 줄에 r36r35+N 이 띄어쓰기를 사이에 두고 주어진다.

출력

첫 번째 줄에 가능한 r0r35가 존재하는지의 여부를 YES 혹은 NO로 출력한다. YES라면 두 번째 줄에 가능한 r0 ∼ r35 조합 중 r0r1r2...r35가 사전순으로 가장 빠른 조합을 r0, r1, ... , r35 순서대로 띄어쓰기를 사이에 두고 출력한다. 000...000이 가장 사전 순으로 빠르며, 111...111이 가장 사전 순으로 느리다.

예제 입력 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
3
1 0 1

예제 출력 1

YES
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

예제 입력 2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1
1

예제 출력 2

NO

예제 입력 3

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
64
1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1

예제 출력 3

YES
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

힌트

첫 번째 예제는 r36 = r35 r34 r33 = 1, r37 = r36 r35 r34 = 0, r38 = r37 r36 r35 = 1로 풀어서 쓸 수 있다. 이를 만족하는 r33, r34, r35는 0, 1, 0 뿐이다. r0r32은 어떠한 값이 와도 상관 없다. 그러나 이 중 사전순으로 가장 빠르려면 r0, r1, ... , r32 = 0이여야 한다.

두 번째 예제는 모든 ai 값이 0이기 때문에 가능한 Output은 0뿐이다. 그러나 1이 왔으므로 답은 NO이다.

출처

University > POSTECH > 2019 PPC F번

  • 잘못된 데이터를 찾은 사람: jh05013
  • 문제를 만든 사람: jhs7jhs