Chu de 07 2015

<span class='text_page_counter'>(1)</span>LUYỆN THI HỌC SINH GIỎI MÔN TIN HỌC Thời gian làm bài: 150 phút. CHỦ ĐỀ 07 SẮP XẾP. Tổng quan TT. Tên bài. 1 2 3. Kết nối số Tổ chức tham quan Tìm bội số. Tệp chương trình NOISO.PAS TCTQ.PAS TIMBS.PAS. Tệp dữ liệu. Tệp kết quả. NOISO.INP TCTQ.INP TIMBS.INP. NOISO.OUT TCTQ.OUT TIMBS.OUT. Thời Gian 1s/test 1s/test 1s/test. Bài 1. (6 điểm) KẾT NỐI SỐ Cho N số nguyên dương a[1], a[2],..a[N], mỗi số không vượt quá 10 9. Từ các số nguyên dương đó, người ta tạo ra các số nguyên dương mới bằng cách kết nối (viết liên tiếp nhau) tất cả các số đã cho. Ví dụ: với N = 4 và các số 12, 34, 567, 890, ta có thể tạo ra các số mới như sau: 1234567890, 3456789012, 8905673412,... Dễ thấy rằng có tất cả 4! = 24 số được tạo ra theo cách đó. Trong 24 số mới tạo thành đó, số 9805673412 là số lớn nhất. Yêu cầu: Cho biết số N (1<N<=100) và N số a[1], a[2],..a[N], tìm số lớn nhất tạo thành bằng cách kết nối theo cách đã nêu. Dữ liệu: Đọc vào từ tệp NOISO.INP, gồm nhiều phương án, mỗi phương án trên một dòng, trên dòng đó ghi số N, tiếp sau là N số a[1], a[2],..a[N]. Kết quả: Ghi ra màn hình và ghi ra tệp NOISO.OUT, mỗi phương án trên một dòng, trên dòng đó ghi độ dài DD của số kết nối lớn nhất SKN tìm được, tiếp đó, nếu DD<=20 thì ghi ra số SKN đó, trái lại, nếu DD > 20 thì ghi ra 10 chữ số đầu, dấu ba chấm (...), và 10 chữ số cuối của SKN, để trong cặp ngoặc vuông. Ví dụ: NOISO.INP NOISO.OUT 4 12 34 567 890 10 [8905673412] 9 12 34 567 890 321 123 45 54 678 23 [8906785675...3432112312] Bài 2. (7 điểm) TỔ CHỨC THAM QUAN Một công ty du lịch tổ chức cho N đoàn (đánh từ số 1 đến N) đi tham quan. Mỗi đoàn đi tham quan một địa điểm khác nhau. Đoàn thứ i đi tham địa điểm ở cách khách sạn D i km (i=1,2,...., N). Công ty có M xe khách, đánh số từ 1 đến M (MN) để phục vụ việc đưa các đoàn đi thăm quan. Xe thứ j có mức tiêu thụ xăng là V j lít/km. Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng X cần sử dụng là ít nhất. Dữ liệu: Đọc từ tệp văn bản TCTQ.INP, gồm nhiều phương án, mỗi phương án ghi trên 1 dòng, trên dòng đó ghi 2 số tự nhiên N, M (1<= N <= M <= 200), tiếp theo là N số D i (1 <= i <= N), tiếp theo là M số Vj (1 <= j <= M); Kết quả: Ghi ra màn hình và ghi ra tệp văn bản TCTQ.OUT, mỗi phương án trên 1 dòng, trên dòng đó ghi tổng số lít xăng X cần dùng cho việc đưa các đoàn đi tham quan (không tính lượt về), tiếp theo đó ghi N số C i, là chỉ số của xe dùng để chở đoàn thứ i (1 <= i <= N). N số Ci đó cần để trong cặp ngoặc vuông [].. Ví dụ:. TCTQ.INP 3 4 7 5 9 17 13 15 10 4 5 7 5 9 17 13 15 10 22 31. TCTQ.OUT 256 [2 3 4] 502 [2 4 1 3]. Bài 3. (7 điểm) TÌM BỘI SỐ Cho số nguyên dương S có không quá 250 chữ số hệ 10. Yêu cầu: Tìm bội số lớn nhất của 30, tạo được bằng cách xáo trộn các chữ số của số S nói trên..

