//
you're reading...
Bài tập huấn luyện, Giáo trình Tin học cơ bản

Bài tập bổ sung: Chia kẹo

[Mục lục bài tập bổ sung]


Chuyên đề


Đề bài


Có n gói kẹo, mỗi gói có day[i] cái kẹo (i = 1 .. n). Hãy lập trình tìm cách chia n gói kẹo thành 2 nhóm sao cho chênh lệch (dương hoặc bằng 0) giữa hai nhóm là ít nhất.

Dữ liệu vào: File chiakeo.inp gồm 2 dòng:

  • Dòng đầu tiên ghi giá trị n (1<= n <= 20);
  • Dòng thứ  2 ghi n số day[i], mỗi số cách nhau dấu cách;

Dữ liệu ra: File chiakeo.out gồm 3 dòng:

  • Dòng đầu tiên ghi độ chênh lệch nhỏ nhất.
  • Dòng thứ 2 và thứ 3 ghi các giá trị a[i] thuộc về 2 nhóm sau khi tách.

Nếu có nhiều cách chia chỉ cần nêu ra một cách.

Ví dụ:

CHIAKEO.INP CHIAKEO.OUT
10 1
1 9 6 7 5 2 8 3 9 9 1 9 6 7 5 2
8 3 9 9

Hướng dẫn


[]


Chương trình


uses crt;
const
Maxpt = 1000000;
fi = 'd:\chiakeo.inp';
fo = 'd:\chiakeo.out';

type
m1= array[0..maxpt] of longint;
var
day, a,b,c : m1;
max, n,m,k,tong,dolech, i,j: longint;
f,g : text;
d: boolean;
procedure Nhap;
begin
assign(f,fi);
reset(f);
readln(f,n);
tong:= 0;
for i:=1 to n do
begin
read(f,day[i]);
end;
close(f);
end;
procedure KhoiTao;

begin
a[0]:= 0;
b[0]:= 0;
c[0]:= 0;
max:= 0;
for i:= 1 to n do
for j:= 0 to max do
begin
d:= true;
m:= max;
for k:= 0 to max do
if a[j] + day[i] = a[k] then d:= false;

if d then
begin
inc(m);
a[m]:= a[j]+day[i];
b[m]:= i;
c[m]:= j;
max:= m;
end;
end;
{for i:= 0 to max do
begin
write(a[i]:4);
write(b[i]:4);
write(c[i]:4);
writeln;
end; }

end;

procedure Truyvet;
var
logic: array[0..maxpt] of boolean;
nhom1, nhom2 : set of byte;
begin
writeln('Max = ',Max);
nhom1 :=[];
nhom2 :=[];
for k:= 1 to n do nhom1:= nhom1 +[k];
fillchar(logic, sizeof(logic),false);
write('Day 1: ');
while a[i]>0 do
begin
logic[b[i]]:=true;
i:= c[i];
end;

for i:= 0 to max do
if logic[i] then
begin
write(day[i],' ');
nhom2:= nhom2 + [i];
end;
writeln;
write('Day 2: ');
for i:= 0 to max do
if (i in nhom1-nhom2) then write(day[i],' ');
end;
BEGIN
clrscr;
Nhap;
for i:=1 to n do tong:=tong +day[i];
KhoiTao;

i:=0;
writeln('Tong = ',tong);
dolech:= -1;
repeat
dolech:= dolech +1;
while a[i] <> (dolech + tong) div 2 do
inc(i);
until ((dolech + tong) mod 2 = 0);
writeln('Do lech: ',dolech);
Truyvet;
END.
Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Staithes

Reflecting Pool

Golden Hour

More Photos

Thống kê

  • 115,384 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: