Độ khó: Dễ (1/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Barbara là một người gõ phím tốc độ. Để kiểm tra tốc độ gõ của mình, cô làm một bài kiểm tra tốc độ: cô được cho một chuỗi ~\mathbf{I}~ mà cô cần gõ lại.

Trong lúc gõ, Barbara có thể mắc vài lỗi, chẳng hạn như bấm nhầm phím. Vì tốc độ gõ rất quan trọng với cô nên cô không muốn tốn thêm thời gian sửa lỗi, cô cứ gõ tiếp cùng với các lỗi đó cho tới khi hoàn thành bài kiểm tra. Sau khi hoàn thành, cô tạo ra được chuỗi ~\mathbf{P}~.

Giờ cô muốn biết cần xoá bao nhiêu chữ cái thừa để thu được ~\mathbf{I}~ từ ~\mathbf{P}~. Có thể Barbara đã gõ sai đến mức không thể biến ~\mathbf{P}~ trở lại thành ~\mathbf{I}~ chỉ bằng cách xoá bớt chữ cái. Đặc biệt, có thể Barbara đã gõ sót một số chữ cái.

Hãy giúp Barbara tìm xem cô cần xoá bao nhiêu chữ cái thừa để thu được ~\mathbf{I}~, hoặc nếu không thể thu được ~\mathbf{I}~ từ ~\mathbf{P}~ bằng cách xoá chữ cái thì in ra IMPOSSIBLE.

Dữ liệu vào

• Dòng đầu tiên cho số lượng test ~\mathbf{T}~, tiếp theo là ~\mathbf{T}~ test.
• Mỗi test gồm 2 dòng: dòng thứ nhất là chuỗi ~\mathbf{I}~ (chuỗi mà bài kiểm tra đưa ra), dòng tiếp theo là chuỗi ~\mathbf{P}~ (chuỗi Barbara đã gõ).

Kết quả

• Với mỗi test, in ra một dòng Case #x: y, trong đó ~x~ là số thứ tự của test (bắt đầu từ ~1~) và ~y~ là số chữ cái thừa cần xoá để thu được ~\mathbf{I}~. Nếu không thể thu được ~\mathbf{I}~ thì in IMPOSSIBLE thay cho ~y~.

Giới hạn

• Bộ nhớ: 1 GB.
• ~1 \le \mathbf{T} \le 100~.
• Cả hai chuỗi chỉ gồm các chữ cái a-z và A-Z.
• Độ dài hai chuỗi: ~1 \le |\mathbf{I}|, |\mathbf{P}| \le 10^5~.
• Giới hạn thời gian trên hệ thống: 1 giây (đề gốc cho 20 giây với Test Set 1 và 40 giây với Test Set 2).

Subtask

• Subtask 1 (Test Set 1, ~40\%~ số điểm): mọi chữ cái trong ~\mathbf{I}~ đều giống nhau.
• Subtask 2 (Test Set 2, ~60\%~ số điểm): không có ràng buộc gì thêm.

Sample Input 1

2
aaaa
aaaaa
bbbbb
bbbbc

Sample Output 1

Case #1: 1
Case #2: IMPOSSIBLE

Giải thích

Ở test thứ nhất, ~\mathbf{P}~ thừa một chữ a, nên cô cần xoá ~1~ chữ cái thừa để thu được ~\mathbf{I}~. Ở test thứ hai, Barbara chỉ gõ ~4~ chữ b, trong khi ~\mathbf{I}~ gồm ~5~ chữ b, nên đáp án là IMPOSSIBLE.

Sample Input 2

2
Ilovecoding
IIllovecoding
KickstartIsFun
kkickstartiisfun

Sample Output 2

Case #1: 2
Case #2: IMPOSSIBLE

Giải thích

Ở test thứ nhất, ~\mathbf{P}~ thừa 2 chữ cái là I và l, các chữ cái còn lại đúng thứ tự như trong ~\mathbf{I}~, nên cần xoá ~2~ chữ cái. Ở test thứ hai, trong ~\mathbf{P}~ không có chữ K (in hoa) nên đáp án là IMPOSSIBLE.

Nguồn: Google Kick Start 2022 – Round A.