FOOL - Cá tháng tư
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

Hôm nay là ngày Cá tháng tư và An nhận được một bài tập đặc biệt từ thầy giáo của mình.

Cho N điểm trên mặt phẳng tọa độ Descartes, điểm p có tọa độ là px, py. Khoảng cách giữa 2 điểm a và b lúc này không còn được tính theo khoảng cách Euclid mà có giá trị bằng min(|ax - bx|, |ay - by|). Bạn phải chọn điểm bắt đầu và đi qua tất cả các điểm còn lại, mỗi điểm đúng một lần, và tổng khoảng cách của đường đi đó phải là nhỏ nhất, nếu có nhiều đường đi thì chọn đường đi có thứ tự từ điển nhỏ nhất (Dãy A được xem là có thứ tự từ điển nhỏ hơn dãy B nếu tồn tại một điểm k nào đó mà A1 = B1, A2 = B2, ... Ak-1 = Bk-1 và Ak < Bk). Nhưng thầy giáo lại không muốn An trả lời cho ông đường đi tìm được vì cho rằng như thế thì nó sẽ trờ thành bài toán tìm đường đi Hamilton và không còn gì là thú vị. Ông ấy muốn xuất ra tổng XOR của các đỉnh trên đường đi đó: HP = P1 xor P2 xor ... xor PN, Pi là đỉnh thứ i trong đường đi (xem ví dụ để hiểu rõ hơn). Thầy giáo yêu cầu An phải giải bài toán với giới hạn N  100) nhưng An cho rằng với N điểm sẽ tạo thành là N! với các chu trình khác nhau và cho rằng đây là một trò đùa của thầy. Tuy nhiên, thầy giáo lại nói rằng nếu An không giải được bài này trong ngày hôm nay (1/4) thì sẽ bị đánh rớt môn học (và tất nhiên An không hề muốn như thế). Cậu bắt đầu nhờ những người bạn của mình nhưng oái ăm thay hôm nay lại là Cá tháng tư và tất cả đều cho rằng đó chỉ là một trò đùa. Còn các bạn - những NTUCoder thì sao? Các bạn nghĩ đây chỉ là một trò đùa hay thật sự là một bài toán hay?

Dữ liệu nhập: gồm nhiều bộ test:

-  Dòng đầu tiên chứa một số nguyên T - số bộ test (T ≤ 10)

- Tiếp theo là T bộ test, mỗi bộ test gồm nhiều dòng: dòng đầu tiên là N - số điểm trên mặt phẳng tọa độ (0 < N ≤100), dòng thứ i trong N dòng tiếp theo chứa 2 số nguyên x, y (|x|, |y|  ≤ 109)

Dữ liệu xuất: gồm T dòng, mỗi dòng chứa một số nguyên duy nhất là tổng XOR của đường đi ngắn nhất tìm được.

 

Ví dụ

  • input
    2
    2
    1 2
    0 0
    3
    3 3
    0 0
    0 3
    output
    3
    0

Ở bộ test thứ hai, 2 đường đi [2, 3, 1] và [1, 3, 2] đều có tổng khoảng cách là nhỏ nhất (bằng 0) nhưng đường đi thứ hai có thứ tự từ điển nhỏ hơn, nên kết quả sẽ là H([1, 3, 2]) = 1 XOR 3 XOR 2 = 0

Back to Top