Chia phần thưởng

Chia phần thưởng
Vào dịp tổng kết cuối năm học 2000-2001 ,trường PTNK có N học sinh được xếp loại xuất sắc.Để động viện các em học sinh này ,hội phụ huynh học sinh đã quyết định xin N đơn vị tài trợ ,mỗi đơn vị tài trợ một số vở loại tốt để làm phần thưởng cho các em.Rất may các đơn vị đều đáp ứng lờikêu gọi tài trợ một cách sốt sắng.Mỗi đơn vị đã gửi đến nhà trường một gói quà ,có ghi tên ngoài số vở mà mình tặng cho trường.Để tiện việc quản lý ,nhà trường đã quyết định gói quà nào đã mở ra thì sẽ dùng toàn bộ số vở trong đó làm quà tặng cho các học sinh và mỗi học sinh đều phải nhận được phần thưởng như nhau .
Giả sử các đơn vị lần lượt cho X1,X2 ,...Xn quyển vở .Hãy giúp nhà trường chọn ra M gói quà để phát thưởng cho các học sinh hoặc cho biết không thể chia đều được như mong muốn của nhà trường.
1.Hãy chỉ ra cách giải bất kỳ
2.Hãy chỉ ra lời giải với M nhỏ nhất.
DỮ liệu cho trong file văn bản có tên CHIAQUA.INP có nội dung như sau :
- Dòng đầu chứa số N (1<=1000)
- Các dòng tiếp theo chứa N số nguyên dương X1 ,X2 ,...Xn .
- Các số trên cùng một dòng cách nhau bởi khoảng trắng.
Kết quả xuất ra file văn bản có tên CHIAQUA.OUT có nội dung như sau :
- Dòng đầu chứa câu "CO LOI GIAI " hoặc " KHONG CO LOI GIAI "
- Trong trường hợp không có lời giải thì file không chứa gì thêm.
- Nếu có lời giải thì dòng kế tiếp sẽ gồm:
1.Dòng đầu chứa dòng văn bản : " Cau 1: "
2.Dòng tiếp theo chứa số M1 cho biết cần mở gói quà (ứng với câu 1 )
3.Tiếp theo là dòng chứa M1 số cho biết chỉ số của các gói quà cần mở.
4.Tiếp theo là dòng chứa chuỗi kí tự : "Cau 2 : "
5.Dòng tiếp theo chứa số M2 cho biết chỉ số của các gói quà cần mở.
Ví dụ :
CHIAQUA.INP
5
1 3 1 7 3
CHIAQUA.OUT
CAU 1:
5
1 2 3 4 5
CAU 2:
2
2 4

Nhận xét chung: bài này giống bài dãy con chia hết cho k. Trông không có vẻ khó lắm. Tuy nhiên phải suy nghĩ kĩ lại.

bạn học thầy Nguyễn Thanh Hùng đúng ko

có học ai đâu

xin lỗi !
bài này tới nghĩ, áp dụng tư tưởng của "bài dãy con có tổng bằng k cho trước"

lâu lâu nhìn lại mấy cái đề này zui ghê. nhớ thời ngày ngày coding quá

Sao gửi câu hỏi lên trên dc vậy. chỉ với.
Tui có bài này giải hộ cái:
Cho dãy Finbonaci 1,1,2,3,5,8,13,21,....
Biểu diễn số N thành tổng các số hạng thuộc dãy Fibo sao cho các số hạng là nhiều nhất.
VD:
N=9
9=1+8 ;9=1+3+5;
Vậy 9=1+3+5 là cách biểu diễn thỏa yc

dùng dãy con có tổng bằng k cho trước
trong đó theo vi dụ trên
k:=9;
mảng dãy số là các số finbonaci, số lớn nhất trong dãy phải nhỏ hơn k ...
nhưng nếu số k quá lớn thì dùng cách này chạy lâu, vì nó là quy hoạch động với độ phức tạp là O(n*n) trong đó n là sô phần tử của trên