Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Chia phần thưởng

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Chia phần thưởng   Fri 19 Mar 2010, 18:39

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.
Về Đầu Trang Go down
nham00
Gà mờ


Tổng số bài gửi : 7
Join date : 06/09/2010

Bài gửiTiêu đề: Re: Chia phần thưởng   Tue 07 Sep 2010, 20:54

bạn học thầy Nguyễn Thanh Hùng đúng ko
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Chia phần thưởng   Wed 08 Sep 2010, 20:04

có học ai đâu tongue

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
nham00
Gà mờ


Tổng số bài gửi : 7
Join date : 06/09/2010

Bài gửiTiêu đề: Re: Chia phần thưởng   Fri 10 Sep 2010, 00:08

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"
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Chia phần thưởng   Fri 17 Sep 2010, 19:59

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á
Về Đầu Trang Go down
zZzSựPhụcSinhzZz
Gà mờ


Tổng số bài gửi : 4
Join date : 24/09/2010

Bài gửiTiêu đề: Re: Chia phần thưởng   Fri 24 Sep 2010, 10:56

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
Về Đầu Trang Go down
nham00
Gà mờ


Tổng số bài gửi : 7
Join date : 06/09/2010

Bài gửiTiêu đề: Re: Chia phần thưởng   Sat 20 Nov 2010, 19:57

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
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Chia phần thưởng   Today at 21:32

Về Đầu Trang Go down
 
Chia phần thưởng
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Loi chia tay som muon !
» [Entry] Yêu và chia tay
» GIÂY PHÚT CHIA TAY
» Mình Chia Tay Nhau Rồi Mà Em......
» Loi chia tay nhe nhang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến