cho.sh적당히 좋은 비율 (작은 입력)
이진 문자열과 목표 비율 F가 주어질 때 1의 비율이 F에 가장 가까운 연속 부분 문자열의 시작 인덱스를 구합니다.
보통4완전 탐색누적 합면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB문제
0과 1로만 이루어진 길이 N의 문자열이 있다. 이 문자열에서 1의 비율이 목표값 F에 최대한 가까운 연속 부분 문자열을 찾아야 한다. 비율이 F와 정확히 같은 부분 문자열은 없을 수도 있으므로, 차이가 가장 작은 것을 고른다.
부분 문자열의 1의 비율은 그 안에 든 1의 개수를 길이로 나눈 값이다. 길이가 1 이상인 부분 문자열만 대상으로 한다. ∣비율−F∣가 최소인 부분 문자열의 시작 인덱스를 구한다.
입력
첫 줄에 테스트 케이스 수 T가 주어진다. 이어서 각 테스트 케이스가 두 줄씩 주어진다. 첫 줄에는 N과 F가 공백 하나로 구분되어 주어진다. F는 0 이상 1 이하의 소수이고, 소수점 아래 자리가 정확히 6개다. 둘째 줄에는 0 또는 1인 숫자 N개가 공백 없이 붙어서 주어진다.
제한
- 1≤T≤100
- 1≤N≤1000
- 0≤F≤1
- F는 소수점 아래 자리가 정확히 6개다.
출력
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 1의 비율이 F에 가장 가까운 부분 문자열의 시작 인덱스다. 인덱스는 0부터 센다. 최소 오차를 달성하는 부분 문자열이 여러 개면 그중 시작 인덱스가 가장 작은 값을 출력한다.
힌트
문자열 001001010111과 F=0.666667을 보자. 1의 비율이 정확히 666667/1000000인 부분 문자열은 없다. 가장 가까운 값은 2/3이고, 이 값을 만드는 부분 문자열은 다섯 개다. 길이가 3인 것은 인덱스 5, 7, 8에서 시작하는 101, 101, 011이고, 길이가 6인 것은 인덱스 5와 6에서 시작하는 101011, 010111이다. 이 중 가장 작은 시작 인덱스는 5다.