| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 92 | 13 | 11 | 14.474% |
0과 1로만 이루어진 길이 $N$의 이진 문자열 $S$가 주어진다. 어떤 자연수 $x$의 0으로 시작하지 않는 이진수 표현을 $\mathrm{bin}(x)$라고 하자. 이 문제에서 자연수는 0ドル$을 포함하며, 예외적으로 $\mathrm{bin}(0) =$ “0”이다.
문자열 $T$의 점수란, 어떤 두 자연수 0ドル\leq l\leq r$에 대해 $T$가 $\mathrm{bin}(l),ドル $\mathrm{bin}(l+1),ドル $\cdots,ドル $\mathrm{bin}(r)$을 이어붙여서 쓴 문자열과 일치할 때, 그러한 $(l,r)$ 쌍 중 $(r-l+1)$의 최댓값으로 정의한다. 만약 그러한 $(l,r)$이 존재하지 않는다면 $T$의 점수는 0ドル$점으로 정의한다.
$S$의 substring 중 점수가 가장 높은 substring의 점수를 구하라. 어떤 문자열의 substring이란, 그 문자열의 앞의 몇 글자와 뒤의 몇 글자를 지워서 (지우지 않는 것도 가능) 만들 수 있는 문자열을 의미한다.
첫째 줄에 테스트 케이스의 개수 1ドル\leq T\leq 500,円 000$이 주어진다.
각 테스트 케이스마다, 첫째 줄에 이진 문자열의 길이 1ドル\leq N\leq 500,円 000$이 주어진다.
그 다음 줄에 길이 $N$의 문자열 $S$가 주어진다. $S$는 0과 1로만 구성되어 있다.
모든 테스트 케이스에서 $N$의 합은 500ドル,円 000$을 넘지 않는다.
각 테스트 케이스마다 한 줄에 하나씩, 총 $T$개의 줄에 걸쳐 정답을 출력한다.
6 9 011011100 2 10 9 110110001 11 11011100101 10 1011011000 14 11000110010101
5 1 3 5 4 3