NCOB - Cuộc đấu cân não

Problem

https://vn.spoj.com/problems/NCOB

https://oj.vnoi.info/problem/NCOB

Người hành tinh BrainPower vừa mời Nuga tham dự một cuộc thi đấu thú vị. Đó là giải “Cờ Chạy” liên hành tinh.

“Cờ Chạy” là thể loại cờ do Co & Da – người hành tinh BP đưa ra vào năm 3101. Mỗi ván có 2 người chơi, luân phiên nhau thực hiện nước đi của mình, bốc thăm để chọn người chơi trước. Bàn cờ là một dãy N ô vuông, đánh số từ 1 đến N từ trái sang phải, và chỉ có 2 quân cờ duy nhất, ban đầu được đặt ở 2 ô vuông do 2 người chơi tự do lựa chọn (hai ô vuông này có thể trùng nhau). Giả sử 2 quân cờ đang ở 2 ô vuông có chỉ số là X và Y ( X ≤ Y). Người chơi thực hiện nước đi bằng cách di chuyển quân cờ ở vị trí Y đi K ô về bên trái, sao cho K phải là một bội số dương của X, và quân cờ vẫn ở trên bàn cờ. Nói cách khác, vị trí mới của quân cờ Y là Y’ = Y – K, Y’ ≥ 1. Trò chơi kết thúc khi không thể thực hiện được nước đi nào nữa. Và người không thực hiện được nước đi của mình là người thua cuộc.

Cuộc thi có nhiều vòng, mỗi vòng gồm các cặp đấu loại trực tiếp. Người thắng được lọt vào vòng trong. Người thắng trong tất cả các trận, tất nhiên, trở thành Nhà vô địch, và được thưởng 100 Triệu USD.

Nuga rất muốn giành được số tiền khổng lồ này vì cô bé đang có ý định tân trang lại con tàu siêu tốc của mình. Những người tham gia trò chơi đều là những bộ óc vĩ đại đến từ các hành tinh khác nhau, họ đều chơi tối ưu cho mọi nước đi, vì thế, Nuga phải chuẩn bị trước một số khả năng chọn ô ban đầu đặt quân cờ sao cho mình chắc chắn thắng. Cho một loạt cặp 2 số X, Y là chỉ số của 2 ô vuông ban đầu đặt 2 quân cờ. Bạn hãy giúp Nuga xác định xem Nuga phải đi trước hay đi sau thì chắc chắn sẽ thắng?

(P/S: Nuga hứa sẽ chia cho bạn một nửa giải thưởng nếu Vô địch! :P)

Dữ liệu

Gồm nhiều dòng, mỗi dòng ghi 2 số nguyên dương X Y. Kết thúc bằng cặp số 0 0.

Kết quả

Tương ứng với mỗi X Y, ghi ra trên một dòng, T nếu Nuga phải đi trước, S nếu Nuga phải đi sau để chắc chắn thắng.

Giới hạn

X, Y ≤ 2^31 – 1
Trong 50% số điểm, có X, Y ≤ 1000
Thời gian: 1s

Ví dụ

Dữ liệu
1 1
9 2
0 0

Kết quả
S
T

Tutorial

Một số lưu ý cho bài toán là các giá trị x, y luôn > 1 và giá trị k > 0 và là bội của số nhỏ.

Từ đó ta có một vài trường hợp (kí hiệu W (win, thắng) và L (lose, thua)):

(1;1) - L, vì không còn cách chơi
(1;2), (1;3),..., (1;n) - W, vì đưa về được (1;1)
(2;2) - L, vì không còn cách chơi
(2;3) - L, vì chỉ còn cách đưa về (1;2) - W
(2;4), (2;6),..., (2;2n) - W, vì có cách đưa về (2;2) - L
(2;5), (2;7),..., (2;2n+1) - W, vì có cách đưa về (2;3) - L
(3;3) - L
(3;4) - L, vì chỉ đưa về (1;3) - W
(3;5) -> (2;3) - L => trạng thái W
(3;6) -> (3;3) - L => W
(3;7) -> (3;4) - L => W
(3;8) -> (3;5) - W (2;3) - L => W

Nhận xét các trạng thái (x;2x) luôn là trạng thái thắng. Qua một số trường hợp trên, ta thấy rằng x >= 2y thì luôn thắng. Có thể chứng minh như sau: từ trạng thái (x;y), với x >= 2y, trong các cách chơi, ta có hai cách đó là đưa về trạng thái (x%y ; y), hoặc (x%y+y ; y).

Ta chứng minh một trong hai trạng thái trên là trạng thái thua. Dễ chứng mình bằng phản chứng, giả sử cả hai cùng thắng hoặc cùng thua và chú ý rằng trạng thái (x%y+y ; y) chỉ có một cách duy nhất đưa về trạng thái (x%y ; y) nên có thể chứng minh dễ dàng. Vì thế ta luôn có cách đưa đối thủ về trạng thái thua nên x >= 2y sẽ thắng.

Bây giờ còn trường hợp x < 2y nữa. Dễ thấy trạng thái này chi có một cách chơi là đưa về (x - y ; y) nên chỉ đếm số lần để đưa về trạng thái x >= 2y là có thể xác định ai thắng ai thua.

Submission

NCOB.cpp

Tutorial SPOJ