Bài Tập Tin Học Nhà Trường Tập III: Bài Tập 151 Đến 200

Bài Tập Tin Học Nhà Trường Tập III là một tài liệu quý giá cho học sinh và giáo viên trong việc nâng cao kỹ năng tin… 129 trang · Tin học & Nhà trường · 2013.

• Tác giả: Trần Sĩ Tùng
• Trường học: Tin học & Nhà trường
• Đề tài: Bài Tập Tin Học Nhà Trường Tập III: Các Bài Tập Từ 151 Đến 200
• Loại tài liệu: bài tập
• Năm xuất bản: 2013

Tóm tắt

I. Giới thiệu về Bài Tập Tin Học Nhà Trường Tập III Các Bài Tập Từ 151 Đến 200

Bài Tập Tin Học Nhà Trường Tập III là một tài liệu quý giá cho học sinh và giáo viên trong việc nâng cao kỹ năng tin học. Tập này bao gồm các bài tập từ 151 đến 200, giúp người học rèn luyện tư duy logic và khả năng giải quyết vấn đề. Các bài tập được thiết kế đa dạng, từ cơ bản đến nâng cao, phù hợp với nhiều đối tượng học sinh.

1.1. Tổng quan về nội dung bài tập tin học

Tài liệu này bao gồm nhiều bài tập khác nhau, từ các bài toán đơn giản đến phức tạp, giúp học sinh làm quen với các khái niệm cơ bản trong tin học.

1.2. Mục tiêu của Bài Tập Tin Học

Mục tiêu chính của tài liệu là giúp học sinh phát triển kỹ năng tư duy phản biện và khả năng lập trình thông qua các bài tập thực hành.

II. Vấn đề và Thách thức trong Bài Tập Tin Học

Trong quá trình học tập, học sinh thường gặp phải nhiều thách thức khi giải quyết các bài tập tin học. Những vấn đề này có thể đến từ việc hiểu sai đề bài, thiếu kiến thức nền tảng hoặc không biết cách áp dụng lý thuyết vào thực tiễn.

2.1. Những khó khăn thường gặp khi giải bài tập

Học sinh thường gặp khó khăn trong việc phân tích đề bài và xác định phương pháp giải quyết phù hợp.

2.2. Cách khắc phục những thách thức này

Giáo viên có thể hỗ trợ học sinh bằng cách cung cấp thêm tài liệu tham khảo và tổ chức các buổi ôn tập.

III. Phương pháp Giải Bài Tập Tin Học Hiệu Quả

Để giải quyết các bài tập tin học một cách hiệu quả, học sinh cần áp dụng một số phương pháp nhất định. Những phương pháp này không chỉ giúp tiết kiệm thời gian mà còn nâng cao khả năng tư duy.

3.1. Phương pháp phân tích đề bài

Phân tích đề bài là bước đầu tiên và quan trọng nhất trong quá trình giải bài tập. Học sinh cần xác định rõ yêu cầu và các dữ liệu đã cho.

3.2. Sử dụng các công cụ hỗ trợ

Các phần mềm lập trình và công cụ trực tuyến có thể giúp học sinh kiểm tra và tối ưu hóa mã nguồn của mình.

IV. Ứng dụng Thực Tiễn của Bài Tập Tin Học

Các bài tập trong tài liệu không chỉ mang tính lý thuyết mà còn có ứng dụng thực tiễn cao. Học sinh có thể áp dụng kiến thức đã học vào các dự án thực tế, từ đó nâng cao kỹ năng lập trình và tư duy logic.

4.1. Các dự án thực tế từ bài tập

Nhiều bài tập trong tài liệu có thể được áp dụng vào các dự án thực tế, giúp học sinh hiểu rõ hơn về cách thức hoạt động của các chương trình máy tính.

4.2. Kết quả nghiên cứu từ việc thực hành

Nghiên cứu cho thấy việc thực hành thường xuyên giúp học sinh cải thiện đáng kể kỹ năng lập trình và khả năng giải quyết vấn đề.

