Chia sô-cô-la
Đề bài
Mô tả
Sô-cô-la dưới nhiều dạng khác nhau được hàng triệu người trên thế giới thưởng thức mỗi ngày. Đây thật sự là một loại kẹo phổ biến toàn cầu, có mặt ở hầu như mọi quốc gia.
Bạn nhận ra rằng điều duy nhất còn tuyệt hơn ăn sô-cô-la là chia sẻ nó với bạn bè. Không may, bạn bè của bạn rất kén chọn và có khẩu vị khác nhau: có người muốn nhiều hơn, có người muốn ít hơn phần sô-cô-la bạn mời. Việc xác định xem có đáp ứng được mọi yêu cầu của họ hay không ngày càng khó. Đã đến lúc viết một chương trình giải quyết bài toán này một lần cho mãi mãi!
Sô-cô-la của bạn có dạng một thanh hình chữ nhật, gồm các miếng hình chữ nhật cùng kích thước. Để chia sô-cô-la, bạn có thể bẻ một thanh thành hai phần dọc theo một đường phân cách giữa hai hàng hoặc giữa hai cột của thanh. Sau đó bạn có thể tiếp tục bẻ các phần thu được theo cùng cách đó. Mỗi người bạn đều đòi nhận đúng một phần sô-cô-la hình chữ nhật chứa đúng số miếng mà người đó yêu cầu. Bạn cũng có yêu cầu riêng: bạn chỉ bẻ thanh sô-cô-la nếu toàn bộ thanh được chia hết cho bạn bè, không thừa miếng nào.
Ví dụ, hình dưới đây cho thấy một cách chia thanh sô-cô-la gồm miếng thành phần chứa lần lượt , , và miếng bằng lần bẻ (ứng với bộ test đầu tiên của ví dụ 1). Mỗi ô ghi số miếng của phần chứa nó.
grid 6 6 6 3 6 6 6 3 2 2 1 3 highlight orange 1,1..2,3 highlight green 1,4..3,4 highlight purple 3,1..3,2 highlight teal 3,3
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test, mỗi bộ mô tả một thanh sô-cô-la cần chia. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên () là số phần cần chia. Dòng tiếp theo chứa hai số nguyên và () là kích thước của thanh sô-cô-la. Dòng tiếp theo chứa số nguyên dương là số miếng của từng phần trong phần.
Dữ liệu vào kết thúc bằng một dòng chứa số .
Dữ liệu ra
Với mỗi bộ test, in ra số thứ tự của bộ test, sau đó cho biết có thể bẻ thanh sô-cô-la theo đúng yêu cầu hay không: in Yes nếu có thể, ngược lại in No. Làm theo đúng định dạng trong ví dụ.
Ràng buộc
- , , .
- Trong một file dữ liệu vào, tổng của mọi bộ test không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 4 6 3 2 1 2 2 3 1 5 0 |
Case 1: Yes Case 2: No |
Bộ 1: cách chia như hình trên. Bộ 2: phần miếng phải là hình chữ nhật , không nằm vừa trong thanh . |
| 3 2 2 2 1 1 2 2 2 3 1 3 3 3 4 4 1 5 4 4 4 4 4 2 2 0 |
Case 1: Yes Case 2: No Case 3: No Case 4: Yes |
Bộ 1: bẻ thanh thành hai thanh , bẻ tiếp một thanh thành hai miếng. Bộ 2: phần miếng không thể là hình chữ nhật nằm trong thanh . Bộ 3: tổng số miếng bằng và mỗi phần đều có thể là hình chữ nhật (, , ), nhưng lần bẻ đầu tiên luôn tách thanh thành hai phần có và miếng, mà không có nhóm phần nào có tổng . Bộ 4: bẻ thành bốn thanh , bẻ đôi thanh cuối cùng. |
Bình luận