Google Code Jam 2017 - Round 1A

Bạn đang chuẩn bị tiệc cho một nhóm trẻ em và phục vụ một chiếc bánh có dạng lưới gồm \(R\) hàng và \(C\) cột. Trợ lý đã bắt đầu trang trí bằng cách viết chữ cái đầu tên của mỗi đứa trẻ bằng kem lên đúng một ô bánh. Mỗi ô chứa nhiều nhất một chữ cái; vì không có hai đứa trẻ nào có cùng chữ cái đầu, không chữ cái nào xuất hiện quá một lần trên bánh.

Mỗi đứa trẻ muốn nhận một miếng bánh hình chữ nhật duy nhất, có các cạnh theo đường lưới, chứa chữ cái đầu của mình và không chứa chữ cái đầu của bất kỳ đứa trẻ nào khác. Bạn có thể gán mọi ô trống của chiếc bánh cho một đứa trẻ sao cho đạt yêu cầu đó không? Đề bảo đảm luôn có thể làm được. Không cần chia bánh đều; thậm chí một hoặc nhiều em có thể chỉ nhận miếng \(1\times1\) — đây sẽ là một bài học cuộc sống quý giá về sự bất công.

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(R\) và \(C\). Sau đó là \(R\) dòng, mỗi dòng gồm \(C\) ký tự mô tả chiếc bánh. Mỗi ký tự hoặc là một chữ cái tiếng Anh viết hoa (trợ lý đã viết chữ đó vào ô), hoặc là ? (ô còn trống).

Dữ liệu ra

Với mỗi bộ test, trước tiên in một dòng chỉ chứa Case #x:, trong đó x là số thứ tự bộ test (bắt đầu từ 1). Sau đó in thêm \(R\) dòng, mỗi dòng \(C\) ký tự.

Lưới đầu ra phải giống hệt lưới đầu vào, ngoại trừ mọi dấu ? được thay bằng một chữ cái tiếng Anh viết hoa, biểu thị ô đó thuộc miếng bánh của đứa trẻ có chữ cái đầu tương ứng. Không được thêm chữ cái nào vốn không xuất hiện trong đầu vào. Với mỗi chữ cái, miền gồm tất cả các ô mang chữ đó phải là một hình chữ nhật duy nhất có cạnh theo đường 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 \le 100\).
• Lưới đầu vào có ít nhất một chữ cái.
• Không chữ cái nào xuất hiện trong nhiều hơn một ô của lưới đầu vào.
• Mỗi bộ test được bảo đảm có ít nhất một đáp án.

Phân nhóm

• Test Set 1 (Visible): \(1 \le R \le 12\), \(1 \le C \le 12\), \(R\times C\le12\).
• Test Set 2 (Hidden): \(1 \le R \le 25\), \(1 \le C \le 25\).

Đ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 3
G??
?C?
??J
3 4
CODE
????
?JAM
2 2
CA
KE

Case #1:
GGJ
CCJ
CCJ
Case #2:
CODE
COAE
JJAM
Case #3:
CA
KE

Nguồn

Google Code Jam 2017, Vòng 1A, bài Alphabet Cake.

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à một chú rồng thân thiện đang chiến đấu để bảo vệ hang ổ khỏi một hiệp sĩ tham lam! Bạn có \(H_d\) điểm máu và sức tấn công \(A_d\); hiệp sĩ có \(H_k\) điểm máu và sức tấn công \(A_k\). Nếu tại bất kỳ lúc nào máu của bạn giảm xuống 0 hoặc thấp hơn, bạn bị hạ gục và thua ngay lập tức. Nếu máu của hiệp sĩ giảm xuống 0 hoặc thấp hơn, hắn bị hạ gục và bạn thắng!

Trận đấu diễn ra theo nhiều lượt. Trong mỗi lượt, bạn hành động trước và chọn thực hiện đúng một trong các hành động sau:

• Attack: giảm máu đối thủ một lượng bằng sức tấn công hiện tại của bạn.
• Buff: tăng sức tấn công của bạn thêm \(B\) trong toàn bộ phần còn lại của trận đấu.
• Cure: đưa máu của bạn trở lại \(H_d\).
• Debuff: giảm sức tấn công của đối thủ đi \(D\) trong toàn bộ phần còn lại của trận đấu. Nếu Debuff làm sức tấn công của đối thủ xuống dưới 0 thì đặt nó bằng 0.

Sau hành động của bạn, nếu hiệp sĩ vẫn còn nhiều hơn 0 máu, hắn sẽ thực hiện hành động Attack. Sau đó lượt kết thúc. Lưu ý rằng lượt bạn hạ hiệp sĩ vẫn được tính là một lượt, dù hắn không còn được hành động.

Các Buff cộng dồn: mỗi Buff tăng thêm \(B\) sức tấn công. Tương tự, các Debuff cũng cộng dồn.

Bạn muốn hạ hiệp sĩ nhanh nhất có thể (nếu có thể), để không đến muộn buổi nướng kẹo dẻo cùng dân làng trong lễ hội tối nay. Hãy xác định số lượt ít nhất để hạ hiệp sĩ, hoặc kết luận IMPOSSIBLE.

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test gồm một dòng chứa sáu số nguyên \(H_d,A_d,H_k,A_k,B,D\) với ý nghĩa như 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à IMPOSSIBLE nếu không thể hạ hiệp sĩ, hoặc là số lượt ít nhất cần thiết.

Ràng buộc

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

Phân nhóm

• Test Set 1 (Visible): \(1\le H_d,A_d,H_k,A_k\le100\); \(0\le B,D\le100\).
• Test Set 2 (Hidden): \(1\le H_d,A_d,H_k,A_k\le10^9\); \(0\le B,D\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ụ

4
11 5 16 5 0 0
3 1 3 2 2 0
3 1 3 2 1 0
2 1 5 1 1 1

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

Nguồn

Google Code Jam 2017, Vòng 1A, bài Play the Dragon.

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 đã khám phá ra công thức ratatouille tối thượng, món ăn nổi tiếng của Pháp! Bạn biết cần những nguyên liệu nào và cần bao nhiêu gam mỗi nguyên liệu để làm một phần ratatouille. Nhưng bạn tin rằng ai cũng có thể nấu ăn, nên muốn chia sẻ công thức với cả thế giới... đồng thời kiếm thêm chút tiền!

Bạn đã đặt mua các gói nguyên liệu dễ vận chuyển. Mỗi gói chứa một lượng của đúng một nguyên liệu; các gói có thể có khối lượng khác nhau ngay cả khi chứa cùng nguyên liệu. Để tiện lợi, bạn đặt cùng một số lượng gói cho mỗi nguyên liệu.

Bạn muốn dùng các gói đó để tạo càng nhiều bộ kit ratatouille gửi khách hàng càng tốt. Một kit gồm đúng một gói của mỗi nguyên liệu và một nhãn ghi số nguyên phần ratatouille mà kit làm được. Vì không muốn bán thiếu cho khách hay lãng phí thức ăn, mỗi gói phải chứa từ 90% đến 110% (kể cả hai đầu) lượng nguyên liệu thật sự cần để làm số phần ghi trên nhãn.

Ví dụ, giả sử một phần ratatouille cần 500 g cà chua và 300 g hành. Bạn có một gói 900 g cà chua và một gói 660 g hành. Có thể ghép chúng thành kit làm hai phần. Hai phần cần 1000 g cà chua và 600 g hành; 900 g nằm trong khoảng \([90,110]\%\) của 1000 g, còn 660 g nằm trong khoảng \([90,110]\%\) của 600 g. Tuy nhiên, không thể ghi kit làm một hoặc ba phần, cũng không thể ghi 1.999 phần vì số phần phải là số nguyên.

Một số tập gói không bao giờ tạo được kit. Vẫn với công thức trên, nếu có gói 1500 g cà chua và 809 g hành thì không có số phần nào phù hợp. Ba phần cần 1500 g cà chua và 900 g hành, nhưng 809 g hành không nằm trong khoảng \([90,110]\%\); không số nguyên phần nào khác phù hợp.

Bạn muốn chia sẻ công thức với nhiều khách nhất nên cần tạo số kit hợp lệ lớn nhất. Mỗi gói chỉ được dùng trong nhiều nhất một kit. Lưu ý rằng bạn không cần tối đa hóa tổng số phần ratatouille được tạo. Hỏi có thể tạo nhiều nhất bao nhiêu kit?

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test gồm:

• Một dòng chứa hai số nguyên \(N\), số nguyên liệu, và \(P\), số gói của mỗi nguyên liệu.
• Một dòng chứa \(N\) số nguyên \(R_i\); số thứ \(i\) là số gam nguyên liệu thứ \(i\) cần cho một phần ratatouille.
• Tiếp theo là \(N\) dòng, mỗi dòng \(P\) số nguyên. Giá trị thứ \(j\) trên dòng thứ \(i\), \(Q_{ij}\), là số gam trong gói thứ \(j\) của nguyên liệu thứ \(i\).

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à số kit lớn nhất có thể tạo.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le R_i \le 10^6\) với mọi \(i\).
• \(1 \le Q_{ij} \le 10^6\) với mọi \(i,j\).

Phân nhóm

• Test Set 1 (Visible): \(1\le N\le2\), \(1\le P\le8\).
• Test Set 2 (Hidden): \(1\le N\le50\), \(1\le P\le50\), \(N\times P\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ụ

6
2 1
500 300
900
660
2 1
500 300
1500
809
2 2
50 100
450 449
1100 1101
2 1
500 300
300
500
1 8
10
11 13 17 11 16 14 12 18
3 3
70 80 90
1260 1500 700
800 1440 1600
1700 1620 900

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

Nguồn

Google Code Jam 2017, Vòng 1A, bài Ratatouille.

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