NGUỒN: ĐỀ THI CHỌN HỌC SINH GIỎI THÀNH PHỐ BẢNG A VÀ CHỌN ĐỘI TUYỂN DỰ THI HỌC SINH GIỎI QUỐC GIA (TỈNH HẢI PHÒNG)
NĂM HỌC 2021 - 2022
Hôm nay trong tiết Tin học, Tài được cô giáo dạy gõ ba ký tự trong tên của mình, chính là T, A, I. Trong ngày tới, mỗi ngày cô giáo sẽ đưa cho Tài một xâu chỉ gồm ba ký tự đã nêu trên để cho Tài luyện gõ phím.
Tài chỉ có thể gõ được hai ký tự A và T bằng tay trái, hai ký tự T và I bằng tay phải. Nghĩa là khi bắt đầu làm bài về nhà của một ngày, Tài có thể chọn dùng một trong hai tay để gõ, sau đó trong quá trình làm bài, Tài phải đổi giữa hai tay nếu cần thiết để gõ được hết các ký tự trong xâu theo thứ tự.
Ví dụ: nếu bài về nhà là xâu ATIA thì Tài có thể gõ như sau:
Đầu tiên Tài sẽ gõ ký tự A và T bằng tay trái;
Đổi sang tay phải để gõ ký tự I;
Cuối cùng đổi sang tay trái để gõ nốt ký tự A.
Vậy, Tài phải đổi tay lần để gõ hết xâu ATIA.
Ký hiệu là số lần ít nhất Tài phải đổi tay để gõ hết xâu .
Hãy xét hai giá trị và lần lượt là xâu ký tự bài về nhà mà cô giáo cho Tài vào ngày thứ và câu hỏi mà Tài muốn được giải đáp. có thể là một trong hai giá trị sau:
Nếu thì Tài muốn biết rằng để hoàn thành bài của ngày thứ , Tài cần đổi tay ít nhất bao nhiêu lần, hay cụ thể hơn là muốn biết giá trị của ;
Nếu thì Tài muốn biết rằng nếu phải gõ riêng biệt tất cả các xâu con liên tiếp của thì Tài sẽ phải đổi tay ít nhất bao nhiêu lần. Cụ thể hơn, gọi là tập hợp những xâu con liên tiếp của thì Tài muốn tính:
Vì đáp án có thể lớn nên Tài chỉ muốn biết phần dư của kết quả trong phép chia cho .
Dữ liệu:
Dòng đầu gồm một số nguyên là số ngày Tài phải làm bài tập;
dòng tiếp theo, mỗi dòng gồm một số nguyên và một xâu . Tổng độ dài các xâu trong tất cả ngày không vượt quá .
Kết quả:
Ghi ra dòng, dòng thứ là đáp án cho câu hỏi mà Tài muốn được giải đáp vào ngày thứ .
Ví dụ:
Dữ liệu:
4
0 I
0 ATIA
1 ATIA
1 TAIIII
Kết quả:
0
2
5
8
Giải thích:
Ngày thứ , xâu bài tập về nhà: ATIA và :
Có xâu con liên tiếp độ dài : A, T, I, A. Để gõ riêng biệt từng xâu trên, mỗi xâu mất lần đổi tay;
Có xâu con liên tiếp độ dài : AT, TI, IA. Để gõ riêng biệt từng xâu trên, chỉ có xâu IA phải đổi tay lần;
Có xâu con liên tiếp độ dài : ATI, TIA. Để gõ riêng biệt từng xâu trên, mỗi xâu phải đổi tay lần;
Có xâu con liên tiếp độ dài : ATIA, để gõ xâu này phải đổi tay lần.
Vậy để gõ riêng biệt tất cả xâu con liên tiếp của xâu ATIA cần đổi tay ít nhất lần.
Giới hạn:
Subtask ( số điểm): ;
Subtask ( số điểm): Bài tập về nhà của Tài không có ký tự T;
