Google Code Jam 2009 - Round 3

Như chúng ta đều biết, có một sự khác biệt lớn giữa đa thức bậc 4 và đa thức bậc 5. Câu hỏi về việc không tồn tại công thức nghiệm tổng quát cho đa thức bậc 5 đã tạo ra lý thuyết Galois nổi tiếng, mà theo như tác giả thấy, không có liên quan gì đến bài toán của chúng ta ở đây.

Chúng ta chỉ xem xét các đa thức nhiều biến có bậc tối đa là 4, trên 26 biến, được đại diện bởi tập hợp 26 chữ cái tiếng Anh viết thường. Dưới đây là một đa thức như vậy:

aber+aab+c

Cho một chuỗi \(s\), chúng ta tính giá trị của đa thức trên chuỗi đó. Việc tính toán cho kết quả \(p(S)\) như sau: Mỗi biến được thay thế bằng số lần xuất hiện của chữ cái đó trong \(S\).
Ví dụ, lấy đa thức ở trên và giả sử \(S\) = "abracadabra edgar". Có sáu chữ 'a', hai chữ 'b', một chữ 'c', một chữ 'e', và ba chữ 'r'. Vì vậy

p(S) = 6 * 2 * 1 * 3 + 6 * 6 * 2 + 1 = 109.

Cho một từ điển gồm các từ phân biệt chỉ chứa các chữ cái viết thường, chúng ta gọi một chuỗi \(S\) là một d-cụm từ (d-phrase) nếu

S = "S1 S2 S3 ... Sd",

trong đó \(S_i\) là bất kỳ từ nào trong từ điển, với \(1 \le i \le d\). Nghĩa là, \(S\) có dạng \(d\) từ trong từ điển ngăn cách bởi các khoảng trắng. Cho một số K \(\le 10\), nhiệm vụ của bạn là, với mỗi \(1 \le d \le \mathbf{K}\), hãy tính tổng của \(p(S)\) trên tất cả các \(d\)-cụm từ. Vì kết quả có thể rất lớn, bạn được yêu cầu tính số dư khi chia kết quả cho 10009.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test T. T bộ test tiếp theo. Định dạng của mỗi bộ test là:
Một dòng chứa biểu thức \(p\) cho đa thức nhiều biến, như mô tả bên dưới, sau đó là một khoảng trắng, tiếp theo là một số nguyên K.
Một dòng với một số nguyên n, số lượng từ trong từ điển.
Sau đó là n dòng, mỗi dòng chứa một từ, chỉ gồm các chữ cái viết thường. Không có từ nào bị lặp lại trong cùng một bộ test.

Chúng ta luôn viết đa thức dưới dạng tổng của các số hạng; mỗi số hạng là tích của các biến. Chúng ta viết \(a^t\) đơn giản là \(t\) chữ \(a\) viết liền nhau. Ví dụ, \(a^2b\) được viết là \(aab\). Các biến trong mỗi số hạng luôn được sắp xếp không giảm theo thứ tự từ điển.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng có dạng

Case #X: sum1 sum2 ... sumK

trong đó \(X\) là số thứ tự bộ test bắt đầu từ 1, và \(sum_i\) là tổng của \(p(S)\), với \(S\) chạy qua tất cả các \(i\)-cụm từ, modulo 10009.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• Chuỗi \(p\) gồm một hoặc nhiều số hạng nối với nhau bằng dấu '+'. Nó sẽ không bắt đầu hoặc kết thúc bằng dấu '+'. Sẽ có tối đa 5 số hạng cho mỗi \(p\). Mỗi số hạng gồm ít nhất 1 và tối đa 4 chữ cái viết thường, được sắp xếp theo thứ tự không giảm. Không có hai số hạng nào trong cùng một đa thức giống nhau.
• Mỗi từ không rỗng, chỉ gồm các chữ cái tiếng Anh viết thường và không dài quá 50 ký tự. Không có từ nào bị lặp lại trong cùng một từ điển.

