Tài liệu Dethi_chonqd_2014_v2

TỈNH ĐỒNG THÁP ĐỀ THI CHỌN HỌC SINH GIỎI QUỐC GIAI NĂM 2013-2014 VÒNG 2 Bài Bài 4. Gói bánh ngày Tết Tên tệp chương trình B4.* Tên tệp input Tên tệp output GOIBANH.INP GOIBANH.OUT Bài 5. Chia nhóm văn nghệ B5.* CHIANHOM.INP CHIANHOM.OUT Bài 6. Bùa may mắn BUAMAYMAN.INP BUAMAYBAN.OUT B6.* Ghi chú. Tất cả chương trình đều có giới hạn thời gian là 1 giây. Câu 4. (7 điểm) GÓI BÁNH NGÀY TẾT Để chuẩn bị cho dịp tết nguyên đán, chủ một cửa hàng bánh đã lên kế hoạch gói các loại bánh tét với cùng một thứ nếp nhưng nhân bánh thì khác nhau. Mỗi loại nhân bánh khác nhau sẽ cho ra các loại bánh khác nhau. Ông ta còn tổng cộng n kilogram nếp và m loại nhân bánh được đánh số từ 1 đến m. Với mỗi 1≤i≤m, nhân thứ i hiện tại còn lại a[i] kilogram và mỗi cái bánh gói loại nhân này sẽ cần b[i] kilogram nhân cùng c[i] kilogram nếp, bán ra với giá d[i] nghìn đồng. Ngoài ra, ông ta cũng có thể gói một số bánh chay không có nhân, mỗi cái cần c[0] kilogram nếp và bán ra với giá d[0] nghìn đồng. Các nguyên liệu dư thừa (nếp và các loại nhân bánh) sau khi gói số bánh sẽ không cần quan tâm. Các khối lượng tính toán đều là số nguyên. Yêu cầu: Giả sử với số bánh tét gói được, ông chủ cửa hàng luôn có thể bán hết. Hãy tìm số tiền lớn nhất mà ông ấy có thể nhận được từ việc gói bánh tét vào dịp Tết này. Dữ liệu vào: Trong file GOIBANH.INP, dòng đầu tiên là 4 số nguyên n,m,c[0],d[0], hai số cạnh nhau cách nhau bởi một khoảng trắng trong đó 1≤n≤1000, 1≤m≤10, 1≤c[0],d[0]≤100. Trong m dòng tiếp thep, mỗi dòng sẽ gồm 4 số nguyên a[i],b[i],c[i],d[i], hai số cạnh nhau cách nhau bởi một khoảng trắng, trong đó 1≤a[i],b[i],c[i],d[i]≤100 với 1≤i≤m. Kết quả: In ra file GOIBANH.OUT, mộ số nguyên duy nhất là số tiền lớn nhất mà ông chủ cửa hàng có thể nhận được, tính theo đơn vị nghìn đồng. Ví dụ. GOIBANH.INP GOIBANH.OUT 10 2 2 1 7 3 2 100 12 3 1 10 241 Giải thích. Trong test trên, ông chủ cửa hàng có thể gói 2 bánh với nhân 1, 4 bánh với loại nhân 2 và 1 bánh không có nhân. Tổng số tiền thu được là 2x100+4x10+1 = 241 nghìn đồng. Câu 5. (7 điểm) CHIA NHÓM VĂN NGHỆ Để chào đón ngày Nhà giáo Việt Nam 20/11 sắp tới, một trường THPT trên địa bàn Đồng Tháp đang ráo riết tập dượt tổ chức biểu diễn văn nghệ. Sau khi tuyển chọn được n em học sinh từ các khối lớp của trường, thầy thể dục định chia họ thành các nhóm 3 người để thực hiện tiết mục múa (giả sử n là số chia hết cho 3) và mỗi học sinh phải thuộc về đúng một nhóm. Tuy nhiên, trong n em này, có một số học sinh quen nhau và thầy muốn rằng, nếu có hai học sinh nào đó quen nhau thì bắt buộc họ phải thuộc cùng một nhóm (chú ý rằng theo điều kiện này thì một nhóm không nhất thiết phải có học sinh đếu quen biết nhau). Thầy bèn đánh số các học sinh từ 1 đến n và ghi chú lại cá cặp họa sinh quen biết nhau, mỗi cặp xuất hiện không quá một lần trong danh sách của thầy. Tất nhiên A quen B thì B cũng sẽ quen A. Sau khi nhận được danh sách các cặp học sinh quan nhau này, thầy đang rất đau đấu để chia nhóm cho họ. Việc chia có thể không khó nhưng trước hết, thầy muốn biết rằng có tồn tại cách chia như vậy không. Bạn hãy giúp thầy nhé! Yêu cầu: Hãy xác định xem với danh sách các cặp học sinh quen nhau đã có, thầy giáo có thể chia được tất cả học sinh này thành các nhóm 3 người mà các học sinh quen nhau đều sẽ thuộc cùng một nhóm được hay không. Dữ liệu vào: Trong file CHIANHOM.INP, dòng thứ nhất gồm các số n,m cách nhau bởi một khoảng trắng chỉ số học sinh trong đội văn nghệ và số cặp học sinh quen biết nhau trong danh sách. Điều kiện 0 - Xem thêm -