Kỹ Thuật Đảo Ngược

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Elsie có một chương trình nhận vào một mảng gồm $N$ biến nhị phân và thực thi một loạt các câu lệnh if/else if/else, mỗi câu lệnh kiểm tra tối đa một biến và trả về 0 hoặc 1. Bessie biết $M$ cặp input-output đúng nhưng nghi ngờ Elsie có thể đã nói dối.

Hãy xác định liệu có tồn tại một chương trình hợp lệ nhất quán với tất cả các cặp input-output được cung cấp hay không.

Dữ liệu vào

Dòng đầu tiên chứa $T$ ( $1 \leq T \leq 10$ ), số lượng bộ test.
Với mỗi bộ test (các bộ test cách nhau bởi dòng trống):
- Dòng 1: hai số nguyên $N$ và $M$ ( $1 \leq N, M \leq 100$ ).
- $M$ dòng tiếp theo: mỗi dòng chứa một xâu nhị phân độ dài $N$ (input) và một chữ số nhị phân (output).

Dữ liệu ra

Với mỗi bộ test, in "OK" nếu tồn tại chương trình hợp lệ, ngược lại in "LIE".

Ràng buộc

$1 \leq N \leq 100$
$1 \leq M \leq 100$
$1 \leq T \leq 10$

Ví dụ

Input	Output	Giải thích
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	Test 3: cùng input "0" nhưng output khác nhau, nên là LIE. Test 4: không thể xây dựng chương trình nhất quán vì "01" cho 1 và "11" cho 0 nhưng "00" cho 0 và "10" cho 1.

Bình luận

Không có bình luận tại thời điểm này.