Làng Ma Sói
Problem
Tối nào dân làng Gió Hú cũng tụ tập chơi Ma Sói. Mỗi người chơi thuộc đúng một trong hai phe: Dân làng hoặc Ma sói. Không ai biết ai thuộc phe nào, chỉ biết chắc chắn là chỉ có hai phe.
Năm nay làng mời được thám tử Mèo Mun về làm người dẫn trò. Mèo Mun ngồi một góc, lắng nghe và ghi chép lại \(q\) dòng thông tin theo đúng thứ tự xuất hiện. Mỗi dòng có một trong ba dạng:
SAME A B: một lời khai nói rằng \(A\) và \(B\) cùng phe.DIFF A B: một lời khai nói rằng \(A\) và \(B\) khác phe.ASK A B: trưởng làng hỏi Mèo Mun: "\(A\) và \(B\) có cùng phe không?".
Mèo Mun luôn giữ một danh sách các lời khai mà mình tin. Ban đầu danh sách này rỗng. Ta gọi một cách chia phe là một cách xếp mỗi người vào một trong hai phe, và nói cách chia đó hợp lệ nếu nó thỏa mãn mọi lời khai Mèo Mun đang tin.
Khi gặp một lời khai về \(A\) và \(B\), Mèo Mun trả lời:
LIEnếu không có cách chia phe hợp lệ nào thỏa mãn lời khai mới. Lời khai này bị coi là nói dối và bị bỏ qua.KNOWNnếu mọi cách chia phe hợp lệ đều đã thỏa mãn lời khai mới, tức là Mèo Mun đã tự suy ra được điều này từ trước.NEWtrong các trường hợp còn lại. Mèo Mun tin lời khai này và thêm nó vào danh sách.
Khi gặp một câu hỏi về \(A\) và \(B\), Mèo Mun trả lời:
SAMEnếu trong mọi cách chia phe hợp lệ, \(A\) và \(B\) đều cùng phe;DIFFnếu trong mọi cách chia phe hợp lệ, \(A\) và \(B\) đều khác phe;UNKNOWNnếu chưa thể kết luận.
Một vài điều cần lưu ý:
- Mỗi người luôn cùng phe với chính mình.
- Người được hỏi có thể chưa từng xuất hiện trong lời khai nào.
- Tên người chơi phân biệt chữ hoa và chữ thường:
Lan,lanvàLANlà ba người khác nhau (làng Gió Hú rất đông dân và trùng tên khá nhiều).
Hãy giúp Mèo Mun trả lời tất cả các dòng thông tin trước khi trời sáng nhé.
"Kẻ thù của kẻ thù là bạn. Kẻ thù của kẻ thù của kẻ thù... thì cứ đếm cho kỹ."
-- Thám tử Mèo Mun
Input
- Dòng đầu tiên gồm một số nguyên \(q\) \((1 \leq q \leq 10^5)\) là số dòng thông tin.
- \(q\) dòng tiếp theo, mỗi dòng có dạng
SAME A B,DIFF A BhoặcASK A B. Tên \(A\), \(B\) dài từ \(1\) đến \(10\) ký tự, chỉ gồm chữ cái tiếng Anh (hoa và thường) và chữ số. \(A\) và \(B\) có thể trùng nhau.
Output
- Với mỗi dòng thông tin, in ra câu trả lời của Mèo Mun trên một dòng:
NEW,KNOWNhoặcLIEcho lời khai;SAME,DIFFhoặcUNKNOWNcho câu hỏi.
Sample
| # | Input | Output |
|---|---|---|
| 1 | | |
| 2 | | |
Note
Sample 1:
SAME An Binh: chưa biết gì về hai người này, Mèo Mun tin lời khai →NEW.DIFF Binh Cuong: cũng là thông tin mới →NEW.ASK An Cuong:Ancùng phe vớiBinh,Binhkhác phe vớiCuong, nênAnchắc chắn khác phe vớiCuong→DIFF.SAME An Cuong: trái với điều vừa suy ra →LIE, lời khai bị bỏ qua.DIFF Cuong An: điều này Mèo Mun đã biết →KNOWN.ASK Binh Dung:Dungchưa từng xuất hiện →UNKNOWN.DIFF Dung Dung: không ai khác phe với chính mình →LIE.ASK Dung Dung: ai cũng cùng phe với chính mình →SAME.
Sample 2: Soi1 khác phe với Dan, Dan khác phe với Soi2. Vì chỉ có hai phe nên Soi1 và Soi2 chắc chắn cùng phe. Ở hai dòng cuối, lan, Lan và LAN là ba người khác nhau, và chưa có lời khai nào nhắc tới LAN.
Code editor
Sign in to write and submit your solution.
Log in
Comments