Nó ko đơn giản đou nha:D Bài 3. Cân đĩa (100 điểm) Cho một cân hai đĩa và n quả cân có khối lượng đôi một khác nhau w1, w2, . . , wn. 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 n quả cân có khối lượng w1, w2, . . , wn, hãy đếm số cách xếp n 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 n; - Dòng 2: chứa n số nguyên dương w1, w2, . . , wn. 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 n quả cân lên đĩa. Ví dụ: Test 1: 2 1 2 => 3 ///////////////////////////////////////////////// Test 2: 3 10 11 12 => 15 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ó n ≤ 7 và wi ≤ 1000 (1 ≤ i ≤ n); • Có 40% số test khác ứng với 40% số điểm của bài có n ≤ 14 và wi ≤ 1000 (1 ≤ i ≤ n); • Có 20% số test còn lại ứng với 20% số điểm của bài có n ≤ 28 và wi = 2 i−1 (1 ≤ i ≤ n).