Google Code Jam 2008 - EMEA Semifinal

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Google Code Jam 2008 - Bus Stops 34 7.0s 1G
2 Google Code Jam 2008 - Painting a Fence 20 1.0s 1G
3 Google Code Jam 2008 - Rainbow Trees 24 1.0s 1G
4 Google Code Jam 2008 - Scaled Triangle 22 1.0s 1G

1. Google Code Jam 2008 - Bus Stops

Điểm: 34 Thời gian: 7.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Tại Thành phố Thứ nhất của Sao Hỏa có \(N\) trạm xe buýt, tất cả được sắp xếp trên một đường thẳng có chiều dài \(N-1\) km. Thị trưởng thích mọi thứ đơn giản, vì vậy ông đã đánh số các trạm xe buýt từ \(1\) đến \(N\), và các trạm liền kề cách nhau đúng \(1\) km.

Cũng có \(K\) chiếc xe buýt trong thành phố. Thị trưởng phải lập kế hoạch lịch trình xe buýt và ông muốn biết có bao nhiêu cách để thực hiện điều đó. Con số này có thể rất lớn. May mắn thay, có một vài ràng buộc:

  • Vào đầu ngày, tất cả các xe buýt đều ở \(K\) trạm xe buýt đầu tiên (mỗi trạm một xe).
  • Các xe buýt chỉ di chuyển từ trái sang phải (trạm \(1\) là trạm ngoài cùng bên trái).
  • Vào cuối ngày, tất cả các xe buýt phải ở \(K\) trạm xe buýt cuối cùng (mỗi trạm một xe).
  • Tại mỗi trạm xe buýt, chính xác một xe buýt phải dừng lại.
  • Đối với cùng một xe buýt, khoảng cách giữa hai điểm dừng liên tiếp bất kỳ tối đa là \(P\) km.

Hãy giúp thị trưởng đánh giá số lượng lịch trình. Tuy nhiên, đừng đưa cho ông ấy tin quá xấu (quá nhiều lịch trình), vì vậy chỉ cần xuất ra số lượng thực tế theo modulo \(30031\).

Dữ liệu vào

