Ones
시간 제한2.5초메모리 제한1024 MB
숨겨진 비트 배열에서 가장 긴 1의 연속 구간이 어디에 있는지 찾습니다. 각 질의는 뒤집은 뒤의 가장 긴 연속 길이만 알려 주므로 질의 횟수를 최소로 줄여야 합니다.
문제
길이가 인 숨겨진 비트 배열 이 있다. 한 번의 질의에서 수열의 위치 부분집합을 골라 그 위치에 있는 비트를 뒤집을 수 있다. 0 비트를 뒤집으면 1이 되고, 1 비트를 뒤집으면 0이 된다. 각 질의 후에는 새 배열에서 1이 연속으로 이어지는 가장 긴 부분 배열의 길이가 주어진다. 뒤집힌 비트는 나중의 질의에서 다시 뒤집히기 전까지 뒤집힌 상태로 남는다.
모든 질의를 마친 뒤 가장 긴 1의 부분 배열이 어디에 있는지 찾고자 한다. 여러 개가 있다면 그중 아무거나 하나를 찾으면 된다. 가능한 한 적은 질의로 이를 수행하는 프로그램을 작성하라.