V. Kết luận và Tương lai của Bài Tập Tin Học

Bài Tập Tin Học Nhà Trường Tập III không chỉ là một tài liệu học tập mà còn là một công cụ hữu ích giúp học sinh phát triển kỹ năng cần thiết cho tương lai. Việc nắm vững các bài tập trong tài liệu sẽ tạo nền tảng vững chắc cho học sinh trong lĩnh vực công nghệ thông tin.

5.1. Tầm quan trọng của việc học tin học

Tin học ngày càng trở nên quan trọng trong mọi lĩnh vực, từ giáo dục đến công nghiệp.

5.2. Hướng phát triển trong tương lai

Tương lai của tin học sẽ tiếp tục phát triển mạnh mẽ, và việc học tập từ sớm sẽ giúp học sinh dễ dàng thích nghi với những thay đổi này.

Nội dung chính

BÀI TẬP TIN HỌC – TIN HỌC & NHÀ TRƯỜNG (TẬP III: BÀI 151 – 200)

Tổng quan về giáo trình

Tài liệu "Bài Tập Tin Học – Tin học & Nhà trường Tập III (Các Bài Tập Từ 151 – 200)" do tác giả Trần Sĩ Tùng tuyển tập và biên soạn lại vào năm 2013, có nguồn gốc từ chuyên mục Đề ra kỳ này của Tạp chí Tin học & Nhà trường trong giai đoạn 2003–2004. Trong chương trình đào tạo chuyên ngành Khoa học Máy tính, Công nghệ Thông tin và hệ thống bồi dưỡng học sinh giỏi Tin học, tài liệu này giữ vai trò là một tài liệu bài tập chuyên đề thực hành giải thuật và cấu trúc dữ liệu nâng cao.

Mục tiêu học tập của tài liệu tập trung vào ba kết quả cốt lõi:

1. Rèn luyện tư duy mô hình hóa các bài toán logic, hình học, số học và thực tiễn vào các cấu trúc dữ liệu hình thức.
2. Phân tích, thiết kế và tối ưu hóa độ phức tạp thuật toán về cả hai phương diện: thời gian thực thi ($O$) và không gian bộ nhớ (RAM/Heap).
3. Hiện thực hóa giải thuật thông qua ngôn ngữ lập trình cấu trúc (Pascal), thao tác trực tiếp với luồng tệp tin văn bản định dạng chuẩn (.INP và .OUT).

Cấu trúc tài liệu được tổ chức theo phương pháp phân đoạn bài toán kinh điển, gồm hai phần tách biệt:

• Phần 1: Tuyển tập Đề bài (từ Bài 151 đến Bài 200): Mỗi bài toán đều quy định rõ ràng ngữ cảnh thực tế, giới hạn thông số đầu vào, cấu trúc tệp dữ liệu vào (INPUT) và tệp kết quả ra (OUTPUT) kèm ví dụ minh họa cụ thể.
• Phần 2: Lời giải và Phân tích thuật toán: Trình bày chi tiết tư tưởng giải thuật, công thức toán học truy hồi, phân tích những sai lầm phổ biến của người học, kèm theo mã nguồn chương trình mẫu hoàn chỉnh.

Điểm đặc trưng của tài liệu là sự kết hợp giữa các bài toán đố tư duy logic số học (như bài toán Người nông dân và quả táo, Tuổi cha và con, Rán bánh) với các bài toán tối ưu hóa giải thuật quy mô lớn (như Bố trí phòng họp với $N \le 1.000.000$, Phân phối hàng với $N \le 10.000$).

---

Nội dung kiến thức cốt lõi

Các chương và chủ đề chính

