Đề thi Tin học trẻ toàn quốc THCS vòng sơ khảo - Bảng B - Bài 3 - Năm học 2021

 Bài 3. Cân đĩa (100 điểm) 
Cho một cân hai đĩa và 푛 quả cân có khối lượng đôi một khác nhau 푤1, 푤2, . . , 푤푛. Tiến hành đặt lần 
lượt từng quả cân lên một trong hai đĩa của cân và đảm bảo rằng tổng khối lượng bên trái luôn nhỏ 
hơn hoặc bằng tổng khối lượng bên phải. 
Yêu cầu: Cho 푛 quả cân có khối lượng 푤1, 푤2, . . , 푤푛, hãy đếm số cách xếp 푛 quả cân thỏa mãn. 
Hai cách được gọi là khác nhau nếu thứ tự xếp các quả cân khác nhau hoặc tồn tại một quả cân nằm 
ở đĩa khác nhau. 
Dữ liệu: Vào từ thiết bị vào chuẩn có khuôn dạng: 
 - Dòng 1: chứa số nguyên 푛; 
 - Dòng 2: chứa n số nguyên dương 푤1, 푤2, . . , 푤푛. 
Kết quả: Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số cách xếp 푛 quả cân lên đĩa. 
Ví dụ: 
 Dữ liệu vào Kết quả ra Dữ liệu vào Kết quả ra 
 2 3 3 15 
 1 2 10 11 12 
Giải thích: Ở ví dụ bên trái, có 8 cách sắp xếp các quả cân lên hai bàn cân như sau: 
 1. Đặt quả cân 1 bên trái rồi đặt quả cân 2 bên trái; 
 2. Đặt quả cân 1 bên trái rồi đặt quả cân 2 bên phải; 
 3. Đặt quả cân 1 bên phải rồi đặt quả cân 2 bên trái; 
 4. Đặt quả cân 1 bên phải rồi đặt quả cân 2 bên phải; 
 5. Đặt quả cân 2 bên trái rồi đặt quả cân 1 bên trái; 
 6. Đặt quả cân 2 bên trái rồi đặt quả cân 1 bên phải; 
 7. Đặt quả cân 2 bên phải rồi đặt quả cân 1 bên trái; 
 8. Đặt quả cân 2 bên phải rồi đặt quả cân 1 bên phải. 
 Tuy nhiên chỉ có 3 cách (cách 4, 7, 8) là đảm bảo trong toàn bộ quá trình sắp xếp các quả cân, 
đĩa bên trái luôn nhỏ hơn hoặc bằng đĩa cân bên phải. 
Ràng buộc: 
 • Có 40% số test ứng với 40% số điểm của bài có 푛 ≤ 7 và 푤푖 ≤ 1000 (1 ≤ 푖 ≤ 푛); 
 • Có 40% số test khác ứng với 40% số điểm của bài có 푛 ≤ 14 và 푤푖 ≤ 1000 (1 ≤ 푖 ≤ 푛); 
 푖−1
 • Có 20% số test còn lại ứng với 20% số điểm của bài có 푛 ≤ 28 và 푤푖 = 2 (1 ≤ 푖 ≤ 푛). 
 --------------------------- Hết --------------------------- 
 • Thí sinh không được sử dụng tài liệu. 
 • Cán bộ coi thi không giải thích gì thêm. 
 Trang 3/3