Một lưới hình chữ nhật với các chữ cái tiếng Anh viết thường trong mỗi ô được gọi là sắp xếp kép (doubly sorted) nếu trong mỗi hàng, các chữ cái không giảm từ trái sang phải, và trong mỗi cột, các chữ cái không giảm từ trên xuống dưới. Trong các ví dụ sau, hai lưới đầu tiên được sắp xếp kép, trong khi hai lưới còn lại thì không:

abc    ace    aceg    base
def    ade    cdef    base
ghi    bdg    xxyy    base

Bạn được cho một lưới đã điền một phần, trong đó một số ô đã có sẵn chữ cái. Nhiệm vụ của bạn là tính số cách bạn có thể điền vào các ô còn lại để lưới kết quả được sắp xếp kép. Kết quả có thể là một số lớn; bạn cần đưa ra số cách chia dư cho 10007.

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 tiếp nối theo sau. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên R và C, lần lượt là số hàng và số cột. Tiếp theo là R dòng, mỗi dòng chứa một chuỗi có độ dài C, mô tả lưới đã điền một phần. Mỗi ký tự trong lưới là một chữ cái tiếng Anh viết thường, hoặc dấu '.', cho biết ô đó chưa được điền.

Dữ liệu ra

Với mỗi bộ test, hãy xuất 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 lưới sắp xếp kép có thể có, chia dư cho 10007.

Ràng buộc

• 1 ≤ T ≤ 40.
• Mỗi ký tự trong lưới đã điền một phần là '.' hoặc một chữ cái tiếng Anh viết thường.

Phân nhóm

• Small dataset: 1 ≤ R, C ≤ 4.
• Large dataset: 1 ≤ R, C ≤ 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ụ

3
2 2
ad
c.
3 3
.a.
a.z
.z.
4 4
....
.g..
.cj.
....

Case #1: 23
Case #2: 7569
Case #3: 0

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Doubly-sorted Grid.

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

Trong một căn phòng hình vuông lớn, có hai nguồn sáng điểm: một nguồn màu đỏ và một nguồn màu xanh lá cây. Ngoài ra còn có \(n\) cột hình trụ.

Ánh sáng truyền theo đường thẳng và bị hấp thụ bởi các bức tường và cột. Do đó, các cột sẽ đổ bóng: chúng không cho ánh sáng đi qua. Có những vị trí trong phòng không có ánh sáng nào chiếu tới (màu đen), những nơi chỉ có một trong hai nguồn sáng chiếu tới (đỏ hoặc xanh lá), và những nơi cả hai nguồn sáng đều chiếu tới (vàng). Hãy tính tổng diện tích của mỗi loại trong bốn màu này trong phòng. Không tính diện tích của các cột.

Dữ liệu vào

• Dòng đầu tiên chứa số lượng bộ thử nghiệm, \(T\).

Mỗi bộ thử nghiệm bao gồm, theo thứ tự:

• Một dòng chứa tọa độ \(x\), \(y\) của nguồn sáng đỏ.
• Một dòng chứa tọa độ \(x\), \(y\) của nguồn sáng xanh lá.
• Một dòng chứa số lượng cột \(n\).
• \(n\) dòng mô tả các cột. Mỗi dòng chứa 3 số \(x\), \(y\), \(r\). Cột là một hình tròn có tâm (\(x\), \(y\)) và bán kính \(r\).

Căn phòng là hình vuông được mô tả bởi \(0 \le x, y \le 100\). Các cột, tường phòng và nguồn sáng đều rời nhau, chúng không chồng lấn hoặc chạm nhau.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy in ra:

Case #X:
Black: B
Red: R
Green: G
Yellow: Y

trong đó \(X\) là số thứ tự bộ thử nghiệm, bắt đầu từ 1, và mỗi diện tích là một số thực.

Bất kỳ câu trả lời nào có sai số tuyệt đối hoặc tương đối không quá \(10^{-5}\) đều sẽ được chấp nhận.

Case #X:
black area
red area
green area
yellow area

Ràng buộc

Tất cả các số nhập vào đều là số nguyên.
\(1 \le T \le 15\)
\(0 \le x, y \le 100\)
\(1 \le r \le 49\)

Phân nhóm

• Small dataset: \(0 \le n \le 1\).
• Large dataset: \(0 \le n \le 50\).

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

1
5 50
95 50
1
50 50 10

Case #1:
0.7656121
1437.986
1437.986
6809.104

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Lights.

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

Bạn có \(2n\) viên bi trên một lưới ô vuông. Các viên bi được tô bằng \(n\) màu khác nhau sao cho có đúng 2 viên bi mỗi màu. Các viên bi được đặt tại các tọa độ \((1,0), (2,0), \dots, (2n, 0)\).

Nhiệm vụ của bạn là vẽ một đường đi cho mỗi màu để nối hai viên bi cùng màu đó. Mỗi đường đi phải bao gồm các đoạn thẳng nằm ngang hoặc thẳng đứng giữa các điểm lưới. Không có hai đường đi nào được giao nhau hoặc chạm nhau. Không có đường đi nào được cắt đường thẳng \(y=0\). Mỗi đường đi chỉ có thể chạm đường thẳng \(y=0\) tại vị trí của hai viên bi mà nó đang nối, vì vậy đoạn thẳng đầu tiên và cuối cùng của mỗi đường đi phải là đoạn thẳng đứng.

Cho một cách sắp xếp các viên bi, hãy trả về chiều cao tối thiểu của một giải pháp, hoặc trả về -1 nếu không tồn tại giải pháp. Chiều cao được định nghĩa là hiệu giữa tọa độ \(Y\) cao nhất và thấp nhất của các đường đi được sử dụng.

Một ví dụ:

red red blue yellow blue yellow

Một giải pháp có thể là:

 +---+    +-----------+
 |   |    |           |
red red blue yellow blue yellow
                 |           |
                 +-----------+

Chiều cao tối thiểu là 2 trong trường hợp này.

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 tiếp theo. Dòng đầu tiên của mỗi bộ test chứa \(n\), số lượng màu khác nhau của các viên bi. Dòng tiếp theo chứa một chuỗi gồm \(2n\) từ cách nhau bởi dấu cách, tương ứng với màu sắc của các viên bi, theo thứ tự từ trái sang phải. Mỗi màu là một chuỗi các chữ cái tiếng Anh viết thường ('a' .. 'z') dài không quá 10 ký tự. Sẽ có đúng \(n\) màu khác nhau và mỗi màu sẽ xuất hiện đúng hai lần.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(x\): ", trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), tiếp theo là chiều cao của bất kỳ giải pháp tối ưu nào, hoặc -1 nếu không tồn tại giải pháp.

Ràng buộc

• \(1 \le T \le 50\).

Phân nhóm

• Small dataset: \(1 \le n \le 20\).
• Large dataset: \(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ụ

4
3
red red blue yellow blue yellow
3
red blue yellow red blue yellow
3
red blue yellow blue yellow red
3
red red blue blue yellow yellow

Case #1: 2
Case #2: -1
Case #3: 3
Case #4: 1

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Marbles.

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

Min Perimeter

Bạn sẽ được cho một tập hợp các điểm với tọa độ nguyên. Nhiệm vụ của bạn là tính chu vi nhỏ nhất của một tam giác có các đỉnh phân biệt từ tập hợp các điểm này.

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 chứa một số nguyên \(n\) ở dòng đầu tiên, là số lượng điểm trong tập hợp. \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i\). Đây là tọa độ của điểm thứ \(i\). Không có nhiều hơn một điểm tại cùng một tọa độ.

Dữ liệu ra

Với mỗi bộ test, xuất ra:

Case #X: Y

trong đó \(X\) là số thứ tự của bộ test và \(Y\) là chu vi nhỏ nhất. Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá \(10^{-5}\) sẽ được coi là chính xác. Các tam giác suy biến — tam giác có diện tích bằng 0 — được chấp nhận.

Ràng buộc

• \(1 \le T \le 15\)
• \(0 \le x_i, y_i \le 10^9\)

Phân nhóm

• Small dataset: \(3 \le n \le 10000\).
• Large dataset: \(3 \le n \le 1000000\).

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

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

Case #1: 5.656854

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Min Perimeter.

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

Bạn được cho một mạng lưới các tháp phát sóng không dây. Mỗi tháp có một phạm vi hoạt động và có thể gửi dữ liệu đến các tháp lân cận miễn là khoảng cách giữa chúng nhỏ hơn hoặc bằng phạm vi của tháp gửi.

Các tháp hiện đang sử dụng giao thức truyền thông cũ A, nhưng có một giao thức mới tốt hơn là B. Chúng ta đang cân nhắc nâng cấp một số tháp để gửi dữ liệu bằng giao thức B nhằm đạt được băng thông tốt hơn.

Có một ràng buộc quan trọng: nếu một tháp \(T\) đang sử dụng giao thức mới B, thì mọi tháp nằm trong phạm vi của \(T\) cũng phải đang chạy giao thức B để chúng có thể hiểu được dữ liệu gửi từ \(T\). Điều ngược lại là không cần thiết — các tháp chạy giao thức mới B vẫn có thể nhận dữ liệu từ các tháp sử dụng giao thức cũ A.

Nhiệm vụ của bạn là chọn ra tập hợp các tháp tốt nhất để nâng cấp từ giao thức A lên giao thức B. Mỗi tháp khi nâng cấp sẽ đem lại một số điểm nhất định, điểm này có thể dương hoặc âm (đại diện cho giá trị thu được trừ đi chi phí lắp đặt). Hãy chọn tập hợp các tháp cần nâng cấp sao cho tổng số điểm của các tháp được nâng cấp là lớn nhất.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ thử nghiệm, \(T\).
Mỗi bộ thử nghiệm bắt đầu bằng số lượng tháp, \(n\).
\(n\) dòng tiếp theo, mỗi dòng chứa 4 số nguyên: \(x, y, r, s\). Chúng mô tả một tháp tại tọa độ \((x, y)\), có phạm vi hoạt động là \(r\) và điểm số (giá trị của việc nâng cấp lên giao thức mới) là \(s\).

