BOI 2024 - Portal
Xem PDFBạn nghĩ rằng đặt người bạn thân của mình vào ô \((0,0)\) trên một lưới vô hạn gồm các ô được tô màu sẽ là một trò đùa thú vị. Người bạn sau đó di chuyển trên lưới mãi mãi, mỗi lần đi một bước sang một trong bốn ô kề cạnh.
Có \(N\) ô trên lưới chứa cổng dịch chuyển. Khi người bạn bước vào một ô có cổng, người ấy lập tức được dịch chuyển đến một cổng ngẫu nhiên, có thể là chính cổng vừa bước vào hoặc một cổng khác. Nếu ô \((0,0)\) có cổng, người bạn cũng được dịch chuyển ngay khi được đặt lên lưới lúc bắt đầu.
Bạn muốn đánh lừa để người bạn không nhận ra sự tồn tại của các cổng. Điều duy nhất người ấy nhìn thấy là màu của ô đang đứng, vì vậy bạn phải bảo đảm rằng, theo cảm nhận của người ấy, màu của các ô không bao giờ thay đổi. Cụ thể, nếu người ấy nghĩ rằng mình đã đi vào một ô nhiều lần, chẳng hạn bằng cách đi sang trái rồi lập tức đi sang phải, màu nhìn thấy phải giống như lần đầu tiên người ấy nghĩ rằng mình đã đi vào ô đó.
Lưu ý rằng khi bước vào một cổng, người bạn nhìn thấy cả màu của ô vừa bước vào lẫn màu của ô được dịch chuyển đến. Vì thế, bạn phải tô tất cả các ô có cổng cùng một màu để việc dịch chuyển không bị phát hiện ngay lập tức.
Một cách đơn giản là tô tất cả các ô cùng một màu. Nhưng màu sắc rất đẹp! Vì thế, bạn muốn dùng càng nhiều màu càng tốt.
Hãy tính số màu lớn nhất có thể dùng mà vẫn bảo đảm người bạn không nhận ra sự tồn tại của các cổng.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên \(N\) là số cổng dịch chuyển.
Tiếp theo là \(N\) dòng, mỗi dòng chứa hai số nguyên. Dòng thứ \(i\) chứa \(x_i\) và \(y_i\), cho biết có một cổng tại ô \((x_i,y_i)\).
Dữ liệu ra
In ra một số nguyên duy nhất là số màu lớn nhất có thể dùng mà người bạn không nhận ra các cổng, hoặc \(-1\) nếu có thể dùng vô hạn màu.
Ràng buộc
- \(1\le N\le 10^5\).
- \(-10^6\le x_i,y_i\le 10^6\) với mọi \(1\le i\le N\).
- Không có hai cổng có cùng tọa độ.
Phân nhóm
- \(1\) điểm: \(N\le 2\).
- \(10\) điểm: \(N\le 3\).
- \(10\) điểm: với mọi số nguyên \(x_1,x_2,y_1,y_2\), nếu có cổng tại \((x_1,y_1)\) và \((x_2,y_2)\) thì cũng có cổng tại \((x_1,y_2)\).
- \(29\) điểm: \(N\le 100\) và \(-100\le x_i,y_i\le 100\) với mọi \(1\le i\le N\).
- \(15\) điểm: \(N\le 2000\).
- \(35\) điểm: không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
3
1 1
1 3
3 2Output
4Giải thích
Các cổng nằm tại \((1,1)\), \((1,3)\) và \((3,2)\). Giả sử người bạn thực hiện lần lượt các bước: lên, phải, xuống, trái.
Năm khung hình lần lượt mô tả trạng thái sau \(0\), \(1\), \(2\), \(3\) và \(4\) bước. Ô màu xanh dương biểu thị nơi người bạn nghĩ mình đang đứng; ô màu xanh nhạt biểu thị những vị trí khác mà người ấy có thể đang đứng; chấm đỏ biểu thị ô có cổng dịch chuyển.
- Sau \(0\) bước: người bạn ở vị trí ban đầu và nhìn thấy màu của ô \((0,0)\) lần đầu tiên.
- Sau \(1\) bước: đi lên ô \((0,1)\).
- Sau \(2\) bước: đi sang phải vào ô \((1,1)\) và dịch chuyển đến bất kỳ cổng nào trong ba cổng.
- Sau \(3\) bước: đi xuống.
- Sau \(4\) bước: đi sang trái. Người bạn nghĩ mình đã trở lại điểm xuất phát, nhưng có thể đang ở bất kỳ vị trí được tô màu nào trong khung hình này.
Sau chuỗi bước đi, người bạn nghĩ mình đã trở lại ô xuất phát \((0,0)\), nhưng thực tế cũng có thể kết thúc tại \((0,2)\) hoặc \((2,1)\). Người ấy đã nhìn thấy màu của ô \((0,0)\) lúc bắt đầu, nên nếu bây giờ nhìn thấy màu khác, người ấy sẽ nhận ra phải có các cổng dịch chuyển. Vì không muốn điều đó xảy ra, bạn phải tô ba ô này cùng một màu.
Không có chuỗi bước đi nào khiến người bạn nghĩ mình kết thúc tại \((0,0)\) trong khi thực tế kết thúc tại \((1,0)\), nên có thể tô hai ô này bằng hai màu khác nhau mà không làm lộ các cổng.
Hình dưới đây minh họa một cách tô bằng \(4\) màu. Không thể dùng nhiều hơn \(4\) màu trong ví dụ này.
Ví dụ 2
Input
5
0 0
1 0
-1 0
0 1
0 -1Output
1Giải thích
Các cổng nằm tại \((0,0)\), \((0,1)\), \((1,0)\), \((0,-1)\) và \((-1,0)\). Giả sử người bạn muốn đến ô \((1,3)\) bằng cách đi sang phải một lần rồi đi lên ba lần. Có khả năng người ấy kết thúc tại \((0,0)\) nếu bị dịch chuyển về đó lúc bắt đầu và sau mỗi bước đi.
Nếu sau đó người ấy quay lại nơi mình nghĩ là ô \((0,0)\) bằng cách đi xuống ba lần rồi sang trái một lần, và trong quá trình này không bị dịch chuyển ra khỏi ô vừa bước vào, người ấy sẽ kết thúc tại \((-1,-3)\). Người ấy nghĩ rằng mình đang ở ô \((0,0)\) lần thứ hai và mong đợi nhìn thấy cùng một màu. Vì vậy, bạn phải tô \((-1,-3)\) và \((0,0)\) cùng một màu.
Việc ban đầu chọn ô \((1,3)\) không có gì đặc biệt. Bằng lập luận tương tự, có thể chứng minh rằng những ô khác cũng phải có cùng màu với \((0,0)\).
Ví dụ 3
Input
1
1 -1Output
-1Giải thích
Người bạn chỉ có thể được “dịch chuyển” về chính ô chứa cổng. Vì vậy, người ấy không thể nhận ra sự tồn tại của cổng ngay cả khi mỗi ô được tô bằng một màu khác nhau.
Kỳ thi:
- BOI 2024 - Ngày 1 (5 Tháng năm, 2024)
Bình luận