Ngôn ngữ ngoài hành tinh

Bài toán

Sau nhiều năm nghiên cứu, các nhà khoa học tại Google Labs đã phát hiện ra một ngôn ngữ ngoài hành tinh được truyền từ một hành tinh xa xôi. Ngôn ngữ ngoài hành tinh này rất độc đáo ở chỗ mọi từ đều có độ dài chính xác là \(L\) chữ cái thường. Ngoài ra, có đúng \(D\) từ trong ngôn ngữ này.

Sau khi xây dựng được từ điển gồm tất cả các từ trong ngôn ngữ ngoài hành tinh, bước đột phá tiếp theo là phát hiện ra rằng người ngoài hành tinh đã gửi thông điệp đến Trái Đất trong suốt thập kỷ qua. Thật không may, những tín hiệu này bị yếu đi do khoảng cách giữa hai hành tinh và một số từ có thể bị hiểu sai. Để giúp họ giải mã những thông điệp này, các nhà khoa học đã yêu cầu bạn thiết kế một thuật toán xác định số lượng cách giải thích có thể cho một mẫu (pattern) cho trước.

Một mẫu bao gồm đúng \(L\) mã thông báo (token). Mỗi mã thông báo là một chữ cái thường duy nhất (các nhà khoa học rất chắc chắn đó là chữ cái đó) hoặc một nhóm các chữ cái thường duy nhất được bao quanh bởi dấu ngoặc đơn ( và ). Ví dụ: (ab)d(dc) có nghĩa là chữ cái đầu tiên là a hoặc b, chữ cái thứ hai chắc chắn là d và chữ cái cuối cùng là d hoặc c. Do đó, mẫu (ab)d(dc) có thể đại diện cho bất kỳ một trong 4 khả năng sau: add, adc, bdd, bdc.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa 3 số nguyên \(L\), \(D\) và \(N\) cách nhau bởi dấu cách. \(D\) dòng tiếp theo, mỗi dòng chứa một từ có độ dài \(L\). Đây là những từ được biết là tồn tại trong ngôn ngữ ngoài hành tinh. \(N\) trường hợp thử nghiệm sau đó, mỗi trường hợp trên một dòng riêng biệt và mỗi trường hợp bao gồm một mẫu như mô tả ở trên. Bạn có thể giả định rằng tất cả các từ đã biết được cung cấp là duy nhất.

Dữ liệu ra

Với mỗi trường hợp thử nghiệm, xuất ra:

Case #X: K

trong đó \(X\) là số thứ tự trường hợp thử nghiệm, bắt đầu từ 1, và \(K\) cho biết có bao nhiêu từ trong ngôn ngữ ngoài hành tinh khớp với mẫu.

Ràng buộc

Phân nhóm

• Tập dữ liệu nhỏ:
• \(1 \le L \le 10\)
• \(1 \le D \le 25\)
• \(1 \le N \le 10\)
• Tập dữ liệu lớn:
• \(1 \le L \le 15\)
• \(1 \le D \le 5000\)
• \(1 \le N \le 500\)

Đ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 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc

Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0

Nguồn

Google Code Jam 2009, Vòng loại, bài Alien Language.

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

Các nhà địa chất đôi khi chia một khu vực đất đai thành các vùng khác nhau dựa trên nơi nước mưa chảy xuống. Những vùng này được gọi là lưu vực thoát nước.

Cho một bản đồ độ cao (một mảng 2 chiều chứa các độ cao), hãy đánh nhãn bản đồ sao cho các vị trí trong cùng một lưu vực thoát nước có cùng một nhãn, tuân theo các quy tắc sau:

• Từ mỗi ô, nước chảy xuống tối đa một trong 4 ô lân cận của nó.
• Đối với mỗi ô, nếu không có ô nào trong 4 ô lân cận có độ cao thấp hơn ô hiện tại, thì nước không chảy, và ô hiện tại được gọi là một hố thu (sink).
• Ngược lại, nước sẽ chảy từ ô hiện tại đến ô lân cận có độ cao thấp nhất.
• Trong trường hợp có sự bằng nhau về độ cao thấp nhất, nước sẽ chọn hướng đầu tiên có độ cao thấp nhất từ danh sách này: Bắc, Tây, Đông, Nam.

Mọi ô chảy trực tiếp hoặc gián tiếp vào cùng một hố thu đều thuộc cùng một lưu vực thoát nước. Mỗi lưu vực được đánh nhãn bằng một chữ cái viết thường duy nhất, sao cho khi các hàng của bản đồ được nối lại từ trên xuống dưới, chuỗi kết quả là nhỏ nhất về mặt từ điển. (Cụ thể, lưu vực của ô Tây-Bắc ngoài cùng luôn được đánh nhãn là 'a'.)

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào sẽ chứa số lượng bản đồ, \(T\). Tiếp theo là \(T\) bản đồ, mỗi bản đồ bắt đầu bằng hai số nguyên trên một dòng — \(H\) và \(W\) — chiều cao và chiều rộng của bản đồ, tính theo số ô. \(H\) dòng tiếp theo, mỗi dòng chứa một hàng của bản đồ, từ bắc xuống nam, mỗi hàng chứa \(W\) số nguyên, từ tây sang đông, xác định độ cao của các ô.

Dữ liệu ra

Đối với mỗi trường hợp kiểm thử, xuất ra \(1+H\) dòng. Dòng đầu tiên phải có dạng:

Case #X:

trong đó \(X\) là số thứ tự trường hợp kiểm thử, bắt đầu từ 1. \(H\) dòng tiếp theo phải liệt kê các nhãn lưu vực cho mỗi ô, theo cùng thứ tự như chúng xuất hiện trong đầu vào.

Ràng buộc

\(T \le 100\).

Phân nhóm

Tập dữ liệu nhỏ (Small dataset)

\(1 \le H, W \le 10\).
\(0 \le \text{altitudes} < 10\).
Sẽ có tối đa hai lưu vực.

Tập dữ liệu lớn (Large dataset)

\(1 \le H, W \le 100\).
\(0 \le \text{altitudes} < 10,000\).
Sẽ có tối đa 26 lưu vực.

Đ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ụ

4
3 3
9 6 3
5 9 6
3 5 9
1 10
0 1 2 3 4 5 6 7 8 7
2 3
7 6 7
7 6 7
5 5
1 2 3 4 5
2 9 3 9 6
3 3 0 8 7
4 9 8 9 8
5 6 7 8 9

Case #1:
a b b
a a b
a a a
Case #2:
a a a a a a a a a b
Case #3:
a a a
b b b
Case #4:
a a a a a
a a b b a
a b b b a
a b b b a
a a a a a

Nguồn

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

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

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.