Dữ liệu ra

Với mỗi bộ thử nghiệm, xuất ra:

Case #X: score

Ràng buộc

• \(1 \le T \le 55\)
• \(-10\,000 \le x, y \le 10\,000\)
• \(1 \le r \le 20\,000\)
• \(-1000 \le s \le 1000\)
• Không có hai tháp nào có cùng tọa độ.

Phân nhóm

• Tập dữ liệu nhỏ: \(1 \le n \le 15\).
• Tập dữ liệu lớn: \(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ụ

1
5
0 1 7 10
0 -1 7 10
5 0 1 -15
10 0 6 10
15 1 2 -20

Case #1: 5

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Wi-fi Towers.

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 năm mới mang đến một bộ lịch mới, những thử thách mới và nhiều niềm vui mới trong cuộc sống. Tuy nhiên, có một số thứ không bao giờ thay đổi. Vẫn còn nhiều cuộc thi lập trình tuyệt vời sắp được tổ chức, và niềm đam mê của nữ anh hùng Sphinny dành cho chúng vẫn không hề giảm bớt.

Có một số giải đấu mà Sphinny quan tâm. Mỗi giải đấu sẽ bao gồm một số vòng thi. Ban tổ chức của mỗi giải đấu chưa quyết định ngày bắt đầu giải đấu, nhưng đã quyết định sẽ có bao nhiêu vòng thi và mỗi vòng thi sẽ diễn ra sau ngày bắt đầu bao nhiêu ngày.

Trong một số tình huống, hai hoặc nhiều vòng thi (từ các giải đấu khác nhau) có thể được lên lịch vào cùng một ngày. Vì Sphinny rất thích giải quyết vấn đề, cô ấy sẽ hạnh phúc hơn nếu có nhiều vòng thi được lên lịch vào cùng một ngày hơn. Giá trị hạnh phúc của cô ấy được tính như sau: đối với mỗi ngày có \(S\) vòng thi, hạnh phúc của cô ấy sẽ tăng thêm \(S^2\). Hạnh phúc của cô ấy bắt đầu từ 0 (đừng lo lắng — 0 là một điểm khởi đầu hạnh phúc).

Trong hình dưới đây có ba giải đấu, mỗi giải được đại diện bởi một màu khác nhau, và tổng hạnh phúc của Sphinny là 20. Một giải đấu bắt đầu vào ngày thứ hai của năm, một giải bắt đầu vào ngày thứ năm của năm, và một giải bắt đầu vào ngày thứ sáu của năm.

Có \(N\) ngày trong năm. Mỗi giải đấu sẽ bắt đầu vào bất kỳ ngày nào trong \(N\) ngày với xác suất như nhau. Câu hỏi lớn cho năm nay là giá trị kỳ vọng của hạnh phúc của Sphinny là bao nhiêu.

Là một người cầu toàn, cô ấy sẽ không giải quyết vấn đề một cách xấp xỉ. Thay vào đó, cô ấy muốn biết kết quả chính xác. Số lượng giải đấu là \(T\), và có \(N^T\) cách chọn ngày bắt đầu của các giải đấu với xác suất như nhau. Cô ấy sẽ biểu diễn hạnh phúc kỳ vọng của mình dưới dạng \(K + A/B\), trong đó \(K\) và \(B\) là các số nguyên dương và \(A\) là một số nguyên không âm nhỏ hơn \(B\). Nếu \(A\) bằng 0 thì \(B\) phải bằng 1, ngược lại \(A\) và \(B\) không được có ước chung lớn hơn 1.

Nếu một giải đấu bắt đầu đủ muộn trong năm, một số vòng thi của nó có thể được lên lịch vào năm sau. Những vòng thi đó không đóng góp vào hạnh phúc của Sphinny trong năm nay.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào là một số nguyên duy nhất \(C\), số lượng bộ test. \(C\) bộ test tiếp theo. Dòng đầu tiên của mỗi bộ test có dạng:

N T

trong đó \(N\) là số ngày trong năm, và \(T\) là số lượng giải đấu. \(T\) dòng sau đó, mỗi dòng cho một giải đấu, theo định dạng:

m d2 d3 ... dm

cho biết có \(m\) vòng thi, và vòng thứ \(i\) sẽ được tổ chức vào ngày thứ \(d_i\) của giải đấu. Vòng đầu tiên của một giải đấu được tổ chức vào ngày 1 (\(d_1 = 1\)).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng có dạng:

Case #X: K+A/B

trong đó \(X\) là số thứ tự bộ test, bắt đầu từ 1, và \(K, A, B\) như đã mô tả ở trên.

Ràng buộc

• \(1 \le C \le 50\)
• \(1 \le N \le 10^9\)
• \(2 \le m \le 50\)
• \(1 < d_2 < d_3 < \dots < d_m \le 10000\)

Phân nhóm

• Small dataset: \(1 \le T \le 2\)
• Large dataset: \(1 \le T \le 50\)

Đ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
1 1
2 2
4 2
3 2 4
2 3

Case #1: 1+0/1
Case #2: 5+1/8

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Year of More 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.