Google Code Jam 2009 - Round 1C

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 2009 - All Your Base 23 1.0s 1G
2 Google Code Jam 2009 - Bribe the Prisoners 50 1.0s 1G
3 Google Code Jam 2009 - Center of Mass 27 1.0s 1G

1. Google Code Jam 2009 - All Your Base

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

Vào năm 2100, người ngoài hành tinh đến Trái Đất. Họ để lại một thông điệp bằng ngôn ngữ bí ẩn cùng một dãy ký hiệu. Ta kết luận rằng dãy ký hiệu biểu diễn số giây còn lại trước khi chiến tranh bắt đầu.

Mỗi ký hiệu là một chữ số, nhưng ta không biết giá trị của từng ký hiệu hay cơ số họ dùng. Chẳng hạn, ab2ac999 có thể là 31536000 trong hệ 10 (đúng một năm), hoặc 12314555 trong hệ 6 (398951 giây, tức khoảng bốn ngày rưỡi). Ta biết số đó dương, chữ số đầu không phải 0 và cơ số không phải 1.

Hãy tìm số giây nhỏ nhất có thể trước khi chiến tranh bắt đầu.

Dữ liệu vào

Dòng đầu chứa số nguyên \(T\). Mỗi trong \(T\) dòng tiếp theo là một chuỗi chỉ gồm a-z và 0-9, không có dấu cách hay dấu câu. Các test độc lập; cơ số và ý nghĩa ký hiệu có thể khác nhau.

Dữ liệu ra

Với mỗi test, in Case #X: V, trong đó \(X\) đánh số từ 1 và \(V\) là số giây nhỏ nhất.

Ràng buộc

  • \(1 \le T \le 100\).
  • Đáp án không vượt quá \(10^{18}\).

Phân nhóm

  • Nhỏ: độ dài mỗi chuỗi từ 1 đến 9.
  • Lớn: độ dài mỗi chuỗi từ 1 đến 60.

Đ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/23 34,78%
Test Set 2 15/23 65,22%

Ví dụ

Ví dụ 1

Input 
3
11001001
cats
zig
Output 
Case #1: 201
Case #2: 75
Case #3: 11

Nguồn

Google Code Jam 2009, Vòng 1C, bài All Your Base.

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 2009 - Bribe the Prisoners

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

Trong một vương quốc, có các phòng giam (được đánh số từ 1 đến \(P\)) được xây dựng tạo thành một đoạn thẳng. Các phòng số \(i\) và \(i+1\) nằm cạnh nhau, và các tù nhân ở các phòng cạnh nhau được gọi là "hàng xóm". Một bức tường có cửa sổ ngăn cách các phòng cạnh nhau, và hàng xóm có thể giao tiếp qua cửa sổ đó.

Tất cả tù nhân sống trong hòa bình cho đến khi một tù nhân được thả. Khi điều đó xảy ra, những người hàng xóm của tù nhân được thả sẽ biết tin, và mỗi người lại truyền tin này cho hàng xóm khác của mình. Tù nhân đó lại truyền tiếp cho hàng xóm khác của anh ta, và cứ thế cho đến khi tin tức chạm đến một tù nhân không còn hàng xóm nào khác (vì anh ta ở phòng 1, hoặc phòng \(P\), hoặc phòng bên cạnh đang trống). Một tù nhân khi phát hiện ra một tù nhân khác đã được thả sẽ tức giận đập phá mọi thứ trong phòng mình, trừ khi anh ta được hối lộ bằng một đồng tiền vàng. Vì vậy, sau khi thả một tù nhân ở phòng \(A\), tất cả các tù nhân đang ở hai bên phòng \(A\) - cho đến phòng 1, phòng \(P\) hoặc một phòng trống - cần phải được hối lộ.

Giả sử rằng mỗi phòng giam ban đầu có đúng một tù nhân, và mỗi ngày chỉ có thể thả một tù nhân. Cho danh sách \(Q\) tù nhân sẽ được thả trong \(Q\) ngày, hãy tìm tổng số đồng tiền vàng tối thiểu cần dùng để hối lộ nếu các tù nhân có thể được thả theo bất kỳ thứ tự nào.

Lưu ý rằng mỗi lần hối lộ chỉ có tác dụng trong một ngày. Nếu một tù nhân đã được hối lộ hôm qua nghe tin về một tù nhân khác được thả hôm nay, anh ta cần phải được hối lộ lần nữa.

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\). \(N\) bộ test theo sau. Mỗi bộ test gồm 2 dòng.
Dòng đầu tiên có định dạng:

P Q

trong đó \(P\) là số lượng phòng giam và \(Q\) là số lượng tù nhân sẽ được thả.
Tiếp theo là một dòng chứa \(Q\) số phòng khác nhau (của các tù nhân sẽ được thả), cách nhau bởi dấu cách, được sắp xếp theo thứ tự tăng dần.

