Google Code Jam 2010 - Qualification Round

Trên Jamcode IX, ba Đại Sự Kiện xảy ra cách đây 26000, 11000 và 6000 slarbosecond. Sau 4000 slarbosecond, thời gian kể từ cả ba sự kiện đều là bội của 5000 — giá trị lớn nhất có thể — và “tận thế” đến.

Bạn sống trên Jamcode X, nơi có lời tiên tri: sau thời khắc phán xét, vào ngày kỷ niệm tối ưu đầu tiên của \(N\) Đại Sự Kiện, tận thế sẽ đến; 64 bit không cứu được bạn. Các sự kiện đã xảy ra và thời điểm được đo chính xác tới slarbosecond.

Thời khắc phán xét là hiện tại. Tại thời điểm \(y\ge0\) kể từ bây giờ, số slarbosecond kể từ mỗi sự kiện phải chia hết cho cùng một số nguyên lớn nhất có thể \(T\). Trong các \(y\) đạt \(T\) lớn nhất ấy, ngày kỷ niệm tối ưu là \(y\) nhỏ nhất. Hãy tính thời gian còn lại.

Dữ liệu vào

Dòng đầu là số test \(C\). Mỗi dòng tiếp theo gồm \(N\) rồi \(N\) số \(t_i\), số slarbosecond kể từ sự kiện \(i\).

Dữ liệu ra

In Case #x: y, trong đó \(y\) nhỏ nhất sao cho mọi \(t_i+y\) là bội của hệ số nguyên lớn nhất \(T\).

Ràng buộc

• \(1\le C\le100\); tồn tại \(i,j\) với \(t_i e t_j\).
• Thời gian 30 giây mỗi bộ; bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(2\le N\le3\), \(1\le t_i\le10^8\).
• Lớn: \(2\le N\le1000\), \(1\le t_i\le10^{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ụ

3
3 26000000 11000000 6000000
3 1 10 11
2 800000000000000000001 900000000000000000001

Case #1: 4000000
Case #2: 0
Case #3: 99999999999999999999

Hậu truyện

May thay, “tận thế” hóa ra là bản dịch nhầm của “bữa tiệc khổng lồ”. Không ai ở Jamcode IX báo lại vì họ đang vui quá.

Nguồn

Google Code Jam 2010, Vòng loại, bài Fair Warning.

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

Snapper là một thiết bị nhỏ thông minh, một đầu cắm vào ổ cắm điện (hoặc ổ cắm đầu ra của một Snapper khác), và đầu kia cung cấp một ổ cắm đầu ra để cắm đèn hoặc các thiết bị khác.

Khi một Snapper ở trạng thái BẬT (ON) và đang nhận được điện từ phích cắm đầu vào của nó, thì thiết bị kết nối với ổ cắm đầu ra của nó cũng sẽ nhận được điện. Khi bạn búng tay -- tạo ra một tiếng "tách" -- bất kỳ Snapper nào đang nhận được điện tại thời điểm búng tay sẽ chuyển đổi trạng thái giữa BẬT (ON) và TẮT (OFF).

Với hy vọng phá hủy vũ trụ bằng một điểm kỳ dị, tôi đã mua \(N\) thiết bị Snapper và xâu chuỗi chúng lại với nhau bằng cách cắm thiết bị đầu tiên vào ổ cắm điện, thiết bị thứ hai vào thiết bị đầu tiên, và cứ tiếp tục như vậy. Đèn được cắm vào thiết bị Snapper thứ \(N\).

Ban đầu, tất cả các Snapper đều ở trạng thái TẮT, vì vậy chỉ có thiết bị đầu tiên nhận được điện từ ổ cắm, và đèn tắt. Tôi búng tay một lần, làm thiết bị Snapper đầu tiên chuyển sang trạng thái BẬT và truyền điện cho thiết bị thứ hai. Tôi búng tay lần thứ hai, làm cả hai thiết bị Snapper chuyển trạng thái và sau đó ngay lập tức ngắt điện khỏi thiết bị thứ hai, để lại nó ở trạng thái BẬT nhưng không có điện. Tôi búng tay lần thứ ba, làm thiết bị Snapper đầu tiên chuyển trạng thái một lần nữa và truyền điện cho thiết bị thứ hai. Bây giờ cả hai thiết bị Snapper đều ở trạng thái BẬT, và nếu đèn của tôi được cắm vào thiết bị Snapper thứ hai, nó sẽ sáng.

Tôi tiếp tục làm việc này trong nhiều giờ. Liệu đèn sẽ sáng hay tắt sau khi tôi đã búng tay \(K\) lần? Đèn sáng khi và chỉ khi nó nhận được điện từ thiết bị Snapper mà nó được cắm vào.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(N\) và \(K\).

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là "ON" hoặc "OFF", cho biết trạng thái của bóng đèn.

Ràng buộc

• \(1 \le T \le 10,000\).

Phân nhóm

• Small dataset (Test set 1 - Visible):
• \(1 \le N \le 10\);
• \(0 \le K \le 100\);
• Large dataset (Test set 2 - Hidden):
• \(1 \le N \le 30\);
• \(0 \le K \le 10^8\);

Đ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
1 0
1 1
4 0
4 47

Case #1: OFF
Case #2: ON
Case #3: OFF
Case #4: ON

Nguồn

Google Code Jam 2010, Vòng loại, bài Snapper Chain.

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

Tàu lượn siêu tốc thật là vui! Có vẻ như tất cả những ai đến công viên giải trí đều muốn đi tàu lượn siêu tốc. Một số người đi một mình; những người khác đi theo nhóm và không muốn lên tàu trừ khi tất cả họ có thể đi cùng nhau. Và tất cả mọi người đã đi tàu lượn đều muốn đi thêm lần nữa. Một lượt đi tốn 1 Euro mỗi người; nhiệm vụ của bạn là tính xem tàu lượn siêu tốc sẽ kiếm được bao nhiêu tiền trong ngày hôm nay.

Tàu lượn có thể chứa tối đa \(k\) người cùng một lúc. Mọi người xếp hàng chờ theo từng nhóm. Các nhóm lần lượt lên tàu, từng nhóm một, cho đến khi không còn nhóm nào trong hàng hoặc không còn đủ chỗ cho nhóm tiếp theo; sau đó tàu sẽ chạy, dù có đầy chỗ hay không. Sau khi lượt đi kết thúc, tất cả hành khách trên lượt đó sẽ quay lại xếp hàng ở cuối hàng theo đúng thứ tự cũ. Tàu lượn sẽ chạy \(R\) lần trong một ngày.

Ví dụ, giả sử \(R=4\), \(k=6\), và có bốn nhóm người với kích thước: 1, 4, 2, 1.

• Lần chạy thứ nhất, hai nhóm đầu tiên [1, 4] sẽ đi, còn trống một chỗ (nhóm 2 người không vừa, và nhóm 1 người phía sau không thể đi trước họ). Sau đó họ quay lại cuối hàng, hàng đợi bây giờ là: 2, 1, 1, 4.
• Lần chạy thứ hai, tàu sẽ chở 4 người: [2, 1, 1]. Hàng đợi bây giờ là: 4, 2, 1, 1.
• Lần chạy thứ ba, tàu sẽ chở 6 người: [4, 2]. Hàng đợi bây giờ là: 1, 1, 4, 2.
• Lần chạy cuối cùng, tàu sẽ chở 6 người: [1, 1, 4].
  Tổng cộng tàu lượn đã kiếm được 21 Euro!

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\). Tiếp theo là \(T\) bộ test, mỗi bộ test gồm hai dòng.

• Dòng đầu tiên chứa ba số nguyên cách nhau bởi dấu cách: \(R\), \(k\) và \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(g_i\) cách nhau bởi dấu cách, mỗi số là kích thước của một nhóm muốn đi tàu. \(g_0\) là kích thước của nhóm đầu tiên, \(g_1\) là kích thước của nhóm thứ hai, v.v.

Dữ liệu ra

Với mỗi bộ test, hãy xuất ra một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số Euro mà tàu lượn kiếm được.

Ràng buộc

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

Phân nhóm

• Small dataset (Test set 1):
  • \(1 \le R \le 1000\).
  • \(1 \le k \le 100\).
  • \(1 \le N \le 10\).
  • \(1 \le g_i \le 10\).
• Large dataset (Test set 2):
  • \(1 \le R \le 10^8\).
  • \(1 \le k \le 10^9\).
  • \(1 \le N \le 1000\).
  • \(1 \le g_i \le 10^7\).

Đ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
4 6 4
1 4 2 1
100 10 1
1
5 5 10
2 4 2 3 4 2 1 2 1 3

Case #1: 21
Case #2: 100
Case #3: 20

Nguồn

Google Code Jam 2010, Vòng loại, bài Theme Park.

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