레이팅 미적용설명
참고: 이 문제의 시간 제한은 4초로, 기본값의 두 배이다.
베시는 잠들고 싶지만 농장의 불빛 때문에 잠을 이루지 못하고 있다. 어떻게 하면 불을 끌 수 있을까?
베시에게는 길이 \(N\) (\(2\le N\le 20\))의 비트 문자열이 두 개 있는데, 각각 전등의 나열과 스위치의 나열을 나타낸다. 각 전등은 켜져 있거나(1) 꺼져 있다(0). 각 스위치는 활성(1)이거나 비활성(0)이다.
이동(move)은 다음의 연산 순서로 이루어진다.
- 정확히 하나의 스위치를 토글한다 (비활성이면 활성으로, 또는 그 반대로 설정한다).
- 활성인 각 스위치에 대해, 대응하는 전등의 상태를 토글한다 (켜져 있으면 끄고, 또는 그 반대로 한다).
- 스위치들을 오른쪽으로 한 칸 순환 이동한다. 구체적으로, 스위치에 해당하는 비트 문자열이 처음에 \(s_0s_1\dots s_{N-1}\)이었다면 \(s_{N-1}s_0s_1\dots s_{N-2}\)가 된다.
위 문제의 \(T\) (\(1\le T\le 2\cdot 10^5\))개의 인스턴스에 대해, 모든 전등을 끄는 데 필요한 최소 이동 횟수를 구하여라.
Problem credits: William Yue, Eric Yang, and Benjamin Qi
제약
채점 방식
- 입력 3-5: \(N \le 8\)
- 입력 6-13: \(N\le 18\)
- 입력 14-20: 추가 제약이 없다.
Problem credits: William Yue, Eric Yang, and Benjamin Qi
입력 형식
첫째 줄에 \(T\)와 \(N\)이 주어진다.
다음 \(T\)개의 줄에는 각각 길이 \(N\)의 비트 문자열 한 쌍이 주어진다.
출력 형식
각 쌍에 대해, 모든 전등을 끄는 데 필요한 최소 이동 횟수를 출력한다.
예제 1
입력
4 3
000 101
101 100
110 000
111 000출력
0
1
3
2설명
- First test case: the lights are already all off.
- Second test case: We flip the third switch on the first move.
- Third test case: we flip the first switch on the first move, the second switch on the second move, and the second switch again on the third move.
- Fourth test case: we flip the first switch on the first move and the third switch on the second move.
It can be shown that in each case this is the minimal number of moves necessary.
예제 2
입력
1 10
1100010000 1000011000출력
2설명
It can be shown that \(2\) moves are required to turn all lights off.
- We flip the seventh switch on the first move and then again on the second move.
문제 정보
태그