問題
어떤 연구 컨소시엄이 새 데이터 센터를 위한 새로운 데이터베이스 시스템을 만들었다. 이 데이터베이스는 마스터 컴퓨터 1대와 워커 컴퓨터 N대로 이루어져 있으며, 워커의 ID는 0부터 N-1까지이다. 각 워커는 정확히 1비트의 정보를 저장한다... 다소 낭비처럼 보이지만, 이것은 매우 중요한 데이터다!
당신은 이 데이터베이스에 대한 다음 명령을 평가하기 위해 고용되었다:
TEST_STORE<bits>: 마스터는 <bits>를 읽는데, 이는 길이 N의 비트 문자열이다. 그리고 i번째 비트를 i번째 워커에게 보내 저장하게 한다. 그 다음 마스터는 워커들로부터 비트들을 다시 읽어, 입력받은 것과 같은 순서로 사용자에게 반환한다.
정상 동작이라면 TEST_STORE는 읽어들인 비트 문자열과 동일한 문자열을 반환해야 한다.
하지만 불행히도 워커 중 B대가 고장 났다!
고장 난 워커들도 전달받은 비트는 올바르게 저장하지만,
마스터가 고장 난 워커에서 읽기를 시도하면 어떤 비트도 반환되지 않는다.
그 결과 TEST_STORE 연산은 N-B개의 비트만 반환하게 되는데,
이는 고장 나지 않은 워커들에 저장된 비트들이며 (워커 ID의 오름차순으로) 반환된다.
예를 들어 N = 5이고 0번과 3번 워커가 고장 났다고 하자(B = 2).
그러면 다음과 같다:
TEST_STORE 01101은111을 반환한다.TEST_STORE 00110은010을 반환한다.TEST_STORE 01010은100을 반환한다.TEST_STORE 11010도100을 반환한다.
보안상의 이유로 데이터베이스는 지하 산악 금고에 숨겨져 있어서,
TEST_STORE를 호출하는 데에는 매우 오랜 시간이 걸린다.
당신의 임무는 TEST_STORE를 최대 F번 호출해서
어떤 워커들이 고장 났는지 알아내는 것이다.
來源
GCJ 2019qr D
需要登入才能撰寫程式碼。