Tiêu đề là giải thử vì đây là cách giải của mình, có thể không chính xác hoàn toàn.
Mới gần đây vừa kết thúc cuộc thi toán quốc tế IMO 2024, đoàn Việt Nam năm nay đạt kết quả không tốt lắm (đứng thứ 33 tụt 27 hạng so với năm ngoái). Ngày đi học mình khá đam mê toán nên mình cũng hay theo dõi thông tin liên quan đến cuộc thi IMO hằng năm và đặc biệt là đề thi. Năm nay mình thấy bài số 5 ngày thi thứ 2 về ốc sên Turbo khá hay. Nó không phải thuần toán mà chỉ là toán tư duy. Khi xem kết quả thì thấy khá bất ngờ, đoàn VN chỉ có 1 em giải được.
Mình chia sẻ nó lên đây và trình bày cách giải của mình. Thực ra cách giải này giống với cơ chế đánh Index trong SQL mà mình đã từng lên bài trước đây. Link: https://viblo.asia/p/co-che-danh-index-trong-sql-YWOZrazPKQ0
Bài viết này hiện đang nằm top 1 google search về từ khóa "cơ chế đánh index", có 35 upvote và hơn 13.5 ngàn lượt xem (bài nhiều view nhất của mình).
Quay lại với bài toán Ốc sên Turbo, nội dung như sau:
Ốc sên Turbo chơi trò chơi sau trên một bảng ô vuông gồm 2024 hàng và 2023 cột. Trong 2022 ô vuông đơn vị nào đó, có các con quỷ nấp ở đó. Ban đầu, Turbo không hề biết ô nào có quỷ nấp, nhưng nó biết rằng trên mỗi hàng có đúng một con quỷ, ngoại trừ hàng đầu tiên và hàng cuối cùng, và trên mỗi cột có không quá một con quỷ.
Turbo thực hiện một chuỗi các lần thử để tìm cách đi từ hàng đầu tiên tới hàng cuối cùng. Tại mỗi lần thử, nó được quyền chọn một ô bất kỳ trên hàng đầu tiên để xuất phát, sau đó liên tục di chuyển giữa các ô, mỗi bước từ một ô sang một ô có cạnh chung với ô mà nó đang đứng. (Nó được phép đi qua các ô đã từng ghé qua trước đó.) Nếu nó tới một ô có quỷ thì lần thử này dừng lại và nó được đưa trở lại hàng đầu tiên để thực hiện một lần thử mới. Những con quỷ không di chuyển, và Turbo nhớ mỗi ô nó từng ghé qua là có quỷ hay không. Nếu nó tới được một ô bất kỳ trên hàng cuối cùng thì trò chơi kết thúc.
Xác định giá trị nhỏ nhất của n sao cho Turbo luôn có chiến lược đảm bảo tới được hàng cuối cùng sau không quá n lần thử, cho dù những con quỷ có nấp ở những ô nào đi chăng nữa.
Lời giải: (của mình)
Giả sử ô cột x hàng m sẽ gọi là ô (x,m). Ta biết m có min là 1, max là 2022 (2 ô đầu - cuối k có quỷ bỏ qua)
Đầu tiên, chúng ta có nhận xét, nếu tìm thấy 2 cột liên tiếp (có giá trị x hơn kém nhau 1 đơn vị) có tọa độ m hơn kém nhau 2 đơn vị trở lên thì chúng ta chỉ việc đi thẳng ở 1 cột và luồn lên phía trước là bài sẽ về đích an toàn. ( nhìn ảnh để hiểu hơn )
Bài toán quy về tìm 2 cột liên tiếp có m hơn kém nhau 2 đơn vị trở lên. (mệnh đề A)
Nếu một chuỗi cột liên tiếp nhau (2 ô bất kỳ lớn hơn nhau đúng 1 đơn vị), chúng ta sẽ không tìm được 2 ô ở mệnh đề A, ngược lại chúng ta sẽ tìm thấy. Một chuỗi liên tiếp đó sẽ có khoảng cách đúng bằng hiệu số thứ tự. Ví dụ từ ô 1 và ô 1000 liên tiếp thì sẽ có hiệu số = 999. Ngược lại nếu 2 số ở vị trí x-i và x-j có hiệu số khác j-i (với j > i) thì có thể kết luận chắc chắn chúng không liên tiếp, và có thể tìm thấy 2 cột ở mệnh đề A.
Sử dụng phương pháp cưa đôi để rút gọn phạm vi tìm kiếm, như sau: Đầu tiên kiểm tra giá trị ô đầu tiên và cuối cùng(x-1 và x-2023), do hiệu số của chúng bằng 2022 nên chắc chắn chúng không thể là chuỗi cột liên tiếp. Tiếp tục cưa đôi ở giữa (x= 1012) và xem giá trị của ô này bằng bao nhiêu. Chúng ta sẽ tìm được một nửa có hiệu số không đúng với khoảng cách của chúng. Do đó chúng ta sẽ xác định được 2 ô cần tìm ở mệnh đề A nằm ở phạm vi từ x-0 đến x-1012 hoặc ngược lại. (đây chính là cơ chế tìm kiếm trong đánh index của SQL và các hệ quản trị cơ sở dữ liệu khác)
Tiếp tục cưa đôi thêm nhiều lần khác.
Sau khi cưa đôi phạm vi tìm kiếm giảm đi 1 nửa. Cứ cưa đôi 10 lần nữa chúng ta sẽ chắc chắn tìm ra, 2 ô cần tìm ở mệnh đề A. Tại sao lại 10 lần. Vì 2^10=1024 > 1012.
Cộng thêm 3 lần đầu, vậy đáp án là 13 lần.
Lời giả trên có thể còn thiếu sót hoặc thậm chí sai. Mời các bạn cùng đàm đạo thêm.
my blog: https://zreview.vn