Tài liệu bao quát 50 bài toán chuyên đề (từ Bài 151 đến Bài 200), có thể phân loại thành 6 nhóm chủ đề học thuật chính:

                          CÁC CHỦ ĐỀ THUẬT TOÁN (BÀI 151 - 200)
 1. Quy hoạch động   2. Tham lam & Sắp xếp          3. Lý thuyết Đồ thị  4. Hình học & Ma trận
 (DP & Optimization) (Greedy & Sorting)             (Graphs & Trees)     (Geometry & Grids)
  - Biến đổi xâu      - Phân phối hàng (Qsort)       - Dây chuyền TB      - Bao lồi chuẩn
  - Dãy con lồi       - Bố trí phòng họp ($N=10^6$)  - Cân bằng cây       - Nhà gương cười
  - Bày tranh, Bán hàng                             - Truyền tin mạng    - Đường đi con rắn

1. Quy hoạch động (Dynamic Programming):

   • Biến đổi xâu (Bài 157): Bài toán khoảng cách chỉnh sửa (Levenshtein Distance) sử dụng bảng quy hoạch động 2 chiều $L[i,j]$ với 3 thao tác cơ bản: Xóa ($D$), Chèn ($I$) và Thay thế ($R$).
   • Dãy con lồi (Bài 159): Kỹ thuật xây dựng đồng thời hai bảng phương án tăng dần ($U[i]$) và giảm dần ($D[i]$) để xác định điểm gãy tối ưu $vt$ thỏa mãn độ dài cực đại $U[vt] + D[vt] - 1$.
   • Bày tranh (Bài 156) và Bán hàng (Bài 163): Quy hoạch động trạng thái nhiều chiều, ứng dụng kỹ thuật quay vòng hai mảng một chiều ($a1, a2$) để tiết kiệm không gian bộ nhớ.
   • Tìm vị trí đặt trạm (Bài 165): Tối ưu hóa minimax khoảng cách đặt $k$ bể chứa xăng trên tuyến đường phục vụ $n$ trạm bán với công thức $S[i,j] = \max(S[i-1, h], ff(h, j))$.

2. Thuật toán Tham lam và Kỹ thuật Sắp xếp:

   • Phân phối hàng từ 2 kho (Bài 153): Mô hình bài toán cực tiểu hóa hàm mục tiêu tuyến tính $\sum (A_i - B_i) \cdot F_i$ thông qua việc sắp xếp mảng chênh lệch chi phí bằng QuickSort và quản lý dữ liệu gián tiếp bằng mảng chỉ số cs[i].
   • Bố trí phòng họp (Bài 155): Bài toán chọn tập khoảng không giao nhau (Activity Selection) với số lượng cuộc họp lớn ($N \le 1.000.000$). Giải thuật sắp xếp theo thời điểm kết thúc sớm nhất được tối ưu hóa bằng mảng trực tiếp kích thước $MaxN = 32.000$.

3. Lý thuyết Đồ thị và Cấu trúc Cây:

   • Dây chuyền thông báo (Bài 162): Biểu diễn đồ thị có hướng để phát hiện các thành phần liên thông, phân rã đồ thị thành tập hợp $a$ cây và $b$ chu trình rời rạc, từ đó thiết lập phương án nối ngọn cây này với gốc cây kia để tạo chu trình đơn nhất với chi phí $a+b$ lần đổi.
   • Cân bằng trên cây (Bài 173): Xác định trọng tâm của cây (Tree Centroid) thông qua việc duyệt và tính toán kích thước của thành phần liên thông lớn nhất trong rừng sau khi loại bỏ từng đỉnh.
   • Truyền tin trên mạng (Bài 160): Bài toán tìm $K$ đường đi ngắn nhất không chung cạnh trên đồ thị trọng số.

4. Hình học tính toán và Bài toán trên lưới ô vuông:

   • Bao lồi chuẩn (Bài 170 - Princessland): Tìm đa giác lồi diện tích nhỏ nhất bao quanh tập điểm với các cạnh định hướng theo 4 phương (song song, vuông góc hoặc nghiêng $45^\circ$).
   • Nhà gương cười (Bài 172) & Đường đi con rắn (Bài 176): Kỹ thuật duyệt ma trận, tính toán chu vi đường biên nhìn thấy và mô phỏng hướng di chuyển có ràng buộc vật cản trên lưới tọa độ.
   • Tọa độ tam giác đều (Bài 179) & Đường thẳng chia đôi (Bài 191): Nhận dạng hình học thuần túy trên lưới tam giác vô hạn và phân chia tập $2N$ điểm bằng đường thẳng $ax + by + c = 0$.

