trang chủ / đề bài / icpcwf10_j

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 3×4 miếng thành 4 phần chứa lần lượt 6, 3, 2 và 1 miếng bằng 3 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 n (1≤n≤15) là số phần cần chia. Dòng tiếp theo chứa hai số nguyên x và y (1≤x,y≤100) là kích thước của thanh sô-cô-la. Dòng tiếp theo chứa n số nguyên dương a1,a2,…,an là số miếng của từng phần trong n phần.

Dữ liệu vào kết thúc bằng một dòng chứa số 0.

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

  • 1≤n≤15, 1≤x,y≤100, 1≤ai≤104.
  • Trong một file dữ liệu vào, tổng 2n của mọi bộ test không vượt quá 216.

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 5 miếng phải là hình chữ nhật 1×5, không nằm vừa trong thanh 2×3.
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 2×2 thành hai thanh 1×2, bẻ tiếp một thanh thành hai miếng. Bộ 2: phần 3 miếng không thể là hình chữ nhật nằm trong thanh 2×2. Bộ 3: tổng số miếng bằng 9 và mỗi phần đều có thể là hình chữ nhật (2×2, 2×2, 1×1), nhưng lần bẻ đầu tiên luôn tách thanh 3×3 thành hai phần có 3 và 6 miếng, mà không có nhóm phần nào có tổng 3. Bộ 4: bẻ thành bốn thanh 1×4, bẻ đôi thanh cuối cùng.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0