Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Có ~n~ ~(n \ge 2)~ đồng tiền xu trong đó có đúng một đồng tiền giả. Đồng tiền giả này có khối lượng nhẹ hơn so với các đồng tiền thật (tất cả các đồng tiền thật có khối lượng bằng nhau). Sử dụng cân thăng bằng, cân sẽ cho ta biết bên nào nặng hơn, bên nào nhẹ hơn hoặc hai bên bằng nhau. Để tìm đồng tiền giả ta đánh số các đồng tiền từ ~1~ đến ~n~, sau đó tiến hành cân một số lần, mỗi lần cân là đặt một lượng đồng xu bằng nhau lên đĩa bên trái và đĩa bên phải. Kết quả của các lần cân được ghi lại.

Yêu cầu: Xác định đồng xu giả sử dụng các kết quả được ghi chép lại.

Dữ liệu vào

• Dòng đầu là hai số nguyên ~n~ và ~k~ trong đó ~n~ là số đồng tiền xu, ~k~ là số lần cân được ghi chép lại.
• Tiếp theo là ~k~ dòng mô tả ~k~ lần cân, mỗi dòng mô tả một lần cân. Lần cân thứ ~i~ có dạng: Bắt đầu bằng số nguyên ~s_i~ ~(1 \le s_i \le \frac{n}{2})~ là số đồng xu được đặt lên bên phải và bên trái. Tiếp theo là ~s_i~ số nguyên là số hiệu các đồng xu được đặt bên trái và ~s_i~ số nguyên là số hiệu các đồng xu được đặt bên phải. Cuối cùng là một số mô tả kết quả lần cân đó, số ~0~ nếu cân thăng bằng, số ~1~ nếu bên trái nặng hơn, số ~2~ nếu bên phải nặng hơn. Dữ liệu đảm bảo đúng đắn và tổng ~s_1 + s_2 + \dots + s_k~ không vượt quá ~10^5~.

Kết quả

• Một số nguyên là số hiệu đồng xu giả hoặc ghi ra số ~0~ nếu không thể tìm ra đồng xu giả.

Subtask

• Có ~30\%~ số test của bài có ~n \le 3~;
• Có ~40\%~ số test khác của bài có ~n \le 100~;
• Có ~30\%~ số test còn lại của bài có ~n \le 10^9~.

Sample Input 1

2 1
1 1 2 1

Sample Output 1

2

Sample Input 2

6 2
1 1 2 0
2 1 2 3 4 0

Sample Output 2

0

Nguồn: NTUCoder – Lê Quý Đôn (FCOIN).