5. Tổ hợp, Xử lý số học và Dãy số:

   • Số Catalan (Bài 183): Tính số Catalan và bài toán ánh xạ song ánh giữa thứ tự từ điển với cấu hình dãy ngoặc/dãy bước đi.
   • Món quà may mắn (Bài 169): Dãy số dạng $3^i \cdot 5^j \cdot 7^k$ (Hamming numbers mở rộng).
   • Chia kẹo (Bài 152): Phân tích sự giới hạn của phương pháp Quy hoạch động ba lô khi $N = 10.000$ và đề xuất giải thuật tìm kiếm cục bộ / tối ưu hóa chênh lệch bằng phép tráo đổi phần tử.

6. Suy luận Logic và Phương trình Số học:

   • Tập hợp các bài toán suy luận đại số và nghiệm nguyên: Người bạn cũ (Bài 161 - phân tích $2450 = 2 \times 5^2 \times 7^2$), Tuổi cha và con (Bài 154), Đàn gia súc (Bài 177), Gà và Thỏ (Bài 187).

Kiến thức nền tảng được xây dựng

Tài liệu cung cấp nền tảng vững chắc về:

• Đại số tổ hợp và Số học: Dấu hiệu chia hết, phân tích thừa số nguyên tố, giải phương trình nghiệm nguyên Diophantine, hệ thức truy hồi Catalan.
• Cấu trúc dữ liệu nâng cao: Cây (Trees), Đồ thị có hướng (Directed Graphs), Bảng phương án 2 chiều, Con trỏ và Vùng nhớ Heap.
• Lý thuyết tối ưu hóa: Nguyên lý tối ưu Bellman trong Quy hoạch động, nguyên lý lựa chọn cục bộ tối ưu trong Tham lam (Greedy Choice Property).

Kỹ năng phát triển

• Kỹ năng phân tích thuật toán: Nhận diện giới hạn bài toán ($N, Time, Memory$) để lựa chọn cấu trúc dữ liệu tương thích; phân biệt khi nào một phương pháp quen thuộc (như Quy hoạch động) bị phá vỡ bởi giới hạn bộ nhớ.
• Kỹ năng kỹ thuật lập trình: Quản lý bộ nhớ con trỏ trong môi trường hạn chế (Segment 64KB của Turbo Pascal), sử dụng các chỉ thị biên dịch {$M}, {$A+}, hàm cấp phát new(), dispose(), Mark(), Release().
• Kỹ năng xử lý dữ liệu lớn: Quản lý chỉ số mảng gián tiếp, đọc ghi tệp tuần tự nhiều lần thay vì lưu trữ toàn bộ dữ liệu vào RAM.

---

Phương pháp giảng dạy và học tập

Tài liệu được xây dựng dựa trên phương pháp sư phạm Học tập qua giải quyết vấn đề (Problem-Based Learning - PBL) và Đối chiếu phản biện giải thuật:

                       QUY TRÌNH HỌC TẬP VÀ PHẢN BIỆN

1. Phương pháp tiếp cận sư phạm:

   • Đặt người học trước những bài toán thực tế có ràng buộc cụ thể về dữ liệu đầu vào.
   • Thay vì chỉ đưa ra lời giải đúng, ban biên tập tạp chí trực tiếp phân tích các bài làm gửi về của độc giả, chỉ ra những đường mòn tư duy sai lầm (như việc cả 5 độc giả đều dùng Quy hoạch động cho Bài 152 dẫn đến vượt giới hạn mảng, hoặc dùng Bubble Sort thay vì QuickSort trong Bài 153).

