실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 1024 MB |
Elsie는 길이가 인 배열을 입력으로 받는 프로그램을 가지고 있습니다. 이 배열에는 0과 1로 이루어진 요소 가 포함되어 있습니다. 프로그램은 순서대로 if/else if/else 문을 적용하여 결과를 반환합니다. 하나의 조건문은 배열의 한 요소만 검사하며, 조건에 따라 0 또는 1을 반환합니다. 예를 들어:
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
Elsie는 Bessie에게 프로그램의 동작 방식에 대한 여러 예제 출력 개를 알려줍니다. 이제 Bessie의 목표는 주어진 출력을 토대로 Elsie의 프로그램을 유추하는 것입니다. 그러나, Elsie가 항상 정직하게 말한 것은 아닐 수 있습니다. 따라서 Bessie가 얻은 정보로 Elsie의 프로그램을 완벽하게 유추할 수 없는 경우도 있습니다.
입력은 테스트 케이스 의 수로 시작하며, 각 테스트 케이스는 배열의 길이 , 제공된 출력 예제의 수 및 해당하는 개의 입력-출력 쌍으로 구성됩니다.
Elsie의 설명이 유효한 프로그램을 유추할 수 있는 경우 'OK'를, 그렇지 않은 경우 'LIE'를 출력합니다.
4 1 3 0 0 0 0 1 1 2 4 00 0 01 1 10 1 11 1 1 2 0 1 0 0 2 4 00 0 01 1 10 1 11 0
OK OK LIE LIE
첫 번째 테스트 케이스에 대한 유효한 프로그램이 있습니다:
if (b[0] == 0) return 0;
else return 1;
첫 번째 테스트 케이스에 대한 다른 유효한 프로그램:
if (b[0] == 1) return 1;
else return 0;
두 번째 테스트 케이스에 대한 유효한 프로그램:
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
단, 동일한 입력에 대해 항상 동일한 출력을 해야 하므로, 모든 주어진 예제 출력을 만족시키는 프로그램을 찾을 수 없는 경우도 있습니다.
출처: USACO 2022 December Contest, Bronze Problem 3. Reverse Engineering