Google Code Jam 2018 - Round 1A

Ngày nay, robot có thể lái ô tô, nhưng liệu chúng có thể tổ chức một bữa tiệc ra trò không? Nghiên cứu của đội Code Jam về chủ đề này vẫn đang ở giai đoạn đầu. Chúng tôi vừa triển khai \(R\) robot mua hàng đến siêu thị địa phương để mua đồ dùng cho Vòng Chung kết Thế giới tại Toronto, nhưng mô hình bậc nhất của chúng về một bữa tiệc kiểu Canada rất đơn giản: chúng chỉ mua \(B\) “bit” (mỗi bit là một món ăn nhỏ giống bánh vòng có ở vùng này). Chúng tôi sẽ cải thiện trí tuệ nhân tạo của chúng sau; còn bây giờ, chúng tôi muốn giúp chúng mua đủ số bit đó nhanh nhất có thể.

Siêu thị có \(C\) thu ngân có thể quét hàng của khách. Thu ngân thứ \(i\) sẽ:

• nhận tối đa \(M_i\) món hàng từ mỗi khách;
• mất \(S_i\) giây để quét mỗi món;
• mất thêm \(P_i\) giây để xử lý thanh toán và đóng gói các bit.

Nói cách khác, một khách mang \(N\) bit đến thu ngân thứ \(i\) (với \(N\le M_i\)) sẽ tương tác với thu ngân đó tổng cộng \(S_i\times N+P_i\) giây.

Trước khi các robot tương tác với bất kỳ thu ngân nào, bạn có thể phân phối các bit cho robot theo cách tùy ý. (Các bit phải được giữ nguyên; bạn không thể bẻ chúng thành những phần lẻ!) Robot nào không nhận bit sẽ không được tương tác với thu ngân và sẽ thất vọng bỏ đi.

Sau đó, với mỗi robot có ít nhất một bit, bạn chọn cho nó đúng một thu ngân khác nhau. (Hai robot không thể dùng chung một thu ngân, và một robot không thể dùng nhiều hơn một thu ngân.) Tất cả robot bắt đầu tương tác với thu ngân của mình tại thời điểm 0. Lưu ý rằng sau khi một robot tương tác xong với thu ngân, nó không thể được giao thêm bit và cũng không thể tương tác với thu ngân khác.

Nếu bạn giúp các robot đưa ra lựa chọn tối ưu, thời điểm sớm nhất mà tất cả robot có thể hoàn tất tương tác với các thu ngân là khi nào?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng gồm ba số nguyên \(R\), \(B\) và \(C\): lần lượt là số robot mua hàng, số bit và số thu ngân. Sau đó có thêm \(C\) dòng. Dòng thứ \(i\) trong số này mô tả thu ngân thứ \(i\) và chứa ba số nguyên \(M_i\), \(S_i\), \(P_i\): số bit tối đa, thời gian quét mỗi bit (tính bằng giây), và thời gian thanh toán/đóng gói (tính bằng giây) của thu ngân đó như đã mô tả ở trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là thời điểm sớm nhất (tính bằng giây) mà tất cả robot có thể hoàn tất tương tác với các thu ngân.

Ràng buộc

• \(1\le T\le100\).
• \(1\le M_i\le10^9\) với mọi \(i\).
• \(1\le S_i\le10^9\) với mọi \(i\).
• \(1\le P_i\le10^9\) với mọi \(i\).
• Tổng của \(R\) giá trị \(M_i\) lớn nhất không nhỏ hơn \(B\). (Tồn tại ít nhất một tập con gồm \(R\) thu ngân có thể xử lý toàn bộ số bit.)

Phân nhóm

Test Set 1 (Hiển thị):

• \(1\le R\le C\le5\).
• \(1\le B\le20\).

Test Set 2 (Ẩn):

