프로그램 역설계

실행 시간 제한	메모리 제한
2 초	1024 MB

📃 해결할 문제

Elsie는 길이가 $N$ 인 배열을 입력으로 받는 프로그램을 가지고 있습니다. 이 배열에는 0과 1로 이루어진 요소 $b[0], \dots, b[N-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에게 프로그램의 동작 방식에 대한 여러 예제 출력 $M$ 개를 알려줍니다. 이제 Bessie의 목표는 주어진 출력을 토대로 Elsie의 프로그램을 유추하는 것입니다. 그러나, Elsie가 항상 정직하게 말한 것은 아닐 수 있습니다. 따라서 Bessie가 얻은 정보로 Elsie의 프로그램을 완벽하게 유추할 수 없는 경우도 있습니다.

💻 입력

입력은 테스트 케이스 $T$ 의 수로 시작하며, 각 테스트 케이스는 배열의 길이 $N$ , 제공된 출력 예제의 수 $M$ 및 해당하는 $M$ 개의 입력-출력 쌍으로 구성됩니다.

🖨️ 출력

Elsie의 설명이 유효한 프로그램을 유추할 수 있는 경우 'OK'를, 그렇지 않은 경우 'LIE'를 출력합니다.

💻 예제 입력 1

🖨️ 예제 출력 1

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