CHUYÊN ĐỀ CHIA KẸO
1, Cha keo: Có n gói keo vói mối gói có a[i] cái kẹo. Hãy chia số gói kẹo làm 2 sao cho chênh lech số kẹo là ít nhất.
2, Có các loại tiền có các mệnh giá 1000đ, 2000đ, 5000đ, 10000đ, 20000đ, 50000đ. Hãy trả n nghìn đồng sao cho tổng số tờ giấy bạc là càng ít càng tốt.
2, Đổi tiền: Có số tiền là M hãy đổi ra các mệnh giá a1, a2, a3,…,an. Sao cho số tờ là ít nhất.
3, Sau một thời gian tìm kiếm. cuối cùng Bờm cũng tìm được cong việc tại ngân hnàg KID Banh là ngân hang mới thành lập tại thị trấn. Một hôm nọ Bờm được Giám độc gọi lên và lập chương trình cho máy rut tiền tự động –ATM. Khổ nỗi bờm chỉ được đào tạo sửa chữa máy tính và nhừng hư hỏng thông thường cuả máy Phô tô, máy Fax và .. lập trình pascal.
Qua một thời gian tìm hiểu, Bờm thấy rằng, trong máy ATM có 6 ngăn đựng tiền riêng, các tờ tiền mệnh giá X lần lượt xếp vào các ngăn theo chiểu từ trên xuống là 10 đồng; 20 đồng, 50 đồng, 100 đồng , 200 đồng và 500 đồng, mỗi mêngh giá tiền X đồng đó lại lại có Y tờ tiềnn nhất định.
Hãy giúp Bờm viết chương trình cho máy ATM sao cho tổng số lượng tờ tiền khách hang nhận được là ít nhất mỗi khi khách hang rút tiền.
Dữ liệu: Vào từ tệp văn bản ATM.INP gồm 7 dòng:
- Dòng thứ nhất ghi số N là số tiền khách hang cần rút.
- Trong 6 dòng tiếp theo, mỗi dòng ghi:
+ Số thứ nhất là mệnh giá tiền X
+ Số thứ 2 Y là số tiền của mệnh giá X đồng hiện còn trong máy ATM ( số tờ của mỗi lạoi mệnh giá không quá 1000 tờ)
Kết quả: Đưa ra tệp văn bản ATM.OUT ghi 1 dòng duy nhất là tổng số tờ tiền mà khách hang nhậ được. Nếu không có phương án rút tiền thì ghi số -1
VD:
ATM.INP ATM.OUT ATM.INP ATM.OUT
180 10 44 20 2 50 3 100 2 200 0 500 9
4 10
10 0 20 2 50 3 100 2 200 1 500 0
-1
Giải thích:
VD1: Máy phải đưa ra mộtt tờ 100, một tờ 50, một tờ 20, một tờ 10. Vậy tổng số tờ là 4 VD2: Máy khồn đưa ra phương án, vậy ghi -1.
Bài 2 (7 điểm): Công ty sữa A có N loại sữa, đánh số từ 1 tới N với giá trị tương ứng S[1],..S[N].
Một người cần mua sữa với tổng số tiền bằng M.
Yêu cầu: Hãy chọn cho người đó một cách mua với số lượng sữa ít nhất hết tổng số tiền M.
Dữ liệu vào: Được cho bởi file văn bản SUA.INP trong đó dòng thứ nhất ghi 2 số nguyên dương N, M (N<=20, M<=1000). Trong N dòng tiếp theo, dòng thứ i ghi số S[i] (S[i] <=1000). Biết rằng ta luôn có thể chọn được số lượng sữa có tổng giá trị bằng M.
Dữ liệu ra: Ghi ra file văn bản SUA.OUT có N dòng, dòng thứ i ghi số lượng sữa i cần mua.
Ví dụ:
SUA.INP SUA.OUT
3 34 4 12 10
0 2 1
{Đổi tiền ra số tờ ít nhất}
VAR n,i,j,k,h,tien,tg,tg1:longint;
a,b,c:array[1..1000]of longint;
f,g:text;
Begin
assign(f,'men.inp');reset(f);
assign(g,'men.out');rewrite(g);
readln(f,n,tien);
for i:=1 to n do read(f,a[i]);
for i:=1 to n-1 do for j:=i+1 to n do if a[i]<=a[j] then begin
tg:=a[i];
a[i]:=a[j];
a[j]:=tg;
end;
i:=1;
repeat k:=0;
while tien>=a[i] do begin
tien:=tien-a[i];
inc(k);
end;
c[i]:=k;
inc(i);
until (i>n)or(tien=0);
for i:=1 to n do h:=h+c[i];
writeln(g,h);
for j:=n downto 1 do write(g,c[j],' ');
close(f);
close(g);
End.
{ Chia kẹo làm 2 phần sao cho số kẹo chênh lệch là ít nhất}
Var n,i,k,j,h,s,s1,tg:longint;
tg1:boolean;
a:array[1..500]of longint;
b:array[1..500]of boolean;
f,g:text;
Begin
assign(f,'chiakeo.inp');reset(f);
assign(g,'chiakeo.out');rewrite(g);
readln(f,n);
for i:=1 to n do begin
read(f,a[i]);
b[i]:=true;
s:=s+a[i];
end;
s1:=s div 2;
for i:=1 to n-1 do for j:=i+1 to n do if a[i]<a[j] then begin
tg:=a[i];
a[i]:=a[j];
a[j]:=tg;
end;
i:=1;
repeat
if (s1>=a[i]) and b[i] then begin
b[i]:=false;
s1:=s1-a[i];
end;
inc(i);
until (s1<=0)or(i>n);
for i:=1 to n do if b[i]<>true then write(g,a[i],' ');
writeln(g);
for i:=1 to n do if b[i]=true then write(g,a[i],' ');
close(f);
close(g);
End.
{Rút thẻ ATM}
var a,b:array[1..10] of longint;f,f1:text;
tg,tg1,i,j,h,k,d,n:longint;
begin
assign(f,'ATM.inp');reset(f);
assign(f1,'ATM.out');rewrite(f1);
READ(f,n);
for i:=1 to 6 do
begin read(f,a[i],b[i]);end;
for i:=1 to 5 do for j:=i+1 to 6 do if a[i]<a[j] then begin
tg:=a[i];
a[i]:=a[j];
a[j]:=tg;
tg1:=b[i];
b[i]:=b[j];
b[j]:=tg1;end;
i:=0;k:=0;
repeat inc(i);d:=0;
while(n>=a[i])and(d<b[i]) do begin
n:=n-a[i];inc(d);
end;
k:=k+d;
until (n=0) or(i>6);
if n=0 then write(f1,k) else
write(f1,'-1');
close(f);
close(f1);
end.