• \(1\le R\le C\le1000\).
• \(1\le B\le10^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.

Ví dụ

3
2 2 2
1 2 3
1 1 2
2 2 2
1 2 3
2 1 2
3 4 5
2 3 3
2 1 5
2 4 2
2 2 4
2 5 1

Case #1: 5
Case #2: 4
Case #3: 7

Nguồn

Google Code Jam 2018, Vòng 1A, bài Bit Party.

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

Thợ làm bánh Maillard đã cán một ít bột bánh quy rồi cắt thành \(N\) chiếc bánh quy, mỗi chiếc là một hình chữ nhật. Ngay trước khi cho chúng vào lò, ông nhớ ra rằng phần rìa giòn và được caramen hóa của bánh quy đặc biệt thơm ngon. Cụ thể, ông cho rằng mình sẽ hài lòng nhất nếu tổng chu vi của tất cả bánh quy gần \(P\) milimét (mm) nhất có thể nhưng không vượt quá \(P\). (Nếu mẻ bánh có quá nhiều rìa, nó có thể bị cháy!)

Với mỗi chiếc bánh, ông Maillard có thể quyết định giữ nguyên nó, hoặc thực hiện một đường cắt thẳng duy nhất để chia nó thành hai nửa (không nhất thiết là hình chữ nhật) có diện tích bằng nhau. (Lưu ý rằng một đường cắt như vậy nhất thiết phải đi qua tâm chiếc bánh.) Hai chiếc bánh mới được tạo ra theo cách này không thể tiếp tục bị cắt.

Nếu ông Maillard đưa ra các quyết định tối ưu, ông có thể tiến gần đến \(P\) nhất là bao nhiêu mà không vượt quá nó?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng gồm hai số nguyên \(N\) và \(P\): lần lượt là số bánh quy và tổng chu vi mong muốn (tính bằng mm). Sau đó là \(N\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(W_i\) và \(H_i\): chiều rộng và chiều cao (đều tính bằng mm) của chiếc bánh thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là một số thực: tổng chu vi lớn nhất có thể (tính bằng mm) của tất cả bánh quy sau khi ông Maillard cắt xong mà không vượt quá \(P\). Giá trị y được coi là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không quá \(10^{-6}\). Xem FAQ của Code Jam để biết ý nghĩa của điều này và các định dạng số thực được chấp nhận.

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le100\).
• \(1\le W_i\le250\) với mọi \(i\).
• \(1\le H_i\le250\) với mọi \(i\).
• \(P\ge 2\times\sum_i(W_i+H_i)\). (\(P\) ít nhất bằng tổng chu vi của tất cả bánh trước khi thực hiện bất kỳ đường cắt nào.)
• \(P\le10^8\).

Phân nhóm

Test Set 1 (Hiển thị):

• \(W_i=W_j\) với mọi \(i,j\).
• \(H_i=H_j\) với mọi \(i,j\).
• Tất cả bánh quy được cung cấp đều có cùng kích thước.

Test Set 2 (Ẩn): Không có ràng buộc bổ sung ngoài các ràng buộc chung. (Đặc biệt, các bánh quy được cung cấp không nhất thiết đều có cùng kích thước.)

Đ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 7
1 1
2 920
50 120
50 120
1 32
7 4
3 240
10 20
20 30
30 10

Case #1: 6.828427
Case #2: 920.000000
Case #3: 32.000000
Case #4: 240.000000

Nguồn

Google Code Jam 2018, Vòng 1A, bài Edgy Baking.

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

Các thực khách tại Ngôi nhà Bánh kếp Vô hạn đã chán bánh kếp hình tròn, nên các đầu bếp sắp đưa ra một lựa chọn mới trong thực đơn: bánh waffle! Để quảng bá, họ đã làm một chiếc waffle lớn có dạng lưới ô vuông gồm \(R\) hàng và \(C\) cột. Mỗi ô của chiếc waffle hoặc trống, hoặc chứa đúng một hạt sô-cô-la.

Giờ là lúc các đầu bếp chia chiếc waffle cho những thực khách đang đói. Một đường cắt ngang chạy dọc toàn bộ đường lưới nằm giữa hai hàng; một đường cắt dọc chạy dọc toàn bộ đường lưới nằm giữa hai cột. Để làm việc hiệu quả, một đầu bếp sẽ thực hiện đúng \(H\) đường cắt ngang khác nhau và một đầu bếp khác sẽ thực hiện đúng \(V\) đường cắt dọc khác nhau. Nhờ đó, họ tạo ra đúng một miếng cho mỗi người trong số \((H+1)\times(V+1)\) thực khách. Các miếng không nhất thiết có cùng kích thước, nhưng điều đó không sao; nghiên cứu thị trường cho thấy thực khách không quan tâm đến chuyện này.

Điều thực khách quan tâm là số hạt sô-cô-la họ nhận được, vì vậy mỗi miếng phải có chính xác cùng một số hạt sô-cô-la. Bạn có thể xác định liệu các đầu bếp có đạt được mục tiêu này với số đường cắt ngang và dọc đã cho hay không?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\); tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa bốn số nguyên \(R\), \(C\), \(H\), \(V\): số hàng và số cột của chiếc waffle, cùng số đường cắt ngang và dọc chính xác mà các đầu bếp phải thực hiện. Sau đó có thêm \(R\) dòng, mỗi dòng gồm \(C\) ký tự; ký tự thứ \(j\) trên dòng thứ \(i\) biểu diễn ô ở hàng \(i\), cột \(j\) của chiếc waffle. Mỗi ký tự là @, nghĩa là ô đó có một hạt sô-cô-la, hoặc ., nghĩa là ô đó trống.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là POSSIBLE nếu các đầu bếp có thể đạt mục tiêu như mô tả ở trên, hoặc IMPOSSIBLE nếu không thể.

Ràng buộc

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

Phân nhóm

Test Set 1 (Hiển thị):

• \(2\le R\le10\).
• \(2\le C\le10\).
• \(H=1\).
• \(V=1\).

Test Set 2 (Ẩn):

• \(2\le R\le100\).
• \(2\le C\le100\).
• \(1\le H<R\).
• \(1\le V<C\).

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

6
3 6 1 1
.@@..@
.....@
@.@.@@
4 3 1 1
@@@
@.@
@.@
@@@
4 5 1 1
.....
.....
.....
.....
4 4 1 1
..@@
..@@
@@..
@@..
3 4 2 2
@.@@
@@.@
@.@@
3 4 1 2
.@.@
@.@.
.@.@

Case #1: POSSIBLE
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
Case #4: IMPOSSIBLE
Case #5: POSSIBLE
Case #6: IMPOSSIBLE

.@@. .@
.... .@

@.@. @@

Nguồn

Google Code Jam 2018, Vòng 1A, bài Waffle Choppers.

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