KOI 2차 2021 중3- 일이 이어져야 좋다 > 문제은행 : 정보올림피아드&알고리즘


4804 : 일이 이어져야 좋다

제한시간
5000 ms   
메모리제한
1024 MB   
해결횟수
2 회   
시도횟수
9 회   

문제

일이 이어져야 좋다

양의 정수 N으로 만들어지는 문자열 SN은 다음과 같이 정의된다. 

아래에서 ⌊N/2⌋은 N을 2로 나눈 몫이다.

1. N = 1인 경우: SN = 1 (즉, 1 한 글자로 이루어진 문자열)

2. N ≥ 2이고 N이 짝수인 경우: SN = S⌊N/2⌋ 0 S⌊N/2⌋​ (즉, 0 한 글자 좌우에 S⌊N/2⌋가 이어진 문자열)

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

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

• 위의 약속에서 적용이 가능한 것은 3번이므로 S13 = S6 1 S6임을 알수 있다.

• S6은 위의 약속의 2번에 의해 S3 0 S3이 되므로 S13 = S6 1 S6 = S3 0 S3 1 S3 0 S3이다.

• S3은 위의 약속의 3번과 1번을 순서대로 적용하면 111이 된다.

• 따라서 S13 = 111011111110111이다.

 

  양의 정수 N이 주어질 때, 아래와 같은 형태의 질의 Q개를 해결하는 프로그램을 작성하라.

 

  q (1 ≤ q ≤ Q)번째 질의는 세 개의 정수 (iq, jq, kq)가 주어질 때 다음과 같다: 

SN [iq..jq]에서 0을 최대 kq개까지 포함하는 가장 긴 부분문자열의 길이는?

 

위의 예에서 질의가 (1, 15, 0)이라면 가장 긴 부분문자열은 1로만 이루어져야 한다. 

또, 질의가 S13 전체에서 찾기를 요구하고 있으므로 해당 문자열의 길이는 7이다.

 

만약, (2, 14, 2)이라면 질의는 S13의 두번째부터 14번째 문자까지에서 0이 최대 2개인 가장 긴 부분문자열을 찾으라고 요구한다. 

그런데 S13[2..14] = 1101111111011에는 0이 2개 뿐이므로 그 전체가 답이 되고, 그 길이는 13이다.

 

참고

부분문자열의 정의 길이가 인 문자열 s와 1 ≤ i ≤ j ≤ 인 두 정수 i와 j에 대해, s[i..j]는 s의 i번째

문자에서부터 j번째 문자까지를 모두 순서대로 포함하는 문자열이며, 

이러한 문자열들을 문자열 s의 부분문자열이라고 한다.

예를 들어 s가 0100101이라면, s[3..5]는 001이고, s[4..7]은 0101이다. 따라서 001과 0101은 문자열

0100101의 부분문자열이다. 하지만 1010은 문자열 0100101의 부분문자열이 아니다.

 

제약 조건

• 1 ≤ N ≤ 1018

• 1 ≤ Q ≤ 10 000

• ∑Qq=1 kq ≤ 10 000. 즉, 모든 질의에서 주어지는 k의 값을 더하면 최대 10 000이다.

• 모든 1 ≤ q ≤ Q에 대해, 1 ≤ iq ≤ jq ≤ (SN의 길이)

 

부분문제

1. (5점) N = 2t가 성립하는 음이 아닌 정수 t가 존재한다.
   즉, N은 1, 2, 4, 8, ..과 같이 2의 거듭제곱 중 
하나이다.

2. (11점) N ≤ 1 000.

3. (17점) Qq=1(jq − iq + 1) ≤ 100 000. 즉, 모든 질의에서 j − i + 1의 값을 더하면 최대 100 000이다.

4. (25점) 모든 q (1 ≤ q ≤ Q)에 대해, kq = 0

5. (42점) 추가 제약 조건 없음.


입력형식

첫 번째 줄에 N과 질의의 개수 Q가 정수로 주어진다.

다음 Q개의 줄에 질의들이 한 줄에 하나씩 주어진다. 

이 중 q (1 ≤ q ≤ Q)번째 줄에는 세 개의 정수 iq, jq, kq가 공백 하나씩을 사이로 두고 주어진다.


출력형식

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


입력 예

13 3
1 15 0
2 14 2
2 8 0

출력 예

7
13
4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP