Google Code Jam 2015 - Round 1A

Bạn đang chờ trong một hàng dài để cắt tóc tại một tiệm tóc thời thượng. Tiệm có \(B\) thợ đang làm việc, được đánh số từ 1 đến \(B\). Thợ thứ \(k\) luôn mất đúng \(M_k\) phút để cắt tóc cho một khách và mỗi thợ chỉ có thể cắt tóc cho một khách tại một thời điểm. Ngay khi cắt xong, thợ lập tức rảnh để phục vụ khách khác.

Trong thời gian tiệm mở cửa, người đứng đầu hàng luôn đến thợ đang rảnh có số nhỏ nhất. Khi không có thợ nào rảnh, người đó chờ cho đến khi ít nhất một thợ rảnh.

Bạn là người thứ \(N\) trong hàng và tiệm vừa mở cửa. Thợ nào sẽ cắt tóc cho bạn?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên cách nhau bởi dấu cách \(B\) và \(N\) — số thợ và vị trí của bạn trong hàng. Người đứng đầu hàng mang số 1, người kế tiếp mang số 2, v.v. Dòng thứ hai chứa \(M_1, M_2, \ldots, M_B\).

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số của thợ sẽ cắt tóc cho bạn.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le N \le 10^9\).

Phân nhóm

• Nhỏ: \(1 \le B \le 5\); \(1 \le M_k \le 25\).
• Lớn: \(1 \le B \le 1000\); \(1 \le M_k \le 100000\).

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

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

Nguồn

Google Code Jam 2015, Vòng 1A, bài Haircut.

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 khu rừng có \(N\) cây, mỗi cây là nơi ở của một chú sóc.

Biên của khu rừng là đa giác lồi có diện tích nhỏ nhất chứa mọi cây, giống như một sợi dây cao su khổng lồ được căng quanh phía ngoài khu rừng.

Nói chính xác, mỗi cây là một điểm trong không gian hai chiều, có tọa độ \((X_i,Y_i)\) riêng biệt, và biên là bao lồi của các điểm đó.

Một số cây nằm trên biên khu rừng, nghĩa là chúng nằm trên một cạnh hoặc một đỉnh của đa giác. Các chú sóc muốn biết cây của mình gần với việc nằm trên biên đến mức nào.

Lần lượt từng chú sóc trèo xuống khỏi cây, quan sát khu rừng và xác định số cây ít nhất cần bị chặt để cây của chính nó nằm trên biên. Sau đó, nó ghi con số ấy lên một khúc gỗ.

Hãy xác định danh sách các số được ghi trên khúc gỗ.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa số nguyên \(N\), là số cây, tiếp theo là \(N\) dòng, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(X_i\) và \(Y_i\), là tọa độ của một cây. Không có hai cây nào có cùng tọa độ.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x:, sau đó là \(N\) dòng, mỗi dòng chứa một số nguyên; dòng thứ \(i\) là số cây mà chú sóc sống trên cây \(i\) cần chặt.

Ràng buộc

• \(-10^6 \le X_i,Y_i \le 10^6\).

Phân nhóm

• Nhỏ: \(1 \le T \le 100\); \(1 \le N \le 15\).
• Lớn: \(1 \le T \le 14\); \(1 \le N \le 3000\).

Đ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
5
0 0
10 0
10 10
0 10
5 5
9
0 0
5 0
10 0
0 5
5 5
10 5
0 10
5 10
10 10

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

Nguồn

Google Code Jam 2015, Vòng 1A, bài Logging.

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

Kaylin rất thích nấm. Chỉ cần đặt chúng lên đĩa là cô ấy sẽ ăn hết! Trong bài này, cô ấy đang ăn nấm trên một chiếc đĩa, còn Bartholomew thì đặt thêm các miếng nấm lên đĩa.

Ta quan sát số miếng nấm trên đĩa ở các thời điểm cách nhau 10 giây. Bartholomew có thể đặt thêm một số nguyên không âm miếng nấm vào bất kỳ lúc nào; cách duy nhất để nấm rời khỏi đĩa là bị ăn.

Hãy tính số nấm ít nhất mà Kaylin có thể đã ăn theo hai phương pháp tính khác nhau:

1. Giả sử Kaylin có thể ăn bất kỳ số miếng nấm nào vào bất kỳ lúc nào.
2. Giả sử rằng, kể từ lần đầu tiên ta nhìn vào đĩa, Kaylin ăn nấm với tốc độ không đổi bất cứ khi nào trên đĩa còn nấm.

Ví dụ, nếu dữ liệu là 10 5 15 5:

Theo phương pháp thứ nhất, Kaylin phải ăn ít nhất 15 miếng nấm: đầu tiên cô ăn 5 miếng, sau đó 10 miếng nữa được đặt lên đĩa, rồi cô ăn thêm 10 miếng. Không có cách nào để cô ăn ít hơn.

Theo phương pháp thứ hai, Kaylin phải ăn ít nhất 25 miếng. Ta xác định được rằng tốc độ ăn phải ít nhất là 1 miếng mỗi giây. Ban đầu cô có 10 miếng trên đĩa. Trong 10 giây đầu, cô ăn 10 miếng và 5 miếng nữa được đặt lên đĩa. Trong 5 giây tiếp theo, cô ăn 5 miếng; đĩa rỗng trong 5 giây còn lại, rồi Bartholomew đặt thêm 15 miếng. Cuối cùng, cô ăn 10 miếng trong 10 giây cuối.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa số nguyên \(N\), tiếp theo là một dòng chứa \(N\) số nguyên \(m_i\) cách nhau bởi dấu cách: số nấm trên đĩa của Kaylin lúc bắt đầu và tại các thời điểm cách nhau 10 giây.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y z, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), \(y\) là số nấm ít nhất Kaylin có thể đã ăn theo phương pháp thứ nhất và \(z\) là số nấm ít nhất theo phương pháp thứ hai.

Ràng buộc

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

Phân nhóm

• Nhỏ: \(2 \le N \le 10\); \(0 \le m_i \le 100\).
• Lớn: \(2 \le N \le 1000\); \(0 \le m_i \le 10000\).

Đ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
4
10 5 15 5
2
100 100
8
81 81 81 81 81 81 81 0
6
23 90 40 0 100 9

Case #1: 15 25
Case #2: 0 0
Case #3: 81 567
Case #4: 181 244

Nguồn

Google Code Jam 2015, Vòng 1A, bài Mushroom Monster.

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