Sasha và cái tên khác

Điểm: 6,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một xâu $s$ là xâu đối xứng (palindrome) — đọc xuôi và đọc ngược cho ra cùng một xâu. Bạn được phép cắt $s$ thành đúng $k + 1$ đoạn liên tiếp (không lật ngược đoạn nào), rồi ghép các đoạn này theo một thứ tự bất kỳ để tạo thành một xâu mới $s^{'}$ .

Hãy tìm giá trị nhỏ nhất của $k$ sao cho có thể chọn cách cắt và cách ghép phù hợp để $s^{'}$ vừa là một xâu đối xứng, vừa khác với xâu ban đầu $s$ . Nếu không tồn tại $k$ thoả mãn, in ra Impossible.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ ( $1 \leq | s | \leq 5000$ ), chỉ gồm các chữ cái Latin in thường.
Đảm bảo $s$ là xâu đối xứng.

Dữ liệu ra

In ra một số nguyên là giá trị nhỏ nhất của $k$ , hoặc Impossible nếu không tồn tại.

Ràng buộc

$1 \leq | s | \leq 5000$ .
$s$ chỉ gồm chữ cái Latin in thường và là xâu đối xứng.

Ví dụ

Input	Output	Giải thích
nolon	2	Cắt thành 3 đoạn: no \| l \| on, ghép lại theo thứ tự on \| l \| no thu được `onlno`.
otto	1	Cắt ở chính giữa thành ot \| to, ghép lại thành `toot`.
qqqq	Impossible	Mọi cách ghép đều cho ra `qqqq`.
kinnikkinnik	1	Cắt lấy hậu tố `nik` rồi đem ra đầu, thu được `nikkinnikkin`.

Bình luận

Không có bình luận tại thời điểm này.