Phân nhóm

• Small dataset: \(1 \le \mathbf{n} \le 20\), \(1 \le \mathbf{K} \le 5\).
• Large dataset: \(1 \le \mathbf{n} \le 100\), \(1 \le \mathbf{K} \le 10\).

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

2
ehw+hwww 5
6
where
when
what
whether
who
whose
a+e+i+o+u 3
4
apple
orange
watermelon
banana

Case #1: 15 1032 7522 6864 253
Case #2: 12 96 576

Nguồn

Google Code Jam 2009, Vòng 3, bài Alphabetomials.

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

Sokoban là trò chơi Nhật Bản, tên gọi có nghĩa là “người giữ kho”. Bạn phải đẩy các thùng tới ô đích. Muốn đẩy một thùng, cả ô phía sau (nơi đứng) và ô phía trước nó phải trống. Mỗi lần chỉ đẩy một thùng; không được đẩy thùng hay đứng ra ngoài bàn.

Trong hình, thùng 1 đẩy được theo bốn hướng; thùng 2 chỉ theo đông hoặc tây vì ô phía nam không trống; thùng 3 không đẩy được; thùng 4 chỉ theo đông hoặc tây vì có tường phía nam.

Sokoban đã được chứng minh là một bài toán đầy đủ PSPACE, nhưng ở đây ta xét một biến thể dễ hơn. Sokoban đã được chứng minh là một bài toán đầy đủ PSPACE, nhưng ở đây ta xét một biến thể dễ hơn. Ở biến thể này, các thùng chứa nam châm mạnh và gần như luôn phải dính nhau. Trạng thái ổn định nghĩa là mọi thùng liên thông qua cạnh. Nếu một lần đẩy làm chúng mất liên thông, ta vào chế độ nguy hiểm và lần đẩy kế tiếp bắt buộc khôi phục liên thông.

Nếu đẩy thùng phía bắc sang tây, ta vào chế độ nguy hiểm:

Sau đó có thể đẩy chính thùng ấy xuống nam để ổn định lại:

Cho bàn, cấu hình ban đầu và cấu hình đích. Hãy tìm số lần đẩy thùng ít nhất, hoặc kết luận không thể giải. Cả cấu hình đầu và cuối đều không nguy hiểm. Người giữ kho có thể nhảy tức thời tới bất kỳ ô trống nào.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test bắt đầu bằng \(R,C\), rồi \(R\) dòng, mỗi dòng \(C\) ký tự: . ô trống, # tường, x đích, o thùng, w vừa là thùng vừa là đích. Số thùng bằng số đích.

Dữ liệu ra

In Case #X: K, với \(K\) là số lần đẩy nhỏ nhất, hoặc -1 nếu không thể giải.

Ràng buộc

• \(1 \le T \le 50\), \(1 \le R,C \le 12\); bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: 1–2 thùng.
• Lớn: 1–5 thùng.

Đ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
5 4
....
#..#
#xx#
#oo#
#..#
7 7
.######
.x....#
.x....#
..#oo.#
..#...#
.######
.######
4 10
##########
#.x...o..#
#.x...o..#
##########
3 4
.#x.
.ow.
....

Case #1: 2
Case #2: 8
Case #3: 8
Case #4: 2

Nguồn

Google Code Jam 2009, Vòng 3, bài EZ-Sokoban.

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

Một đội bóng sẽ đứng thành các hàng để chụp ảnh. Vị trí của mỗi cầu thủ được xác định bởi hai số nguyên \(x\) và \(y\), trong đó \(y\) là số thứ tự của hàng, và \(x\) là khoảng cách của cầu thủ đó tính từ mép trái của hàng. Các giá trị \(x\) đều khác nhau.

Để bức ảnh trở nên thú vị hơn, bạn muốn đảm bảo rằng những cầu thủ đứng gần nhau phải mặc áo màu khác nhau. Để thực hiện điều này, bạn đặt ra quy tắc sau:

