양의 정수 N으로 만들어지는 문자열 S_N은 다음과 같이 정의된다. 아래에서 ⌊N/2⌋은 N을 2로 나눈 몫이다. 

1. N = 1인 경우: SN = 1 (즉, 1 한 글자로 이루어진 문자열) 
2. N ≥ 2이고 N이 짝수인 경우: S_N = S_⌊N/2⌋ 0 S_⌊N/2⌋ (즉, 0 한 글자 좌우에 S_⌊N/2⌋가 이어진 문자열) 
3. N ≥ 2이고 N이 홀수인 경우: S_N = S_⌊N/2⌋ 1 S_⌊N/2⌋ (즉, 1 한 글자 좌우에 S_⌊N/2⌋가 이어진 문자열)

  위의 약속에 따라 S₁₃을 구해보면 다음과 같다.

• 위의 약속에서 적용이 가능한 것은 3번이므로 S₁₃ = S₆ 1 S₆임을 알수 있다.
• S₆은 위의 약속의 2번에 의해 S₃ 0 S₃이 되므로 S₁₃ = S₆ 1 S₆ = S₃ 0 S₃ 1 S₃ 0 S₃이다.
• S₃은 위의 약속의 3번과 1번을 순서대로 적용하면 111이 된다.
• 따라서 S₁₃ = 111011111110111이다.

  양의 정수 N이 주어질 때, 아래와 같은 형태의 질의 Q개를 해결하는 프로그램을 작성하라.
  q (1 ≤ q ≤ Q)번째 질의는 세 개의 정수 (i_q, j_q, k_q)가 주어질 때 다음과 같다: S_N [i_q..j_q]에서 0을 최대 k_q 개까지 포함하는 가장 긴 부분문자열의 길이는?
  위의 예에서 질의가 (1, 15, 0)이라면 가장 긴 부분문자열은 1로만 이루어져야 한다. 또, 질의가 S₁₃ 전체에서 찾기를 요구하고 있으므로 해당 문자열의 길이는 7이다.
  만약, (2, 14, 2)이라면 질의는 S₁₃의 두번째부터 14번째 문자까지에서 0이 최대 2개인 가장 긴 부분문자열 을 찾으라고 요구한다. 그런데 S₁₃[2..14] = 1101111111011에는 0이 2개 뿐이므로 그 전체가 답이 되고, 그 길이는 13이다.

참고 

  부분문자열의 정의 길이가 l인 문자열 s와 1 ≤ i ≤ j ≤ l인 두 정수 i와 j에 대해, s[i..j]는 s의 i번째 문자에서부터 j번째 문자까지를 모두 순서대로 포함하는 문자열이며, 이러한 문자열들을 문자열 s의 부분문자열이라고 한다.
  예를 들어 s가 0100101이라면, s[3..5]는 001이고, s[4..7]은 0101이다. 따라서 001과 0101은 문자열 0100101의 부분문자열이다. 하지만 1010은 문자열 0100101의 부분문자열이 아니다. 

  첫 번째 줄에 N과 질의의 개수 Q가 정수로 주어진다.
  다음 Q개의 줄에 질의들이 한 줄에 하나씩 주어진다. 이 중 q (1 ≤ q ≤ Q)번째 줄에는 세 개의 정수 i_q, j_q, k_q가 공백 하나씩을 사이로 두고 주어진다.

• 1 ≤ N ≤ 10¹⁸
• 1 ≤ Q ≤ 10 000
• ∑^Q _q=1 kq ≤ 10 000. 즉, 모든 질의에서 주어지는 k의 값을 더하면 최대 10 000이다.
• 모든 1 ≤ q ≤ Q에 대해, 1 ≤ i_q ≤ j_q ≤ (S_N의 길이)

1. (5점) N = 2^t가 성립하는 음이 아닌 정수 t가 존재한다. 즉, N은 1, 2, 4, 8, ..과 같이 2의 거듭제곱 중 하나이다.
2. (11점) N ≤ 1 000.
3. (17점) ∑^Q _q=1(j_q − i_q + 1) ≤ 100 000. 즉, 모든 질의에서 j − i + 1의 값을 더하면 최대 100 000이다.
4. (25점) 모든 q (1 ≤ q ≤ Q)에 대해, k_q = 0
5. (42점) 추가 제약 조건 없음.

각 질의에 대한 답을 질의가 주어진 순서대로 각각 한줄에 하나씩 출력한다.

	작성자	제목(댓글)
글이 없습니다.

문제 게시판

새 글 작성

2021KOI2차