<span class='text_page_counter'>(2)</span> Dữ liệu: Đọc từ tệp TIMBS.INP, gồm nhiều phương án, mỗi phương án trên 1 dòng, trên dòng đó ghi số S. Kết quả: Ghi ra màn hình và ghi ra tệp TIMBS.OUT, mỗi phương án trên một dòng, trên dòng đó ghi bội số tìm được. Nếu không tìm được bội số theo yêu cầu trên thì ghi số 0.. Ví dụ:. TIMBS.INP 102 2931. TIMBS.OUT 210 0. TÓM TẮT LÝ THUYẾT Sắp xếp là một công việc cần thiết và thường phải thực hiện trong thực tế. Ví dụ: sắp xếp danh sách theo thứ tự AB-C của tên gọi, sắp xếp các thí sinh theo tổng số điểm thi giảm dần để xác định điểm chuẩn vào trường, sắp xếp cán bộ - nhân viên theo năm sinh để giải quyết chế độ hưu trí, … Dù biểu diễn dữ liệu ở dạng nào thì sắp xếp cũng thường dẫn đến việc sắp xếp mảng. Cần chú ý rằng xâu ký tự cũng là một dạng mảng, mà các phần tử của nó là các ký tự, nên cũng có thể áp dụng các thuật toán sắp xếp như đối với các mảng (xem thêm Phần 3. Xâu ký tự)..

<span class='text_page_counter'>(3)</span> Đã có khá nhiều thuật toán sắp xếp được đề xuất như sắp xếp kiểu nổi bọt (Bubble Sort), sắp xếp kiểu chọn (Selection Sort), sắp xếp kiểu chèn (Insertion Sort), sắp xếp nhanh (Quick Sort), sắp xếp kiểu vun đống (Heap Sort), sắp xếp kiểu trộn (Merge Sort), sắp xếp kiểu đếm phân phối (Distibution Counting)… Trong bài này chúng ta sẽ chỉ làm quen với thuật toán sắp xếp đơn giản và thường dùng nhất là sắp xếp nổi bọt, thường được dùng khi số phần tử của mảng không lớn lắm (khoảng vài ngàn phần tử trở lại). Các thuật toán sắp xếp khác sẽ được trình bày ở nơi thích hợp (xem thêm Phần 5. Một số giải thuật nâng cao). Để thuận lợi cho việc trình bày, ta giả sử rằng cần sắp xếp mảng A có N phần tử kiểu longint, và ta muốn sắp xếp theo thứ tự tăng dần (khi muốn sắp xếp theo thứ tự giảm dần, chỉ cần đổi chiều dấu so sánh trong các câu lệnh). Sắp xếp tăng dần: Duyệt với i từ 1 đến N-1 Duyệt với j từ i+1 đến N Nếu A[i] > A[j] thì đổi chỗ A[i], A[j]. Việc đổi chỗ các phần tử A[i] và A[j] của mảng A cho nhau được thực hiện nhờ biến phụ t có kiểu là kiểu của phần tử của mảng: Đặt t = A[i], A[i] = A[j], A[j] = t.. GIỢI Ý CÁCH GIẢI Bài 1. Số kết nối lớn nhất được tạo thành nhờ các bước sau: 1. Sắp xếp các phần tử của mảng A theo thứ tự giảm dần của các xâu ký tự tương ứng (không phải theo giá trị số của chúng). 2. Ghép các số nhận được với nhau. Khi độ dài DD của số kết nối lớn hơn 20, để đưa kết quả ra theo yêu cầu, cần làm như sau: 1. Tạo XauDau chỉ chứa 10 chữ số đầu của số kết nối Khởi tạo s = ‘’, i = 0 Lặp lại khi độ dài của s còn nhỏ hơn 10:.

