ESAb ATAd timer 40s memory 1024MB

작년에 한 연구 컨소시엄은 분산 데이터베이스 시스템에서 데이터 일부가 가끔 사라지는 문제를 겪었다. (그 문제를 풀기 위해 이전 문제를 읽거나 이해할 필요는 없다!)

컨소시엄은 분산 시스템이 너무 복잡하다고 판단해, 중요한 정보 B비트를 하나의 멋진 기계 위에 있는 단일 배열에 저장하기로 했다. 보안을 한 겹 더 강화하기 위해, 정보를 빠르게 얻기 어렵게 만들어 두었다. 사용자는 1부터 B까지의 비트 위치를 질의해야 하며, 그러면 저장된 배열의 그 비트를 응답으로 받는다.

불행히도 이 초현대적 기계는 무작위 양자 요동(quantum fluctuation)의 영향을 받는다! 구체적으로, 1번째, 11번째, 21번째, 31번째... 등의 질의를 보낸 뒤에 응답이 오기 전에, 양자 요동이 다음 네 가지 효과 중 정확히 하나를 같은 확률로 일으킨다:

• 25% 확률로 배열이 보수(complement) 처리된다: 모든 0이 1이 되고, 반대로도 마찬가지다.
• 25% 확률로 배열이 뒤집힌다(reverse): 첫 번째 비트가 마지막 비트와, 두 번째 비트가 끝에서 두 번째 비트와, ... 이런 식으로 서로 바뀐다.
• 25% 확률로 위 두 가지(보수 처리와 뒤집기)가 모두 일어난다. (일어나는 순서는 중요하지 않다.)
• 25% 확률로 아무 일도 일어나지 않는다.

또한 각 요동이 어떤 효과를 일으켰는지에 대한 표시가 전혀 없다. 컨소시엄은 걱정이 되어 당신을 고용했고, 당신은 어떤 형태로든 귀중한 데이터를 되찾아야 한다! 당신이 답을 제출하는 시점을 기준으로 정확한 전체 배열을 찾아낼 수 있겠는가? 답을 제출하는 행위는 질의로 계산되지 않는다. 예를 들어 30번째 질의 이후에 답을 제출한다면, 배열은 21번째부터 30번째 질의까지의 상태와 동일하다.