Nếu chăm làm Codeforces, bài này có lẽ không làm khó bạn được lâu.

Đây là dạng bài thường hay gặp ở các bài A,B,C Div.2 - những bài không đòi hỏi thuật toán gì cụ thể, nhưng bắt ta phải quan sát đặc tính bài toán và đưa ra một lời giải ngắn gọn.

Giả sử bạn dùng một xâu \(S\) có \(n\) kí tự, được đánh số từ \(1\) để diễn tả băng giấy.

Ban đầu, nếu \(S[1] = S[n]\) thì Alice không thể đi được nên thua ngay trong lượt đầu tiên (vì lúc đầu thì toàn bộ xâu \(S\) chính là đoạn duy nhất).

Ngược lại, bạn tìm xem thử có tồn tại \(i : 1 \leq i < n\) mà \(S[i] = S[1], S[i+1] = S[n]\) hay không? Nếu câu trả lời là 'Có', thì Alice thắng như sau : Cô ấy chọn đoạn \(S[1..n]\) và cắt ra tại vị trí \(i\), khi đó đoạn giấy \(S[1..n]\) được tách ra làm 2 đoạn \(S[1..i]\) và \(S[i+1..n]\). Như vậy khi tới lượt Bob, anh ấy sẽ không thể đi được nên thua.

Ta luôn tìm ra được vị trí \(i : 1 \leq i < n\) mà \(S[i] = S[1], S[i+1] = S[n]\), như trên. Để chứng minh ta sẽ phản chứng.

"Trong xâu \(S\) không tồn tại \(i\) mà \(S[i] = S[1], S[i+1] = S[n]\), nên mọi kí tự giống \(S[n]\), phải đứng trước mọi kí tự giống \(S[1]\). Dễ thấy \(S[1]\) đứng trước \(S[n]\) nên mâu thuẫn, từ đó suy ra ĐPCM."