<span class='text_page_counter'>(4)</span> i=i+1 s = s + a[i] Nhớ lại 10 chữ số đầu của s vào XauDau. 2. Tạo XauCuoi chỉ chứa 10 chữ số cuoi của số kết nối Khởi tạo s = ‘’, i = N+1 Lặp lại khi độ dài của s còn nhỏ hơn 10: i=i-1 s = a[i] + s Nhớ lại 10 chữ số cuối của s vào XauCuoi. Bài 2. Một số lưu ý khi giải bài toán này: 1. Sắp xếp các mảng dữ liệu theo thứ tự tăng dần, kèm theo các chỉ số tương ứng. Trong phần mã nguồn, đã sử dụng thuật toán sắp xếp nổi bọt. 2. Chọn xe có định mức tiêu thụ xăng nhỏ hơn cho đoàn có đoạn đường đi dài hơn, chú ý lấy ra đúng chỉ số của xe cho từng đoàn. 3. Để dễ quản lý, trong mã nguồn đã kết hợp 2 mảng thành 1 mảng hai chiều, cụ thể: DV[1,i] (1 <= i <= N) lúc đầu là mảng chứa độ dài đường đi của các đoàn khách, đến cuối, mảng này được dùng để chứa chỉ số của các xe phục vụ đoàn tương ứng. DV[2,j] (1 <= j <= M) là mảng chứa định mức tiêu thụ xăng của các xe. Tương tự: CS[1,i] (1 <= i <= N) là mảng chứa chỉ số của các đoàn khách. CS[2,j] (1 <= j <= M) là mảng chứa chỉ số của các xe. Bài 3. 1. Đọc dữ liệu từ tệp: Vì S có thể có đến 250 chữ số hệ 10 nên ta dùng xâu ký tự để chứa nó. 2. Điều kiện tìm được bội số của 30: Bội số của 30 phải là số vừa chia hết cho 10 vừa chia hết cho 3. Điều kiện để bội số tìm được chia hết cho 10 là trong các chữ số của số S ban đầu phải có ít nhất 1 chữ số ‘0’. Điều kiện để bội số tìm được chia hết cho 3 là tổng các chữ số của số S ban đầu phải chia hết cho 3. 3. Sắp xếp: Dùng thuật toán sắp xếp nổi bọt đối với xâu ký tự, đã nêu ở phần Tóm tắt lý thuyết. 4. Hiển thị kết quả: thực hiện theo yêu cầu đề bài. DỮ LIỆU ĐỂ KIỂM TRA BÀI 1 Tệp NOISO.INP (Chú ý: dữ liệu kéo dài đến dòng tụt vào ngay sau) 4 12 34 567 890 9 12 34 567 890 321 123 45 54 678 5 321 123 45 54 678 9 12 34 567 890 321 123 45 54 678 11 145 554 7678 1321 3123 212 434 7567 9890 212 345 15 145 554 7678 1321 3123 212 434 7567 9890 212 345 132 374 5867 8904 20 145 554 7678 1321 3123 212 434 7567 9890 212 345 132 374 5867 8904 3121 1323 455 544 6789 25 145 554 7678 1321 3123 212 434 7567 9890 212 345 132 374 5867 8904 3121 1323 455 544 678 1321 3123 545 454 96789 Tệp NOISO.OUT 10 [8905673412].

<span class='text_page_counter'>(5)</span> 23 [8906785675...3432112312] 13 [6785445321123] 23 [8906785675...3432112312] 38 [9890767875...2121451321] 52 [9890890476...1451321132] 70 [9890890476...3231321132] 88 [9890967898...3211321132] DỮ LIỆU ĐỂ KIỂM TRA BÀI 2 Tệp TCTQ.INP 3 4 7 5 9 17 13 15 10 4 5 7 5 9 17 13 15 10 22 31 5 6 12 87 28 34 70 24 43 48 17 52 16 6 6 12 87 28 34 70 24 43 48 17 52 16 50 5 8 12 87 28 34 70 24 43 48 17 52 16 85 15 6 7 70 36 17 79 54 89 61 95 71 40 10 73 99 6 8 92 43 79 39 72 85 37 24 39 51 32 84 35 53 7 7 89 84 11 22 22 55 11 10 79 68 79 73 60 28 7 9 89 84 11 22 22 55 11 10 79 68 79 73 60 28 71 70 Tệp TCTQ.OUT 256 [2 3 4] 502 [2 4 1 3] 5178 [3 6 2 1 4] 7212 [4 5 2 1 3 6] 4191 [2 8 1 4 6] 16397 [1 6 2 4 3 5] 14023 [2 3 7 4 1 5] 11382 [1 7 4 3 5 6 2] 11162 [1 7 5 3 9 6 8]. DỮ LIỆU ĐỂ KIỂM TRA BÀI 3 Tệp TIMBS.INP 102 2931 342057 4250793 57093428 605793423 7157093427 81650793428. Tệp TIMBS.OUT 210 0 754320 9754320 0 976543320 9777543210 0.

<span class='text_page_counter'>(6)</span> MÃ NGUỒN BÀI 1 (Tệp NOISO.PAS). {Phan khai bao chung} uses crt; Const tentep = 'NOISO'; ktm = 100; Type str10 = string[10]; Var N: longint; {Dau vao} a: array[1..ktm] of str10; {Dau vao/ Dau ra} DD: longint; {Dau ra} xaudau,xaucuoi: str10; {dau ra} pa, sopa: longint; {QL phuong an} f: text; {Bien tep} {Dem so phuong an} procedure DemSoPA; BEGIN assign(f,tentep+'.INP');. reset(f); sopa:=0; while (not eof(f)) do begin readln(f); inc(sopa); end; close(f); END; {Doc du lieu cua phuong an pa} procedure DocPA; var i, ai: longint; s: str10; BEGIN assign(f,tentep+'.INP'); reset(f); i:=1;.

<span class='text_page_counter'>(7)</span> while (i<pa) do begin readln(f); inc(i); end; read(f,N); for i:=1 to N do {Doc va doi thanh xau} begin read(f,ai); str(ai,s); a[i] := s; end; close(f); END; {Ghi ket qua ra man hinh va tep tin} procedure GhiKQ; var i: longint; BEGIN assign(f,tentep+'.OUT'); if pa=1 then rewrite(f) else append(f); write(DD,' ['); write(f,DD,' ['); if DD <= 20 then begin for i:= 1 to N do begin write(a[i]); write(f,a[i]); end; end else begin write(xaudau); write(f,xaudau); write('...'); write(f,'...'); write(xaucuoi); write(f,xaucuoi); end; writeln(']'); writeln(f,']'); close(f); END; {Sap xep kieu noi bot} Procedure SapXepGiam; var n1,i,i1,j: longint;. ai: str10; BEGIN n1 := N - 1; for i:= 1 to N1 do begin i1 := i + 1; for j := i1 to N do if a[i] < a[j] then begin ai := a[i]; a[i] := a[j]; a[j] := ai; end; end; END; {Tao ket qua de dua ra} procedure TimSKN; var i, ij: longint; s: string; BEGIN SapXepGiam; DD := 0; for i:= 1 to N do DD := DD + length(a[i]); if DD > 20 then begin ij := 0; {Lay 10 chu so dau} s := ''; i := 1; while ij < 10 do begin s := s + a[i]; ij := ij + length(a[i]); inc(i); end; xaudau := ''; for i:= 1 to 10 do xaudau := xaudau + s[i]; ij := 0; {Lay 10 chu so cuoi} s := ''; i := N; while ij < 10 do begin s := a[i] + s; ij := ij + length(a[i]); dec(i); end; xaucuoi := '';.

