#741 (Div.2) C - Rings

문제 링크 => Problem - C - Codeforces

Problem - C - Codeforces

---

problem tags => Constructive algorithms, math

 

길이가 n 인 문자열 s 가 주어질 때, l1, r1, l2, r2 에 대하여 [ l1, r1 ] 에 해당하는 부분 문자열을 t 이라 하고 [ l2, r2 ] 에 해당하는 부분 문자열을 w 라 할 때, f(t) = f(w) * k 를 만족하도록 하는 l1, r1, l2, r2 를 찾는 문제이다.

 

아이디어가 신박한데 문자열 s의 index = 0 부터 접근하여 0인 지점을 발견할 때, 해당 index 값이 n/2 이상인 경우와 미만인 경우를 나눠서 범위를 바로 구할 수 있다.

 

위 방법을 고려하여 101111 와 111101 을 예시로 들어보면 다음과 같다.

 

(1) 101111 인 경우 => index = 1 인 지점에서 0이 발견되었다. 이때, f(01111) = f(1111) * 1 이므로 [ 2, 6 ], [ 3, 6 ] 이 답이 된다.

 

(2) 111101 인 경우 => index = 4 인 지점에서 0이 발견되었다. 이때, f(11110) = f(1111) * 2 이므로 [ 1, 5 ], [ 1, 4 ] 이 답이 된다.

 

즉 0 이 발견될 때, index >= n/2 인 경우 항상 f(t) = f(w) * 2 이고 index < n/2 인 경우 항상 f(t) = f(w) 를 만족한다.

 

0이 발견되지 않는 경우 => 임의로 [ 1, n-1 ], [ 2, n ] 로 잡으면 f(111...11) = f(111...11) 으로 동일하다.

 

풀이 Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

void test() {
	int n;
	string s;
	cin >> n >> s;

	for (int i = 0; i < n; i++) {
		if (s[i] == '0') {
			if (i >= n / 2) {
				cout << 1 << " " << i + 1 << " " << 1 << " " << i << endl;
				return;
			}
			else {
				cout << i + 1 << " " << n << " " << i + 2 << " " << n << endl;
				return;
			}
		}
	}

	cout << 1 << " " << n - 1 << " " << 2 << " " << n << endl;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		test();
	}

	return 0;
}