2. Cấu trúc bài tập và Case Studies:

   • Mỗi bài toán hoạt động như một case study độc lập. Đề bài mô tả chi tiết: Tên tệp nguồn (.INP), tên tệp đích (.OUT), số lượng dòng, định dạng dữ liệu ngăn cách bởi dấu cách, và các giá trị biên ($N \le 10^4, N \le 10^6$).
   • Các bài toán có tính liên kết chặt chẽ giữa toán học lý thuyết và lập trình tính toán.

3. Hướng dẫn tự học và đánh giá:

   • Bước 1: Đọc kỹ yêu cầu bài toán và xác định cấu trúc dữ liệu tối thiểu.
   • Bước 2: Viết chương trình sơ bộ và kiểm tra độ phức tạp không gian (tránh khai báo mảng tĩnh quá lớn).
   • Bước 3: Đọc phần phân tích thuật toán trong Phần II, so sánh mã nguồn cá nhân với mã nguồn chuẩn của ban biên tập.
   • Bước 4: Tinh chỉnh chương trình nhằm giảm thiểu số lượng biến trung gian và tối ưu hóa thời gian chạy.

---

Điểm nổi bật và cập nhật

1. Nguồn gốc học thuật và tính thực chiến: Toàn bộ hệ thống bài tập được tuyển chọn trực tiếp từ các kỳ thi học sinh giỏi các cấp và các đề xuất giải thuật từ cộng đồng giáo viên, học sinh chuyên Tin trên toàn quốc (như bài 195 trích từ Đề thi Học sinh giỏi Tin học Hà Nội – HAOI 2004; các đề bài của cộng tác viên Vũ Mạnh Hùng – THPT Chuyên Ngô Sỹ Liên Bắc Giang, Trần Quang Đức, Phạm Mạnh Cường, Hoàng Anh Vũ – Học viện Công nghệ Bưu chính Viễn thông...).

2. Tính phản biện và sửa đổi lối mòn giải thuật: Tài liệu nhấn mạnh việc phá vỡ các định kiến thuật toán có sẵn. Ví dụ điển hình tại bài toán Chia kẹo (Bài 152), tài liệu chỉ rõ điểm yếu cồng kềnh của phương pháp Quy hoạch động kinh điển khi kích thước dữ liệu tăng cao ($N = 10.000$) và chứng minh tính ưu việt của giải thuật tối ưu hóa cục bộ bằng phép biến đổi tráo đổi trực tiếp.

3. Kỹ thuật tối ưu hóa bộ nhớ chuyên sâu: Cung cấp các kỹ thuật kinh điển trong xử lý dữ liệu lớn trên máy tính:

   • Kỹ thuật sử dụng mảng con trỏ cấp phát động trên vùng nhớ Heap.
   • Kỹ thuật đọc tệp hai lần để truy vết kết quả trong bài toán Bố trí phòng họp (Bài 155), loại bỏ hoàn toàn việc sử dụng mảng phụ lưu vết.
   • Kỹ thuật quay vòng bộ nhớ (mảng $a1, a2$) trong các bài toán Quy hoạch động đường đi và phân phối tài nguyên.

---

Đối tượng sử dụng giáo trình

Đối tượng	Mục đích sử dụng	Yêu cầu kiến thức tiên quyết
Học sinh THPT Chuyên Tin	Luyện thi Học sinh giỏi Tỉnh/Quốc gia, chuẩn bị cho các kỳ thi Olympic Tin học	Nắm vững ngữ pháp Pascal/C++, kỹ thuật đệ quy, sắp xếp cơ bản
Sinh viên ngành CNTT / KHMT	Bổ trợ học phần Cấu trúc dữ liệu & Giải thuật, Phân tích thiết kế giải thuật	Đã học Toán rời rạc, Lập trình hướng cấu trúc, Đại số tuyến tính
Giảng viên & Giáo viên chuyên	Xây dựng ngân hàng đề thi, tài liệu tham khảo chuyên đề bồi dưỡng thuật toán	Nắm vững lý thuyết độ phức tạp giải thuật và phương pháp sư phạm tin học
Lập trình viên tự học thuật toán	Nâng cao tư duy tối ưu hóa mã nguồn, rèn luyện kỹ năng giải quyết bài toán tối ưu	Có tư duy logic toán học và khả năng đọc hiểu mã nguồn giải thuật

