Google Code Jam 2017 - Round 2

Joy sắp đi nghỉ dài ngày, nên cô thuê kỹ thuật viên lắp một hệ thống an ninh dùng tia laser hồng ngoại. Họ đưa cho cô sơ đồ ngôi nhà dưới dạng lưới ô vuông đơn vị gồm \(R\) hàng và \(C\) cột. Mỗi ô chứa một trong các ký hiệu:

• /: gương hai mặt chạy từ góc dưới trái đến góc trên phải của ô.
• \\: gương hai mặt chạy từ góc trên trái đến góc dưới phải của ô.
• -: máy phát bắn tia theo phương ngang vào ô ngay bên trái và bên phải, nếu có.
• |: máy phát bắn tia theo phương dọc vào ô ngay phía trên và phía dưới, nếu có.
• #: tường. Ngôi nhà không nhất thiết được bao kín bởi một viền tường — đó cũng là một lý do Joy cần hệ thống an ninh!
• .: ô trống.

Tia đi thẳng qua các ô trống. Khi gặp gương, tia phản xạ 90 độ rồi tiếp tục. Một tia đi sang phải gặp gương / sẽ đổi hướng lên; các tia đi lên, sang trái, xuống gặp / lần lượt đổi sang phải, xuống, trái. Gương \\ hoạt động tương tự: tia đi sang phải, lên, trái, xuống lần lượt đổi sang xuống, trái, lên, phải. Tia dừng khi gặp tường hoặc ra ngoài lưới. Các tia có thể cắt nhau; nhưng nếu một tia chạm bất kỳ máy phát nào, kể cả máy đã phát ra nó, máy phát đó sẽ bị phá hủy.

Joy muốn mọi ô trống trong nhà có ít nhất một tia đi qua và không máy phát nào bị phá hủy — phá thiết bị chỉ tổ phí tiền! Các kỹ thuật viên đã lắp xong, nên cô chỉ có thể xoay một số máy phát hiện có 90 độ: có thể đổi - thành | hoặc ngược lại cho bất kỳ số máy nào, kể cả không máy nào.

Hãy tìm một cách đạt mục tiêu của Joy hoặc xác định rằng điều đó là không thể. Không cần cực tiểu hóa số máy phát bị xoay.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(R,C\), số hàng và số cột của lưới. Tiếp theo là \(R\) dòng, mỗi dòng gồm \(C\) ký tự thuộc /, \\, -, |, #, . như mô tả.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là IMPOSSIBLE nếu Joy không thể đạt mục tiêu hoặc POSSIBLE nếu có thể. Nếu khả thi, in tiếp đúng \(R\) dòng gồm \(C\) ký tự của lưới đầu vào, trong đó có thể thay không hoặc nhiều ký tự - bằng | hay ngược lại. Nếu có nhiều đáp án, có thể in bất kỳ đáp án nào.

Ràng buộc

• \(1\le T\le100\).
• \(1\le C\le50\).
• Mỗi ký tự lưới thuộc /, \\, -, |, #, ..
• Tổng số máy phát (- và |) từ 1 đến 100.
• Có ít nhất một ô ..

Phân nhóm

Test Set 1 (Visible): \(1\le R\le5\) và lưới không có gương / hay \\.

Test Set 2 (Hidden): \(1\le R\le50\).

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

5
1 3
-.-
3 4
#.##
#--#
####
2 2
-.
#|
4 3
.|.
-//
.-.
#\/
3 3
/|\
\\/
./#

Case #1: IMPOSSIBLE
Case #2: POSSIBLE
#.##
#||#
####
Case #3: POSSIBLE
|.
#|
Case #4: POSSIBLE
.-.
|//
.|.
#\/
Case #5: IMPOSSIBLE

.-.
|//
.-.
#\/

Nguồn

Google Code Jam 2017, Vòng 2, bài Beaming With Joy.

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

Bạn là quản lý quan hệ công chúng của một hãng sản xuất sô-cô-la. Đáng tiếc, hình ảnh công ty bị tổn hại vì khách hàng cho rằng ông chủ keo kiệt và bủn xỉn. Bạn hy vọng xóa bỏ ấn tượng đó bằng cách tổ chức tham quan nhà máy và nếm sô-cô-la miễn phí.

Ngay sau khi bắt đầu dự án, bạn nhận ra tiếng xấu của ông chủ hoàn toàn có cơ sở: ông chỉ đồng ý tặng sô-cô-la nếu bạn giảm chi phí xuống thấp nhất. Sô-cô-la được đóng thành gói, mỗi gói có \(P\) miếng. Bạn muốn mở gói mới cho từng đoàn tham quan, nhưng ông chủ khăng khăng rằng nếu một đoàn dùng còn thừa, số miếng đó phải được dùng cho đoàn kế tiếp trước khi mở gói mới.

