Vậy là bạn đã đăng ký. Chúng tôi đã gửi cho bạn một email chào mừng, để chào mừng bạn đến với Code Jam. Nhưng có thể bạn vẫn chưa cảm thấy thực sự được chào đón. Đó là lý do tại sao chúng tôi quyết định đặt tên cho một bài tập là "welcome to code jam". Sau khi giải bài tập này, chúng tôi hy vọng bạn sẽ cảm thấy rất được chào đón. Rất được chào đón, theo nghĩa đen, đến với Code Jam.

Nếu bạn đọc đoạn văn trên, có lẽ bạn đang thắc mắc tại sao nó lại ở đó. Nhưng nếu bạn đọc thật kỹ, bạn có thể nhận thấy rằng chúng tôi đã viết cụm từ "welcome to code jam" nhiều lần: tổng cộng 400263727 lần. Suy cho cùng, thật dễ dàng để tìm trong đoạn văn một chữ 'w'; sau đó tìm một chữ 'e' ở phía sau; rồi tìm một chữ 'l' sau đó nữa, và cứ thế. Nhiệm vụ của bạn là viết một chương trình có thể nhận bất kỳ văn bản nào và in ra số lần văn bản đó chứa cụm từ "welcome to code jam".

Chính xác hơn, cho một chuỗi văn bản, bạn cần xác định xem chuỗi "welcome to code jam" xuất hiện bao nhiêu lần dưới dạng một dãy con (sub-sequence) của chuỗi đó. Nói cách khác, hãy tìm một dãy \(s\) gồm các chỉ số tăng dần trong chuỗi đầu vào sao cho sự kết hợp của input[s[0]], input[s[1]], ..., input[s[18]] là chuỗi "welcome to code jam".

Kết quả tính toán của bạn có thể rất lớn, vì vậy để thuận tiện, chúng tôi chỉ yêu cầu bạn tìm 4 chữ số cuối cùng.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, N. N dòng tiếp theo, mỗi dòng chứa một bộ test. Mỗi bộ test là một dòng văn bản duy nhất, chỉ chứa các chữ cái viết thường và dấu cách. Không có dòng nào bắt đầu bằng dấu cách và không có dòng nào kết thúc bằng dấu cách.

Dữ liệu ra

Với mỗi bộ test, in ra "Case #x: dddd", trong đó x là số thứ tự bộ test và dddd là 4 chữ số cuối của câu trả lời. Nếu câu trả lời có ít hơn 4 chữ số, vui lòng thêm các chữ số 0 ở phía trước để đảm bảo độ dài đúng 4 chữ số.

Ràng buộc

• 1 ≤ N ≤ 100.

Phân nhóm

• Small dataset: Mỗi dòng sẽ không dài quá 30 ký tự.
• Large dataset: Mỗi dòng sẽ không dài quá 500 ký tự.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
elcomew elcome to code jam
wweellccoommee to code qps jam
welcome to codejam

Case #1: 0001
Case #2: 0256
Case #3: 0000

Nguồn

Google Code Jam 2009, Vòng loại, bài Welcome to Code Jam.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.