JOI 2025 - Cycle String
Xem PDFCho xâu \(S\) có độ dài \(N\), chỉ gồm các chữ cái tiếng Anh viết thường.
Xâu \(S\) được gọi là có tính chu kỳ nếu tồn tại một xâu \(T\) và một số nguyên \(m \ge 2\) sao cho, bắt đầu từ xâu rỗng và nối lần lượt \(m\) bản sao của \(T\), ta thu được đúng xâu \(S\).
Hãy xác định xem \(S\) có tính chu kỳ hay không.
Dữ liệu vào
- Dòng thứ nhất chứa số nguyên \(N\).
- Dòng thứ hai chứa xâu \(S\).
Dữ liệu ra
In ra Yes nếu \(S\) có tính chu kỳ; ngược lại, in ra No.
Chỉ in ra đáp án, không in thêm bất kỳ nội dung nào khác, kể cả lời nhắc nhập dữ liệu.
Ràng buộc
- \(2 \le N \le 1000\).
- \(S\) là xâu có độ dài \(N\).
- Mỗi ký tự của \(S\) là một chữ cái tiếng Anh viết thường.
- \(N\) là số nguyên.
Ví dụ
Ví dụ 1
Input
6
abababOutput
YesGiải thích
Bắt đầu từ xâu rỗng, nối \(3\) bản sao của ab ta được ababab. Vì vậy, \(S\) có tính chu kỳ.
Ví dụ 2
Input
7
abcabcaOutput
NoGiải thích
Nối \(1\) bản sao của abcabca vào xâu rỗng cũng cho ra abcabca, nhưng số lần nối chỉ là \(1\), không thỏa mãn điều kiện \(m \ge 2\). Xâu \(S\) không có tính chu kỳ.
Ví dụ 3
Input
2
aaOutput
YesGiải thích
Bắt đầu từ xâu rỗng, nối \(2\) bản sao của a ta được aa. Vì vậy, \(S\) có tính chu kỳ.
Ví dụ 4
Input
8
ababcdcdOutput
NoNguồn
Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.
Kỳ thi:
- JOI 2025 - Vòng loại 1 - Đợt 3 (16 Tháng 11., 2024)
Bình luận