Dữ liệu ra

Với mỗi bộ test, xuất một dòng có định dạng:

Case #X: C

trong đó \(X\) là số thứ tự bộ test, bắt đầu từ 1, và \(C\) là số lượng đồng tiền vàng tối thiểu cần thiết.

Ràng buộc

  • \(1 \le N \le 100\)
  • \(Q \le P\)
  • Mỗi số phòng nằm trong khoảng từ 1 đến \(P\), bao gồm cả hai đầu.

Phân nhóm

  • Small dataset:

    • \(1 \le P \le 100\)
    • \(1 \le Q \le 5\)

    • Large dataset:

    • \(1 \le P \le 10000\)

    • \(1 \le Q \le 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.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 15/50 30%
Test Set 2 35/50 70%

Ví dụ

Ví dụ 1

Input 
2
8 1
3
20 3
3 6 14
Output 
Case #1: 7
Case #2: 35
Note

Ghi chú

Trong ví dụ thứ hai, đầu tiên bạn thả người ở phòng 14, sau đó là phòng 6, rồi đến phòng 3. Số đồng tiền vàng cần thiết là \(19 + 12 + 4 = 35\). Nếu thay vào đó bạn thả người ở phòng 6 trước, chi phí sẽ là \(19 + 4 + 13 = 36\).

Nguồn

Google Code Jam 2009, Vòng 1C, bài Bribe the Prisoners.

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 2009 - Center of Mass

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

Bạn đang nghiên cứu một đàn gồm \(N\) con đom đóm. Mỗi con đom đóm đang di chuyển trên một đường thẳng với tốc độ không đổi. Bạn đang đứng ở tâm của vũ trụ, tại vị trí \((0, 0, 0)\). Mỗi con đom đóm có khối lượng như nhau và bạn muốn biết tâm của đàn đom đóm sẽ tiến gần đến vị trí của bạn (gốc tọa độ) như thế nào.

Bạn biết vị trí và vận tốc của mỗi con đom đóm tại thời điểm \(t = 0\), và chỉ quan tâm đến \(t \ge 0\). Các con đom đóm có vận tốc không đổi và có thể đi xuyên qua mọi không gian, bao gồm cả nhau và cả bạn. Gọi \(M(t)\) là vị trí tâm khối của \(N\) con đom đóm tại thời điểm \(t\). Gọi \(d(t)\) là khoảng cách giữa vị trí của bạn và \(M(t)\) tại thời điểm \(t\). Tìm giá trị nhỏ nhất của \(d(t)\), \(d_{min}\), và thời điểm sớm nhất khi \(d(t) = d_{min}\), \(t_{min}\).

Dữ liệu vào

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

x y z vx vy vz

Mỗi dòng này mô tả một con đom đóm: \((x, y, z)\) là vị trí ban đầu của nó tại thời điểm \(t = 0\), và \((vx, vy, vz)\) là vận tốc của nó.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất:

Case #X: dmin tmin

trong đó \(X\) là số thứ tự bộ thử nghiệm, bắt đầu từ 1. 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.

Ràng buộc

  • Tất cả các số trong dữ liệu vào đều là số nguyên.
  • \(1 \le T \le 100\)
  • Các giá trị của \(x, y, z, vx, vy\) và \(vz\) sẽ nằm trong khoảng từ \(-5000\) đến \(5000\), bao gồm cả hai đầu mút.

Phân nhóm

  • Tập dữ liệu nhỏ (Small dataset): \(3 \le N \le 10\).
  • Tập dữ liệu lớn (Large dataset): \(3 \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 10/27 37,04%
Test Set 2 17/27 62,96%

Ví dụ

Ví dụ 1

Input 
3
3
3 0 -4 0 0 3
-3 -2 -1 3 0 0
-3 -1 2 0 3 0
3
-5 0 0 1 0 0
-7 0 0 1 0 0
-6 3 0 1 0 0
4
1 2 3 1 2 3
3 2 1 3 2 1
1 0 0 0 0 -1
0 10 0 0 -10 -1
Output 
Case #1: 0.00000000 1.00000000
Case #2: 1.00000000 6.00000000
Case #3: 3.36340601 1.00000000

Ghi chú

Cho \(N\) điểm \((x_i, y_i, z_i)\), tâm khối của chúng là điểm \((x_c, y_c, z_c)\), trong đó:

xc = (x1 + x2 + ... + xN) / N
yc = (y1 + y2 + ... + yN) / N
zc = (z1 + z2 + ... + zN) / N

Nguồn

Google Code Jam 2009, Vòng 1C, bài Center of Mass.

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