<span class='text_page_counter'>(8)</span> for i:= 1 to 10 do xaucuoi := s[ij - i + 1] + xaucuoi; end; END; {Chuong trinh chinh} BEGIN clrscr; DemSoPA; for pa:=1 to sopa do. begin DocPA; TimSKN; GhiKQ; end; writeln; write('Da xong. Nhan ENTER de thoat.'); Readln; END.. GIẢI THÍCH MÃ NGUỒN BÀI 1 1. Chương trình chính. Sau khi gọi lệnh DemSoPA, vòng lặp For gọi các lệnh DocPA, TimSKN, và GhiKQ. 2. Lệnh DemSoPA: đếm số phương án có trong tệp dữ liệu. 3. Lệnh DocPA: đọc dữ liệu của phương án thứ pa. 4. Lệnh GhiKQ: ghi kết quả ra màn hình và tệp tin. 5. Lệnh TimSKN: Tìm độ dài DD và mảng các chữ số của số kết nối để đưa ra, thuật giải đã nêu ở phần Gợi ý cách giải. Lệnh này gọi đến lệnh SapXepGiam. 6. Lệnh SapXepGiam: Sắp xếp các xâu số theo thứ tự giảm dần. Lệnh này gọi đến lệnh DoiCho. 7. Lệnh DoiCho(ii, jj): Đổi chỗ các phần tử A[ii] và A[jj] của mảng A cho nhau.. MÃ NGUỒN BÀI 2 (Tệp TCTQ.PAS) {Phan khai bao chung} uses crt; const tentep = 'TCTQ'; {Ten tep} ktm = 200; {Kich thuoc mang} type Mang2D = array[1..2,1..ktm] of longint; {Kieu mang 2 chieu} var n, m, sum: longint; {So doan, so xe, tong luong xang} DV: Mang2D; {Quang duong, dinh muc xang} CS: Mang2D; {Chi so cua cac xe} sopa, pa: byte; {QL phuong an} f:text; {Bien tep} {Dem so phuong an}.

<span class='text_page_counter'>(9)</span>

<span class='text_page_counter'>(10)</span>

<span class='text_page_counter'>(11)</span>

<span class='text_page_counter'>(12)</span>

<span class='text_page_counter'>(13)</span>

<span class='text_page_counter'>(14)</span>

<span class='text_page_counter'>(15)</span>

<span class='text_page_counter'>(16)</span>

<span class='text_page_counter'>(17)</span>

