레이팅 미적용엘시는 각각 0 또는 1인 \(N\)개(\(1\le N\le 100\))의 변수 \(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;
예를 들어 위 프로그램의 입력이 "10"(즉, \(b[0] = 1\)이고 \(b[1] = 0\))이면 출력은 1이어야 한다.
엘시는 베시에게 \(M\)개(\(1\le M\le 100\))의 서로 다른 입력에 대한 올바른 출력을 알려 주었다. 베시는 이제 엘시의 프로그램을 역공학하려 하고 있다. 안타깝게도 엘시가 거짓말을 했을 수도 있다. 즉, 위와 같은 형태의 프로그램 중 엘시가 말한 내용과 일치하는 것이 하나도 없을 수도 있다.
\(T\)개(\(1\le T\le 10\))의 각 테스트 케이스에 대해, 엘시가 반드시 거짓말을 하고 있는지 아닌지 판별하시오.
출제: Benjamin Qi
배점
- 입력 2와 3은 \(N = 2\)이다.
- 입력 4와 5는 \(M = 2\)이다.
- 입력 6부터 12까지는 추가 제약이 없다.
출제: Benjamin Qi
첫째 줄에 테스트 케이스의 수 \(T\)가 주어진다.
각 테스트 케이스는 두 정수 \(N\)과 \(M\)으로 시작하며, 이어서 \(M\)개의 줄이 주어진다. 각 줄에는 입력(즉, \(b[0] \ldots b[N-1]\)의 값)을 나타내는 0과 1로 이루어진 길이 \(N\)의 문자열과, 출력을 나타내는 추가 문자 하나(0 또는 1)가 주어진다. 연속한 테스트 케이스는 빈 줄로 구분된다.
각 테스트 케이스에 대해 "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 0OK
OK
LIE
LIEHere's a valid program for the first test case:
if (b[0] == 0) return 0;
else return 1;
Another valid program for the first test case:
if (b[0] == 1) return 1;
else return 0;
A valid program for the second test case:
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
Clearly, there is no valid program corresponding to the third test case, because
Elsie's program must always produce the same output for the same input.
It may be shown that there is no valid program corresponding to the last test
case.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Bronze