https://codeforces.com/contest/1562/problem/C
시간 1초, 메모리 256MB

input :

• t (1 ≤ t ≤ 103)
• n (2 ≤ t ≤ 2 * 104)
• non-empty binary string

output :

• For every test case print four integers l1, r1, l2, r2, which denote the beginning of the first substring, the end of the first substring, the beginning of the second substring, and the end of the second substring, respectively.
  각 테스트 케이스에서 l1, r1, l2, r2를 출력하시오.

조건 :

• 연속된 부분문자열을 찾아야 합니다.

• 각 부분문자열을 나타내는 좌표의 경우 절대값의 차이가 (n // 2) - 1보다 크거나 같아야 합니다.

• 그리고 l1과 l2가 다르던지 r1과 r2가 다르던지 둘 중 하나는 만족해야 합니다.

• 각 부분문자열을 이진법으로 해서 계산을 했을 떄 배수관계가 되어야 합니다.

---

일단 k를 생각해볼 떄 가장 쉬운 것은 0, 1이다.
한 쪽이 0이라면 나머지는 생각도 안해도 되고 아니면 동일한 경우를 따지면 된다.

여기서 이진법으로 만들어진 수의 특징을 사용하려면 2까지 쉽게 생각할 수 있다.
1110
111
의 경우 14, 7로 2로 곱해진 상황이다. 그렇기 때문에
동일한 수들에 0하나를 추가하면 되는 거다.

0111
111
의 경우에는 동일한 것이여서 k가 1이 될 수 있고

결국 0을 기준으로 나눌 수 있다.
.. 그렇다

---

2022.01.08

다시 봐도 잘 이해가 되지 않는 문제이다. 암튼 포인트를 잘 잡아야 할 것 같다. 이진법에 0이 존재한다는 것을 잘 상기해야 겠다.

다음 풀이

1. 이진법의 배수?
2. 부분문자열의 분리?

0을 맨 뒤에 추가한다면? 해당 문자열은 다른거의 2배가 된다. 앞에 추가하면? 다른거의 1배가 된다. 결국 2 방법 중 길이가 (n // 2)보다 큰 것을 찾는다. 이는 0의 위치를 찾는 것과 동일하다.

---

0이 존재하지 않는다면 모두 1로 만들어져 있다 생각하고
1 ~ k - 1, 2 ~ k까지로 답을 보면 된다.
여기서 1 ~ k - 1, 1 ~ k로 한다면 이것은 15, 7의 관계라 볼 수 있다. 그냥 배수 관계를 이루지 못해서 동일한 길이를 가지도록 해야한다.

결국 0의 위치를 찾아서 만약 이게 중간보다 앞에 위치하면
0의 위치 ~ k를 이용해서 답을 구하고
그렇지 않은 경우에는 1 ~ 0의 위치를 이용한다.

0을 하나 추가하는 방식을 사용한다는 것에서 신기했다...

import sys

for _ in range(int(sys.stdin.readline())):
    k = int(sys.stdin.readline())
    data = sys.stdin.readline().rstrip()

    idx = -1
    for i in range(len(data)):
        if data[i] == '0':
            idx = i + 1
            break

    if idx == -1:
        print(f"1 {k - 1} 2 {k}")
    else:
        mid = k // 2
        if idx <= mid:
            print(f"{idx} {k} {idx + 1} {k}")
        else:
            print(f"{1} {idx} {1} {idx - 1}")