Problemas
DNA 서열은 A, C, G, T 4개의 문자로 구성되어 있다.
DNA 서열의 GC-비율이란 특정 구간에 포함되어 있는 G와 C의 개수의 합을 해당 구간의 길이로 나눈 것을 의미한다. GC-비율은 유전자 발견에 있어서 중요한데
상대적으로 높은 GC-비율을 가진 DNA서열은 유전자의 시작 부분이 될 좋은 후보이기 때문이다.
아주 긴 DNA 서열이 주어질 때, 연구원들은 일반적으로 전체 부분서열 중에서 최대 GC-비율을 갖는 위치에 관심을 갖는다.
때때로 너무 짧은 구간에서 높은 GC-비율을 정하는 것은 유전자를 발견하는데 있어서 의미가 없기 때문에
신뢰할 수 있는 최저 구간수가 주어진다.
DNA 서열에서 A와 T는 0으로, G와 C는 1로 바꾸어 표기하면 같은 길이의 이진서열로 변환할 수 있다.
이렇게 하면 DNA 서열에서의 GC-비율은 이진서열에서의 평균과 같아진다.
이진 서열이 위와 같고 최저 구간수가 7 이라면 최대 평균은 [7, 14] 구간에서 6/8 이 된다.
GC-비율은 (1의 개수의 합)/(구간의 길이) 이기 때문이다.
만일 최저 구간수가 5라고 한다면 최대 평균은 [7, 11] 구간에서 4/5가 되고 7은 시작 번호, 11은 마지막 번호가 된다.
이진 서열과 최저 구간수가 주어질 때,
주어진 이진서열의 최저 구간 수 이상의 부분서열 중에서 최대 평균을 갖는 구간을 구하는 프로그램을 작성해 보자.
만일 최대 평균을 갖는 구간이 두 개 이상일 경우 가장 짧은 구간을 선택하고
그래도 두 개 이상일 경우에는 시작번호가 가장 앞선 구간을 선택한다.
Entrada
첫 줄에 테스트 케이스의 개수 1≤T≤20 가 입력된다. 다음 줄에 두 개의 정수 1≤N(이진서열의 수)≤100,000과 1≤L(최저구간수)≤1,000가 공백으로 구분하여 주어진다. 다음 줄에 N 개의 이진서열이 문자열로 주어진다.
Salida
최대평균을 갖는 구간의 시작 번호와 마지막 번호를 출력한다. 만일 최대 평균 을 갖는 구간이 두 개 이상일 경우 가장 짧은 구간을 선택하고 그래도 두 개 이상일 경우에는 시작번호가 가장 앞선 구간을 선택한다.
Ejemplo
2
17 5
00101011011011010
20 4
11100111100111110000
7 11
6 9
Debes iniciar sesión para escribir código.