<span class='text_page_counter'>(18)</span> for i := 1 to M do CS[2,i] := i; xe} END;. {Chi so cua cac. {Doi cho cac phan tu thu ii va jj cua mang thu tt} procedure DoiCho(tt, ii,jj: longint; var mang: Mang2D); var tg: longint; BEGIN Tg := mang[tt, ii]; mang[tt, ii] := mang[tt, jj]; mang[tt, jj] := Tg; END; {Sap xep tang dan, giai thuat QuickSort} procedure SapXepTang(t, c: longint); var c1, i, i1, j: longint; BEGIN c1 := c - 1; for i := 1 to c1 do begin i1 := i + 1; for j := i1 to c do if DV[t,i] < DV[t,j] then begin DoiCho(t, i, j, DV); DoiCho(t, i, j, CS); end; end; END; {Tao ket qua de dua ra} Procedure BoTriXe; var i: longint; BEGIN SapXepTang(1, N); {Sap xep do dai duong di tang dan} SapXepTang(2, M); {Sap xep dinh muc xang tang dan} Sum := 0; {Tong luong xang can dung} for i := 1 to N do Sum := sum + DV[1, i] * DV[2, M - i + 1]; for i := 1 to N do DV[1, CS[1,i]] := CS[2, M - i + 1]; END; {Ghi ket qua ra man hinh va tep tin} procedure GhiKQ; var i: LongInt; BEGIN Assign(f, tentep+'.OUT'); if (pa = 1) then Rewrite(f) else Append(f); write(sum,' [',DV[1,1]);.

<span class='text_page_counter'>(19)</span> write(f, sum,' [',DV[1,1]); for i := 2 to N do begin write(' ',DV[1, i]); write(f, ' ',DV[1,i]); end; Writeln(']'); Writeln(f,']'); Close(f); END; {Chuong trinh chinh} BEGIN. clrscr; DemSoPA; for pa:=1 to soPA do begin DocPA; BoTriXe; GhiKQ; end; writeln; write('Da xong. Nhan ENTER de thoat.'); readln; END.. GIẢI THÍCH MÃ NGUỒN BÀI 2 1. Chương trình chính. Sau khi gọi lệnh DemSoPA, vòng lặp For gọi các lệnh DocPA, BoTriXe, và GhiKQ. 2. Lệnh DemSoPA: đếm số phương án có trong tệp dữ liệu. 3. Lệnh DocPA: đọc dữ liệu của phương án thứ pa. 4. Lệnh GhiKQ: ghi kết quả ra màn hình và tệp tin. 5. Lệnh BoTriXe: Tìm cách bố trí xe cho các đoàn khách, thuật giải đã nêu ở phần Gợi ý cách giải. Lệnh này gọi đến lệnh SapXepTang. 6. Lệnh SapXepTang(t, c): Sắp xếp mảng DV[t,.] theo chiều tăng dần, đồng thời sắp xếp lại mảng CS[t,.] tương ứng. Lệnh này gọi đến lệnh DoiCho. 7. Lệnh DoiCho(i, j, m): Đổi chỗ các phần tử A[i] và A[j] của mảng m cho nhau.. MÃ NGUỒN BÀI 3 (Tệp TIMBS.PAS) {Phan khai bao chung}. uses crt;.

<span class='text_page_counter'>(20)</span> const tentep = 'TIMBS'; var S: string; N: byte; sopa, pa: byte; f:text;. n1 := n - 1; for i:= 1 to n1 do begin i1 := i + 1; for j := i1 to N do if S[i] < S[j] then DoiCho(i,j); end; END;. {ten tep}. {dau vao/dau ra} {bien phu} {QL phuong an} {bien tep}. {Tao ket qua de dua ra} Procedure TimBS; var i: byte; tong: longint; co0: boolean; BEGIN n:= length(S); co0 := false; tong := 0; for i := 1 to N do begin tong := tong + ord(S[i]) - ord('0'); if S[i] = '0' then co0 := true; end; if co0 and (tong mod 3 = 0) then SapXepGiam else S := '0'; END;. {Dem so phuong an} procedure DemSoPA; BEGIN Assign(f, tentep+'.INP'); Reset(f); soPA:=0; while (not EOF(f)) do begin readln(f); inc(soPA); end; close(f); END; {Doc du lieu cua phuong an pa} procedure DocPA; var i: byte; BEGIN Assign(f, tentep+'.INP'); Reset(f); i:=1; while (i<pa) do begin Readln(f); inc(i); end; Readln(f, S); Close(f); END;. {Ghi ket qua ra man hinh va tep tin} procedure GhiKQ; var i: LongInt; BEGIN Assign(f, tentep+'.OUT'); if (pa = 1) then Rewrite(f) else Append(f); writeln(S); writeln(f, S); Close(f); END;. {Doi cho cac phan tu thu ii va jj cua xau so N} procedure DoiCho(ii,jj: byte); var ch: char; BEGIN ch := S[ii]; S[ii] := S[jj]; S[jj] := ch; END; {Sap xep giam dan} procedure SapXepGiam; var n1, i, i1, j: byte; BEGIN. {Chuong trinh chinh} BEGIN clrscr; DemSoPA; for pa:=1 to soPA do begin DocPA; TimBS; GhiKQ; end; writeln; write('Da xong. Nhan ENTER de thoat.'); readln; END.. GIẢI THÍCH MÃ NGUỒN BÀI 3.

<span class='text_page_counter'>(21)</span> 1. Chương trình chính. Sau khi gọi lệnh DemSoPA, vòng lặp For gọi các lệnh DocPA, TimBS, và GhiKQ. 2. Lệnh DemSoPA: đếm số phương án có trong tệp dữ liệu. 3. Lệnh DocPA: đọc dữ liệu của phương án thứ pa. 4. Lệnh GhiKQ: ghi kết quả ra màn hình và tệp tin. 5. Lệnh TimBS: Tìm bội số theo yêu cầu, thuật giải đã nêu ở phần Gợi ý cách giải. Lệnh này gọi đến lệnh SapXepTang. 6. Lệnh SapXepTang: Sắp xếp xâu S theo chiều tăng dần. Lệnh này gọi đến lệnh DoiCho. 7. Lệnh DoiCho(i, j): Đổi chỗ các phần tử S[i] và S[j] của xâu S cho nhau..

<span class='text_page_counter'>(22)</span>