Dòng đầu tiên trong tệp đầu vào là số lượng bộ test \(T\).
Mỗi dòng trong \(T\) dòng tiếp theo chứa 3 số nguyên cách nhau bởi một khoảng trắng: \(N\), \(K\) và \(P\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất ra số cách lập kế hoạch lịch trình xe buýt (modulo \(30031\)) theo định dạng Case #t: [số cách modulo 30031] với t là số thứ tự của bộ test, bắt đầu từ 1.

Ràng buộc

  • \(1 < T \le 30\)
  • \(1 < P \le 10\)
  • \(K < N\)
  • \(1 < K \le P\)

Phân nhóm

  • Small dataset (Test set 1): \(1 < N < 1000\)
  • Large dataset (Test set 2): \(1 < N < 10^9\)

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

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 8/34 23,53%
Test Set 2 26/34 76,47%

Ví dụ

Ví dụ 1

Input 
3
10 3 3
5 2 3
40 4 8
Output 
Case #1: 1
Case #2: 3
Case #3: 7380
Note

Hãy gọi tên các xe buýt là: A, B, C...

  • Trong trường hợp đầu tiên, chỉ có một cách lập kế hoạch lịch trình khả thi: A → 1, 4, 7, 10. B → 2, 5, 8. C → 3, 6, 9.
  • Trong trường hợp thứ hai, các cách lập kế hoạch khả thi là:
    • (A → 1, 3, 5. B → 2, 4),
    • (A → 1, 3, 4. B → 2, 5),
    • (A → 1, 4. B → 2, 3, 5).

Nguồn

Google Code Jam 2008, Vòng bán kết EMEA, bài Bus Stops.

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

2. Google Code Jam 2008 - Painting a Fence

Điểm: 20 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bạn cần thuê một số người để sơn một hàng rào. Hàng rào gồm \(10000\) đoạn liên tiếp, được đánh số từ \(1\) đến \(10000\).

Bạn nhận được một số lời đề nghị từ các thợ sơn. Mỗi thợ sơn đề nghị sơn một đoạn liên tiếp của hàng rào bằng một màu cụ thể. Bạn cần chấp nhận một tập hợp các lời đề nghị sao cho:

  • Mọi đoạn của hàng rào đều được sơn.
  • Có tối đa \(3\) màu được sử dụng để sơn hàng rào.

Nếu có thể thỏa mãn hai yêu cầu này, hãy tìm số lượng lời đề nghị tối thiểu mà bạn phải chấp nhận.

Dữ liệu vào

  • Một dòng chứa số nguyên \(T\), số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu:

  • Một dòng chứa số nguyên \(N\), số lượng lời đề nghị.
  • \(N\) dòng, mỗi dòng cho một lời đề nghị, chứa "\(C\) \(A\) \(B\)" trong đó \(C\) là tên màu (một chuỗi in hoa tối đa \(10\) ký tự), \(A\) là đoạn đầu tiên và \(B\) là đoạn cuối cùng được sơn. \(1 \le A \le B \le 10000\).

Dữ liệu ra

  • \(T\) dòng, mỗi dòng cho một bộ dữ liệu theo thứ tự xuất hiện, chứa chuỗi "Case #\(X\): \(Y\)", trong đó \(X\) là số thứ tự bộ dữ liệu, và \(Y\) là số lượng lời đề nghị tối thiểu cần chấp nhận, hoặc "Case #\(X\): IMPOSSIBLE" nếu không có tập hợp lời đề nghị nào thỏa mãn.

Ràng buộc

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

Phân nhóm

  • Tập dữ liệu nhỏ (Test set 1 - Visible): \(1 \le N \le 10\).
  • Tập dữ liệu lớn (Test set 2 - Hidden): \(1 \le N \le 300\).

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

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 7/20 35%
Test Set 2 13/20 65%

Ví dụ

Ví dụ 1

Input 
5
2
BLUE 1 5000
RED 5001 10000
3
BLUE 1 6000
RED 2000 8000
WHITE 7000 10000
4
BLUE 1 3000
RED 2000 5000
ORANGE 4000 8000
GREEN 7000 10000
2
BLUE 1 4000
RED 4002 10000
3
BLUE 1 6000
RED 4000 10000
ORANGE 3000 8000
Output 
Case #1: 2
Case #2: 3
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE
Case #5: 2
Note

Giải thích ví dụ:

  • Trong trường hợp đầu tiên, chấp nhận cả hai lời đề nghị sẽ sơn chính xác toàn bộ hàng rào, mỗi người sơn \(5000\) đoạn, không chồng lấn.
  • Trong trường hợp thứ hai, các thợ sơn sẽ sơn chồng lấn lên nhau, điều này có thể chấp nhận được.
  • Trong trường hợp thứ ba, chấp nhận cả bốn lời đề nghị sẽ bao phủ toàn bộ hàng rào, nhưng nó sử dụng \(4\) màu khác nhau, nên không được chấp nhận.
  • Trong trường hợp thứ tư, đoạn \(4001\) không thể được sơn.
  • Trong trường hợp thứ năm, chúng ta chỉ cần chấp nhận lời đề nghị thứ nhất và thứ hai là có thể sơn thành công hàng rào.

Nguồn

Google Code Jam 2008, Vòng bán kết EMEA, bài Painting a Fence.

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

3. Google Code Jam 2008 - Rainbow Trees

Điểm: 24 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Trong lý thuyết đồ thị, một cây là một đồ thị đơn vô hướng, liên thông và không có chu trình. Một cây có \(n\) nút luôn có \(n - 1\) cạnh.

Một đường đi trong cây là một dãy các cạnh phân biệt liên tiếp nhau (mỗi cặp cạnh liên tiếp trong đường đi chia sẻ chung một đỉnh).

Xét một cây có \(n\) đỉnh và \(n - 1\) cạnh. Bạn có thể tô mỗi cạnh bằng một trong \(k\) màu.

Một cách tô màu các cạnh được gọi là tô màu cầu vồng (rainbow coloring) nếu trong mọi đường đi có độ dài 2 hoặc 3 cạnh, màu của các cạnh đều khác nhau. (Nghĩa là, cứ hai cạnh liên tiếp bất kỳ phải có màu khác nhau, và cứ ba cạnh liên tiếp bất kỳ phải có màu khác nhau).

Cho một cây và số lượng màu \(k\), hãy tìm số cách tô màu cầu vồng modulo \(1000000009\).

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, \(C\). Sau đó, với mỗi bộ trong số \(C\) bộ test:

  • Một dòng chứa hai số nguyên theo định dạng "\(n\) \(k\)". \(n\) là số nút trong cây, và \(k\) là số màu có sẵn.
  • \(n - 1\) dòng, mỗi dòng cho một cạnh, chứa hai số nguyên "\(x\) \(y\)", cho biết có một cạnh giữa nút \(x\) và nút \(y\). Các nút được đánh số từ 1 đến \(n\).

Dữ liệu ra

Với mỗi bộ test, xuất một dòng. Dòng đó phải chứa "Case #\(X\): \(Y\)", trong đó \(X\) là số thứ tự của bộ test (bắt đầu từ 1) và \(Y\) là đáp án cho bộ test đó.

Ràng buộc

  • \(1 \le k \le 1000000000\).
  • Tất cả các số hiệu nút nằm trong khoảng từ 1 đến \(n\), bao gồm cả hai đầu mút.

Phân nhóm

  • Small dataset (Test set 1): \(1 \le C \le 100\); \(2 \le n \le 20\).
  • Large dataset (Test set 2): \(1 \le C \le 40\); \(2 \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.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 9/24 37,5%
Test Set 2 15/24 62,5%

Ví dụ

Ví dụ 1

Input 
2
4 10
1 2
1 3
1 4
5 3
1 2
2 3
3 4
4 5
Output 
Case #1: 720
Case #2: 6
Note

Trong trường hợp đầu tiên, cây có bốn nút. Có các cạnh từ một nút đến mỗi nút trong ba nút còn lại. Mỗi cặp cạnh này đều kề nhau, vì vậy để có một cách tô màu cầu vồng, tất cả các cạnh phải có màu khác nhau. Do đó có \(10 \times 9 \times 8 = 720\) cách tô màu cầu vồng.

Trong trường hợp thứ hai, bản thân cây là một đường đi gồm 4 cạnh và có 3 màu. Ba cạnh đầu tiên phải có màu khác nhau, vì vậy có \(3 \times 2 \times 1\) cách tô màu cho chúng, và sau đó chỉ còn một lựa chọn cho cạnh thứ tư, do đó có 6 cách tô màu cầu vồng.

Nguồn

Google Code Jam 2008, Vòng bán kết EMEA, bài Rainbow Trees.

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

4. Google Code Jam 2008 - Scaled Triangle

Điểm: 22 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bạn được cho hai bức hình hình tam giác. Bức hình thứ hai là một phiên bản đã được dịch chuyển, xoay và thay đổi tỉ lệ của bức hình thứ nhất. Hai tam giác này được đặt trên bàn, với tam giác thứ hai nằm hoàn toàn bên trong (có thể chạm vào biên của) tam giác thứ nhất. Tam giác thứ hai luôn được thu nhỏ theo một tỉ lệ \(S\) nằm trong khoảng \(0 < S < 1\).

Bạn cần xử lý hình ảnh và tìm một điểm trong bức hình trùng với chính điểm đó trong phiên bản thu nhỏ. Nếu có nhiều hơn một giải pháp, bạn có thể trả về bất kỳ điểm nào. Nếu không có giải pháp, hãy in "No Solution" cho trường hợp đó.

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, \(N\). Sau đó, với mỗi bộ test, sẽ có hai dòng, mỗi dòng chứa sáu số nguyên cách nhau bởi dấu cách -- tọa độ của một trong các tam giác -- theo định dạng "\(x_1\) \(y_1\) \(x_2\) \(y_2\) \(x_3\) \(y_3\)". Điểm \((x_1, y_1)\) trong tam giác thứ nhất tương ứng với cùng một góc của bức hình với điểm \((x_1, y_1)\) trong tam giác thứ hai, và tương tự cho \((x_2, y_2)\) và \((x_3, y_3)\).

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #\(x\): " theo sau là hai số thực biểu diễn tọa độ của điểm trùng nhau cách nhau bởi một dấu cách, hoặc chuỗi "No Solution". 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.

Ràng buộc

  • \(1 \le N \le 10\).
  • Tọa độ của các điểm sẽ là các số nguyên nằm trong khoảng từ \(-10\,000\) đến \(10\,000\). Ba điểm trong mỗi tam giác sẽ không thẳng hàng.

Phân nhóm

  • Small dataset (Test set 1 - Visible): Tất cả các bộ test sẽ chứa các tam giác vuông cân (tức là các góc của tam giác sẽ là 45 độ, 45 độ và 90 độ).
  • Large dataset (Test set 2 - Hidden): Các tam giác có thể có hình dạng bất kỳ.

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

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 9/22 40,91%
Test Set 2 13/22 59,09%

Ví dụ

Ví dụ 1

Input 
2
0 0 0 2 2 0
0 0 0 1 1 0
10 0 0 10 0 0
3 3 1 1 3 1
Output 
Case #1: 0.000000 0.000000
Case #2: 2.692308 1.538462

Nguồn

Google Code Jam 2008, Vòng bán kết EMEA, bài Scaled Triangle.

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