---

Câu hỏi thường gặp

1. Giáo trình này phù hợp nhất với trình độ nào?

Tài liệu được thiết kế chuyên biệt cho học sinh các lớp chuyên Tin học (THPT), sinh viên đại học khối ngành Công nghệ thông tin – Khoa học máy tính và các thí sinh ôn luyện kỳ thi học sinh giỏi, Olympic Tin học sinh viên.

2. Cần chuẩn bị kiến thức nền tảng gì trước khi học tài liệu này?

Người học cần nắm chắc kiến thức cơ bản về lập trình cấu trúc (kiểu mảng, xâu, con trỏ, tệp tin), kiến thức toán học rời rạc (lý thuyết đồ thị, đại số tổ hợp, đồng dư thức) và các giải thuật sắp xếp/tìm kiếm cơ bản.

3. Điểm khác biệt căn bản giữa tài liệu này với các sách thuật toán lý thuyết là gì?

Tài liệu không thuần túy trình bày định lý giải thuật mà đi thẳng vào các bài toán thực hành có cấu trúc dữ liệu cụ thể (.INP/.OUT). Đặc biệt, tài liệu phân tích trực tiếp các lỗi tư duy sai lầm, các hạn chế về bộ nhớ khi cài đặt thực tế trên máy tính mà sách lý thuyết thường bỏ qua.

4. Phương pháp tự học tài liệu này như thế nào để đạt hiệu quả cao nhất?

Người học nên tự lực giải quyết đề bài ở Phần I mà không xem trước lời giải. Trong quá trình cài đặt, cần đặc biệt lưu ý đến các ràng buộc dữ liệu lớn ($N \le 10^4, 10^6$) để thiết kế cấu trúc dữ liệu hợp lý, sau đó mới đối chiếu với mã nguồn và phần bình luận giải thuật ở Phần II.

5. Tài liệu sử dụng ngôn ngữ lập trình nào và có chuyển đổi sang ngôn ngữ khác được không?

Mã nguồn mẫu trong tài liệu được viết bằng ngôn ngữ Pascal (chuẩn Turbo Pascal / Free Pascal). Tuy nhiên, toàn bộ tư tưởng giải thuật, công thức truy hồi quy hoạch động và cấu trúc dữ liệu đều mang tính tổng quát, có thể dễ dàng chuyển dịch sang C++, Java hoặc Python.

---

Kết luận

Tập tài liệu "Bài Tập Tin Học – Tin học & Nhà trường Tập III (Bài 151 – 200)" là một tuyển tập học thuật có giá trị thực hành cao về giải thuật và cấu trúc dữ liệu. Bằng việc phân tích sâu sắc mối tương quan giữa độ phức tạp tính toán, cấu trúc dữ liệu và phương pháp quản lý bộ nhớ máy tính, tài liệu cung cấp cho người học phương pháp tiếp cận bài toán một cách khoa học, chính xác và tối ưu.

Lộ trình học tập khuyến nghị từ tài liệu: $$\text{Bài toán Logic / Số học} \longrightarrow \text{Kỹ thuật Tham lam & Sắp xếp} \longrightarrow \text{Quy hoạch động & Kỹ thuật mảng} \longrightarrow \text{Đồ thị & Hình học tính toán}$$

Trích đoạn nội dung tài liệu

TRẦN SĨ TÙNG –«— BÀI TẬP TIN HỌC Tin học & Nhà trường Tập III 151 – 200 2013 Tin hoïc & Nhaø tröôøng 1 Phần 1: ĐỀ BÀI Bài 151/2003 – Người nông dân và những quả táo Một người nông dân đến gặp đức vua và nói: ″Xin đức vua ban cho tôi 1 quả táo trong vườn Thượng uyển của ngài″. Nhà vua đồng ý. Người nông dân đi đến vườn và thấy muốn vào vườn phải lần lượt qua 3 cổng gác và ở mỗi cổng đều có một người lính canh. Người nông dân tiến đến người lính canh thứ nhất và nói: – ″Đức vua cho tôi lấy một quả táo ở trong vườn″ – ″Được, anh hái đi, nhưng khi đi ra phải đưa cho tôi một nửa số táo anh hái và thêm một quả nữa″, người lính canh trả lời.

