Warning: Uninitialized string offset 1 in /usr/local/apache2/htdocs/include/ParsedownExtended/ParsedownExtended.php on line 812
이진수

[2021 SCPC 1차 예선]

이진수

\(n\) 비트로 구성된 이진수 \(A=a_1 a_2 … a_n\) (\(a_i\)는 0 또는 1)와 자연수 \(t\) 가 주어질 때, \(A\)로부터 아래와 같은 연산을 통해 새로운 이진수 \(B=b_1 b_2 …bn\) 를 만든다.



    1. 초기에 \(b_i\ (1 ≤i ≤n)\) 는 모두 0으로 리셋한다.

    2. 만약  \(i>t\) 이고 \(a_{i-t}=1\) 이면 \(b_i \)는 1로 둔다.

    3. 만약  \(i≤n-t\) 이고 \(a\
{i+t}=1\) 이면 \(b_i\) 는 1로 둔다.



예를 들어, 아래 그림에서 보인 것처럼 9 비트로 구성된 이진수 \(A=100100101\) 이고 \(t=2\) 인 경우, 변환을 통해 새로운 이진수 \(B=011011101\) 을 얻을 수 있다.







변환된 이진수 \(B\)와 자연수 \(t\)가 주어질 때, 이 정보로부터 역으로 \(A\)를 유추하는 프로그램을 작성하고자 한다.

예를 들어, 그림에서 보인 것처럼 \(B=011011101\) 이고 \(t=2\) 라면 가능한 \(A\)의 값은 \(100100101,\ 100110101,\ 000110100\) 등이다.



주어진 이진수 \(B\)와 자연수 \(t\)로부터 유추 가능한 \(A\)가 둘 이상일 경우, \(A\)의 값을 이진수로 보았을 때, 가장 작은 값을 출력하는 프로그램을 작성하시오. 주어진 이진수 \(B\)와 자연수 \(t\) 로부터 유추 가능한 \(A\)가 존재하지 않는 경우는 주어지지 않는다.




그림 1

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고,

이후 차례로  \(T\)개의 테스트 케이스가 주어진다. \((1 ≤ T ≤ 64) \)

각 테스트 케이스의 첫 줄에는 변환된 이진수 B의 비트 수를 나타내는 정수 \(n\)과 자연수 \(t\)가 주어진다. \((2≤n≤50,000,1≤t<n)\)

다음 줄에는 길이가 \(n\) 인 이진수가 주어진다.

주어진 이진수 \(B\)와 자연수 \(t\)로부터 유추 가능한 \(A\)가 존재하지 않는 경우는 주어지지 않는다.


출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #\(C\)”를 출력하여야 한다. 이때 \(C\)는 테스트 케이스의 번호이다.

그 다음 줄에, 주어진 이진수 \(B\)와 자연수 \(t\)로부터 유추 가능한 \(A\)중, \(A\)의 값을 이진수로 보았을 때 가장 작은 값을 출력하시오.

입출력예

입력
2
5 1
00111
10 2
1111111000
출력
Case #1
00011
Case #2
0111100000

돌아가기


댓글