Codeforces Round #741 (Div. 2)-C. Rings

문제 설명

수인은 길이가 $n$인 문자열 $s$를 생각하고 있다.

수인은 마법의 함수 $f$를 알고있다. 이 함수는 이진수로 나타낸 문자열을 입력으로 받고 이진수를 십진수로 바꾼 값을 출력으로 한다. 예를 들면 $f(001010) = 10, f(111) = 7, f(11011101) = 221$

그러나 수인은 다음 조건을 만족하는 두 개의 정수로 이루어진 2쌍 $(l_1, r_1), (l_2, r_2)$을 구하고 싶다.

• $1 \le l_1 \le n,; 1 \le r_1 \le n,; r_1 - l_1 + 1 \le [\frac{n}{2}]$
• $1 \le l_2 \le n,; 1 \le r_2 \le n,; r_2 - l_2 + 1 \le [\frac{n}{2}]$
• $(1_1, r_1)$ 과 $(l_2, r_2)$ 는 다르다. 즉 $l_1 \neq l_2$ 이거나 $r_1 \neq r_2$이거나 둘다 같으면 안된다.
• $s$의 부분 문자열 $s[l_1:r_1]$ 을 $t$라고 하고, $s$의 부분문자열 $s[l_2:r_2]$ 을 $w$라고 하자. 그러면 $f(t) = f(w) \cdot k$ 를 만족하는 음이 아닌 정수 $k$가 존재해야한다.

부분 문자열 $s[l:r]$은 $s_ls_{l+1}...s_{r-1}s_r$을 의미한다.

우리가 해야할 것은 수인이 2개의 쌍을 찾도록 하는 것이다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^3)$이 주어진다.

각 테스트 케이스의 첫번째 줄에는 주어진 문자열의 길이를 나타내는 양의 정수 $n (2 \le k \le 2 \cdot10^4)$가 주어진다.

두번째 줄에는 길이가 $n$인 문자열이 주어진다.

Output
각 테스트케이스마다 첫번째 부분 문자열의 시작점, 첫번째 부분문자열의 끝점, 두번재 부분 문자열의 시작점, 두번째 부분문자열의 끝점을 나타내는 4개의 정수 $l_1, r_1, l_2, r_2$를 출력한다.

Example
input
7
6
101111
9
111000111
8
10000000
5
11011
6
001111
3
101
30
100000000000000100000000000000

output
3 6 1 3
1 9 4 9
5 8 1 4
1 5 3 5
1 6 2 4
1 2 2 3
1 15 16 30

문제 접근

사용한 알고리즘: 구현, 수학, 구성적
걸린 시간 : 00:15
와 진짜 풀이 보고 허탈하다는 문제는 이 문제가 처음인것 같았다. 이런 느낌이 드는 문제가 바로 이 구성적 알고리즘을 쓰는 문제인것 같다. 풀이 방법이 떠오르면 금방 풀지만 안떠오르면 절대 안풀리는 마성의 문제.... 풀이 시작하겠다.

처음에 생각해 볼 수 있는 문제는 $k$를 최대한 간단한 수로 표현할 수 없을까? 라는 것이다.

• $k = 1$ 이면 $t$와 $w$이 같은 경우이다.
• $k = 2$ 이면 $t$와 $w$가 2만큼 차이나는 경우이다.

여기서 비트 연산은 왼쪽으로 한 비트 이동하고 남은 비트를 $0$ 으로 채우면 $2$로 곱한 값과 같고, 오른쪽으로 한 비트를 이동하면 $2$로 나눈 값과 같다는 점을 알면 문제를 어떻게 풀지 감이 잡힐 것이다.

먼저 모두 $1$로 이루어진 문자열을 생각할 수 있다. 그러면 여러가지 방법이 있지만 그냥 두 부분 문자열이 서로 같아서 $k$를 1로 만드는것이 제일 간단하지 않을까? 첫번째 조건과 2번째 조건을 만족하기 위해서 그냥 최대한 멀리 떨어트리면 된다고 간단하게 생각하면 된다. 어렵게 생각하지 말자.
따라서 이 경우는 첫번째부터 $n - 1$까지, 두번째부터 $n$까지의 부분 문자열을 가져오면 두 수가 모두 같으면서 길이까지 모두 같고, 모든 조건을 만족한다.

이번에는 문자열에 $0$이 존재하는 경우를 생각해보자. 위에서 언급한 첫번째 조건과 두번째 조건은 두 index가 서로 절반을 기준으로 떨어져 있어야 한다는 뜻이다. 그렇다면 $0$도 서로 절반을 기준으로 경우를 나눌 수 있지 않을까?

• 절반을 기준으로 왼쪽에 0이 있는 경우: 0의 위치를 $p$라고 할 때, $t[p:n], w[p + 1:n]$으로 선택한다. 왜냐하면 맨 앞에 나오는 0은 무시하기 때문이다. $l_1 \neq l_2$이기 때문에 문제 조건에 만족하고 길이는 다르지만 서로 같은 값을 가지고 있기 때문에 $k = 1$이다.
• 절반을 기준으로 오른쪽에 0이 있는 경우: 0의 위치를 $p$라고 할 때, $t[1:p], w[1:p - 1]$으로 선택한다. 이 경우 때문에 위에서 2를 곱하는 비트연산의 성질을 알려준 것이다. 비트에 2를 곱하면 왼쪽으로 1칸 이동하고, 빈 자리에 $0$을 채워넣기 때문에 $w$에 2를 곱한 값이 $w$의 맨 마지막에 $0$을 붙인 $t$가 된다. 따라서 $k = 2$이다.

정답 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        string str; cin >> str;
        int idx = -1;
        for(int i = 0; i < n; i++) if(str[i] == '0') idx = i;
        if(idx == -1) cout << 1 << " " << n - 1 << " " << 2 << " " << n;
        else{
            if(idx < n / 2) cout << idx + 1 << " " << n << " " << idx + 2 << " " << n;
            else cout << 1 << " " << idx + 1 << " " << 1 << " " << idx;
        }
        cout << "\n";
    } 
    return 0;
}