Hai người lính canh kia cũng nói như vậy với người nông dân. Hỏi người nông dân phải hái bao nhiêu quả táo để khi ra khỏi vườn và đưa cho những người lính canh số táo đúng như họ yêu cầu, anh ta còn lại một quả? Bài 152/2003 – Chia kẹo Có N gói kẹo, gói thứ i có A[i] cái kẹo. Yêu cầu: Hãy tìm cách chia các gói kẹo này thành 2 phần sao cho độ chênh lệch giữa tổng số kẹo ở hai phần là ít nhất có thể được 0 <A[i] <1000, 2≤N≤10000 Dữ liệu vào: Cho trong file Chiakeo.inp: Một dòng duy nhất gồm các giá trị là số kẹo trong mỗi gói, các số cách nhau bởi một dấu cách (N = số gói kẹo đọc được) Dữ liệu ra: Ghi ra file Chiakeo.out – Dòng 1 lần lượt ghi 3 số: tổng số kẹo ở phần 1, phần 2 và độ chênh lệch giữa hai phần. – Dòng 2,3 là giá trị các gói kẹo ở mỗi phần được chia.

Ví dụ: Nguyễn Duy Phi Bài 153/2003 – Phân phối hàng Có N công trường cần vật liệu thi công. Công trường i cần cung cấp D[i] đơn vị hàng. Hàng được cung cấp từ hai kho A và B. Cước vận chuyển một đơn vị hàng từ kho A đến công trường i là A[i].

Cước vận chuyển một đơn vị hàng từ kho B đến công trường i là B[i]. Biết rằng kho A có R đơn vị hàng và tổng số hàng của hai kho đủ cung cấp cho N công trường. Yêu cầu: Hãy phân phối hàng từ hai kho đến các công trường sao cho tổng cước phí vận chuyển là ít nhất. Dữ liệu vào: File HANG.INP có cấu trúc như sau: Dòng 1: Ghi 2 số N, R (N≤ 10000) Dòng 2: Ghi N số D[1], D[2], …,D[N].

Dòng 3: Ghi N số A[1], A[2], …,A[N]. Dòng 4: Ghi N số B[1], B[2], …,B[N]. Dữ liệu ra: File HANG.OUT có cấu trúc như sau: Dòng 1: Ghi một số nguyên dương là tổng chi phí vận chuyển ít nhất. Dòng 2: Ghi N số nguyên không âm tương ứng số đơn vị hàng mà kho A cung cấp cho các 2 Tin hoïc & Nhaø tröôøng công trường 1,2…N.

Dòng 3: Ghi N số nguyên không âm tương ứng số đơn vị hàng mà kho B cung cấp cho các công trường 1,2…N. Ví dụ: Trần Đức Thiện − Xóm Chùa − Xã Hương Lạc − Huyện Lạng Giang − Bắc Giang. Bài 154/2003 – Tuổi cha và con Hai người đàn ông gặp nhau trên đường, một người hỏi ″Cậu đi đâu đấy″? − Mình đến trường mẫu giáo đón con, người kia trả lời − Cậu có mấy con và các con cậu mấy tuổi? − Mình có hai đứa. Tuổi của mình gấp 4 lần tuổi đứa lớn và gấp 7 lần tuổi đứa nhỏ, người bạn trả lời.

Bạn hãy cho biết người thứ hai và các con anh ta bao nhiêu tuổi? Bài 155/2003 – Bố trí phòng họp Có N cuộc họp đánh số từ 1 đến N đăng ký làm việc tại một phòng hội thảo.