Với mỗi cầu thủ \(P\):

• Cầu thủ gần nhất bên phải \(P\) trong cùng một hàng (nếu có) phải có màu áo khác.
• Cầu thủ gần nhất bên phải \(P\) ở hàng trước đó (nếu có) phải có màu áo khác.
• Cầu thủ gần nhất bên phải \(P\) ở hàng tiếp theo (nếu có) phải có màu áo khác.

Nói một cách chính xác hơn, nếu có hai cầu thủ ở vị trí \((x_1, y_1)\) và \((x_2, y_2)\), với \(x_1 < x_2\), thì hai cầu thủ đó phải có màu áo khác nhau nếu:

• \(y_1 - 1 \le y_2 \le y_1 + 1\), và
• không tồn tại \(x_3\) sao cho có một cầu thủ ở \((x_3, y_2)\) và \(x_1 < x_3 < x_2\).

Hãy tìm số lượng màu áo tối thiểu cần thiết để có thể thực hiện được điều này.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên \(T\), là số lượng bộ dữ liệu. Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa số nguyên \(N\), số lượng cầu thủ, tiếp theo là \(N\) dòng có dạng:

x y

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy xuất ra:

Case #X: c

Ràng buộc

• \(1 \le T \le 100\)
• \(1 \le x \le 1000\)
• Các giá trị \(x\) đều khác nhau.

Phân nhóm

• Small dataset: \(1 \le y \le 15, 1 \le N \le 100\).
• Large dataset: \(1 \le y \le 30, 1 \le N \le 1000\).

Đ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
3
10 10
8 15
12 7
5
1 1
2 1
3 1
4 1
5 1
3
1 1
2 2
3 1

Case #1: 1
Case #2: 2
Case #3: 3

Nguồn

Google Code Jam 2009, Vòng 3, bài Football Team.

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

Một số nguyên dương được gọi là số đối xứng (palindrome) nếu biểu diễn thập phân của nó (không có các chữ số 0 ở đầu) là một chuỗi đối xứng (đọc từ trái sang phải hay từ phải sang trái đều giống nhau). Ví dụ: các số 5, 77, 363, 4884, 11111, 12121 và 349943 là các số đối xứng.

Một đoạn các số nguyên được gọi là thú vị nếu nó chứa một số lượng chẵn các số đối xứng. Đoạn \([L, R]\) với \(L \le R\) được định nghĩa là dãy các số nguyên từ \(L\) đến \(R\) (bao gồm cả hai đầu): \((L, L+1, L+2, \dots, R-1, R)\). \(L\) và \(R\) lần lượt là số đầu tiên và số cuối cùng của đoạn.

Đoạn \([L_1, R_1]\) được gọi là đoạn con của \([L, R]\) nếu \(L \le L_1 \le R_1 \le R\). Nhiệm vụ của bạn là xác định xem có bao nhiêu đoạn con thú vị của \([L, R]\).

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, T. T bộ test theo sau. Mỗi bộ test nằm trên một dòng chứa hai số nguyên dương L và R (theo thứ tự đó), cách nhau bởi một khoảng trắng.

Dữ liệu ra

Với mỗi bộ test, xuất ra một dòng. Dòng đó phải chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng đoạn con thú vị của \([L, R]\), lấy modulo \(1000000007\).

Ràng buộc

• \(1 \le \mathbf{T} \le 120\)

Phân nhóm

• Small dataset: \(1 \le \mathbf{L} \le \mathbf{R} \le 10^{13}\)
• Large dataset: \(1 \le \mathbf{L} \le \mathbf{R} \le 10^{100}\)

Đ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
1 2
1 7
12 110

Case #1: 1
Case #2: 12
Case #3: 2466

Nguồn

Google Code Jam 2009, Vòng 3, bài Interesting Ranges.

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