Ví dụ, mỗi gói có \(P=3\) miếng và một đoàn 5 người đến. Bạn mở hai gói để mỗi người nhận một miếng và còn thừa một miếng. Sau đó một đoàn 6 người đến: họ nhận miếng thừa trước, rồi bạn mở thêm hai gói để phát đủ, và lại thừa một miếng. Nếu tiếp theo là hai đoàn 4 người, đoàn đầu nhận miếng thừa cùng một gói nguyên; đoàn 4 người cuối nhận sô-cô-la từ hai gói mới mở. Bạn không được mở gói mới trước khi dùng hết đồ thừa, ngay cả khi định dùng hết gói mới lập tức.

Trong ví dụ đó, 2 trong 4 đoàn — đoàn đầu và đoàn cuối — nhận toàn bộ sô-cô-la từ các gói mới mở. Hai đoàn còn lại nhận cả sô-cô-la mới lẫn đồ thừa. Bạn biết phát đồ thừa không phải cách hay để sửa hình ảnh bủn xỉn của ông chủ, nhưng phải chấp nhận hệ thống này để ông sếp hà tiện đồng ý dự án. Dù hoàn cảnh bất lợi, bạn vẫn quyết tâm làm thật tốt.

Bạn có yêu cầu từ \(N\) đoàn; mỗi đoàn cho biết số người sẽ đến. Các đoàn vào nhà máy lần lượt. Bạn muốn chọn thứ tự sao cho nhiều đoàn nhất chỉ nhận sô-cô-la mới, không nhận đồ thừa. Không được từ chối đoàn nào, không được phát cho một đoàn nhiều hơn một lần và phải phát đúng một miếng cho mỗi người.

Với các đoàn ở ví dụ trên, nếu thứ tự là 4, 5, 6, 4 thay vì 5, 6, 4, 4 thì có 3 đoàn — tất cả trừ đoàn 5 người — chỉ nhận sô-cô-la mới. Không cách sắp nào cho cả bốn đoàn chỉ nhận sô-cô-la mới.

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 \(N\), số đoàn tham quan, và \(P\), số miếng mỗi gói. Dòng thứ hai chứa \(N\) số nguyên \(G_1,G_2,\ldots,G_N\), số người trong từng đoàn.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số đoàn tối đa chỉ nhận sô-cô-la mới khi chọn thứ tự tốt nhất.

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le100\).
• \(1\le G_i\le100\) với mọi \(i\).

Phân nhóm

Test Set 1 (Visible): \(2\le P\le3\).

Test Set 2 (Hidden): \(2\le P\le4\).

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

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

Nguồn

Google Code Jam 2017, Vòng 2, bài Fresh Chocolate.

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

Bạn đã tạo ra một tàu lượn siêu tốc mới sắp khai trương. Đoàn tàu có một hàng gồm \(N\) ghế, đánh số từ 1 đến \(N\) theo thứ tự từ trước ra sau; dĩ nhiên ghế càng gần phía trước càng giá trị. Khách hàng đã mua vé ngày khai trương. Mỗi vé cho phép một khách cụ thể đi một chuyến ở một ghế cụ thể. Một số khách có thể mua nhiều vé và mong được đi một chuyến cho mỗi vé.

Bạn cần quyết định ngày khai trương sẽ chạy bao nhiêu chuyến. Trong mỗi chuyến, mỗi ghế có thể có một khách và một số ghế có thể để trống. Không được xếp một khách vào nhiều hơn một ghế trong cùng chuyến, cũng không được xếp hai khách vào cùng một ghế trong một chuyến.

Bạn muốn giảm chi phí vận hành bằng cách dùng ít chuyến nhất mà vẫn thực hiện mọi vé. Để giảm số chuyến, bạn có thể thăng hạng tùy ý nhiều vé. Thăng hạng là đổi vé của một khách sang một ghế gần đầu tàu hơn, tức ghế có số nhỏ hơn. Bạn muốn thăng hạng ít vé nhất vì quá nhiều lần thăng hạng có thể khiến khách trở nên tham lam và đòi hỏi thêm trong tương lai.

Với vị trí và người mua của mọi vé đã bán, hãy tìm số chuyến nhỏ nhất để thực hiện tất cả vé khi được phép thăng hạng và xếp lịch tối ưu; đồng thời tìm số vé phải thăng hạng ít nhất để đạt số chuyến đó. Chẳng hạn, đổi vé của một khách trong một chuyến từ ghế 4 lên ghế 2 chỉ tính là một lần thăng hạng, không phải hai.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng ba số nguyên: \(N\), số ghế; \(C\), số khách tiềm năng; và \(M\), số vé đã bán. Khách được đánh số từ 1 đến \(C\). Tiếp theo là \(M\) dòng, dòng thứ \(i\) chứa \(P_i\), vị trí ghế ghi trên vé thứ \(i\), và \(B_i\), mã số người mua vé đó.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y z, trong đó x là số thứ tự bộ test (bắt đầu từ 1), y là số chuyến nhỏ nhất để thực hiện mọi vé khi thăng hạng và xếp lịch tối ưu, còn z là số lần thăng hạng nhỏ nhất để thực hiện mọi vé bằng đúng y chuyến.

Ràng buộc

• \(1\le T\le100\).
• \(2\le N\le1000\).
• \(1\le M\le1000\).
• \(1\le P_i\le N\).
• \(1\le B_i\le C\).

Phân nhóm

Test Set 1 (Visible): \(C=2\).

Test Set 2 (Hidden): \(2\le C\le1000\).

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

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

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

Nguồn

Google Code Jam 2017, Vòng 2, bài Roller Coaster Scheduling.

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

Cuộc chiến giải phóng thành phố khỏi những kẻ xâm lược ngoài hành tinh đã kết thúc! Mọi người vui mừng vì tình yêu và hòa bình đã trở lại.

Thành phố được biểu diễn bằng lưới \(R\) hàng, \(C\) cột. Một số ô là tòa nhà — không ai có thể nhìn, bắn hay đi xuyên qua — và một số ô là đường phố — mọi người có thể nhìn, bắn và đi qua. Trong chiến tranh, những kẻ xâm lược nay đã bị đánh bại đặt các tháp pháo an ninh tự động trên đường phố, không phải trong tòa nhà. Các tháp gây nguy hiểm cho dân thường, nhưng may mắn là cũng có một số binh sĩ trên đường phố. Ban đầu không binh sĩ nào đứng cùng ô với tháp.

Tháp pháo không di chuyển. Chúng nhỏ nên không chặn tầm nhìn và đường đạn. Binh sĩ không thể đi xuyên qua ô của một tháp còn hoạt động, nhưng có thể đi qua sau khi tháp bị phá. Tháp chỉ nhìn thấy binh sĩ trong các ô có đường ngắm ngang hoặc dọc. Nếu binh sĩ đi vào một ô như vậy, tháp chưa bắn; nếu cô ấy cố rời khỏi ô đó, dù vừa đi vào hay bắt đầu tại đó, tháp sẽ bắn. May mắn thay, binh sĩ vẫn có thể bắn khi đứng yên trong ô và tháp không coi đó là chuyển động. Vì thế không binh sĩ nào thật sự phải chết: trong trường hợp xấu nhất họ có thể đứng im chờ cứu viện, có lẽ rất lâu.

Mỗi binh sĩ có thể thực hiện tổng cộng \(M\) bước đơn vị; mỗi bước sang một ô kề ngang hoặc dọc. Binh sĩ có thể đi xuyên qua nhau và không chặn tầm nhìn của binh sĩ hay tháp. Mỗi binh sĩ có một viên đạn. Nếu có một tháp trong đường ngắm ngang hoặc dọc, cô ấy có thể bắn phá nó. Mỗi phát chỉ phá một tháp, nhưng các binh sĩ bắn giỏi đến mức có thể bắn xuyên qua một hoặc nhiều tháp hay binh sĩ trên cùng đường ngắm để trúng một tháp xa hơn.

Bạn được cho bản đồ có đánh dấu vị trí binh sĩ và tháp. Số tháp lớn nhất họ có thể phá là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng ba số nguyên \(C\) (chiều rộng bản đồ), \(R\) (chiều cao) và \(M\) (số bước đơn vị mỗi binh sĩ có thể đi). Tiếp theo là \(R\) dòng, mỗi dòng \(C\) ký tự: . là đường phố, # là tòa nhà, S là binh sĩ và T là tháp pháo.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số tháp lớn nhất có thể phá. Sau đó in \(y\) dòng; dòng thứ \(i\) chứa hai số nguyên \(s_i,t_i\), biểu thị hành động thứ \(i\) là binh sĩ \(s_i\) phá tháp \(t_i\). Không cần chỉ rõ đường đi. Nếu có nhiều chiến lược hợp lệ, có thể in bất kỳ chiến lược nào.

Binh sĩ được đánh số từ 1 theo thứ tự đọc: trái sang phải trên hàng đầu, rồi trái sang phải trên hàng kế tiếp, từ trên xuống dưới. Tháp có hệ đánh số độc lập, cũng bắt đầu từ 1 và theo cùng thứ tự.

Ràng buộc

• \(1\le T\le100\).
• \(0\le M<C\times R\).

Phân nhóm

Test Set 1 (Visible): \(1\le C,R\le30\); số ký hiệu S từ 1 đến 10 và số ký hiệu T từ 1 đến 10.

Test Set 2 (Hidden): \(1\le C,R\le100\); số ký hiệu S từ 1 đến 100 và số ký hiệu T từ 1 đến 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.

Ví dụ

4
2 2 1
#S
T.
2 6 4
.T
.T
.T
S#
S#
S#
5 5 4
.....
SS#.T
SS#TT
SS#.T
.....
3 3 8
S.#
.#.
#.T

Case #1: 1
1 1
Case #2: 3
3 3
1 1
2 2
Case #3: 3
1 2
2 1
6 3
Case #4: 0

Nguồn

Google Code Jam 2017, Vòng 2, bài Shoot the Turrets.

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