Các thuật toán (Phần 2)
101. GHI ĐĨA 3
102. easy ĐƯỜNG ĐI THOÁT MÊ CUNG danh cho nguoi moi bat dau hoc Tin hoc 4
103. so CHU TRÌNH CƠ BẢN easy – 10test 5
104. Euler CỘT CÂY SỐ circuit – 10test 6
105. LỊCH SỬA CHỮA Ô TÔ meo nho – 10test 7
106. KHỚP VÀ CẦUalg co ban 8
107. use only HÀNG ĐỢI VỚI ĐỘ ƯU TIÊN heap 9
108. dijkstra HỘI CHỢ normal 10test 10
109. SERIE A? easy 11
110. SỐ HIỆU VÀ GIÁ TRỊnghi ki se ra phan sau 12
111. kho o doan PHÉP COin ket qua 13
112. CHỮA NGOẶC 14
113. up to now I still MÃ HOÁ BURROWS WHEELER fell it’s hard 15
114. kruskal MẠNG RÚT GỌN normal 16
115. tt DÃY NGOẶCquen thuoc 17
116. QHD LẮP RÁP MÁY TÍNH n3 18
117. ĐƯỜNG MỘT CHIỀU 19
118. PHỦ 20
119. THÁP GẠCH 21
120. cap ghep binh thuong THU THUẾ cung co the an duoc 8/10 test 22
121. PHÂN CÔNG 23
122. XÂU CON 24
123. LĂN XÚC XẮC 25
124. VỆ SĨ 27
125. GIAO LƯU 28
126. GIAO LƯU 29
127. ĐẠI DIỆN 30
128. HỘI CHỢ 31
129. LỊCH HỌC 32
130. MÃ LIÊN HOÀN 33
131. TUYỂN NHÂN CÔNG 34
132. ĐƯỜNG TRÒN 35
133. ĐOẠN 0 36
134. HỌC BỔNG 37
135. ĐOẠN DƯƠNG 38
136. TÍN HIỆU GIAO THÔNG 39
137. PHỦ 40
138. DI CHUYỂN RÔ-BỐT 41
139. TRẠM NGHỈ 42
140. CHIA CÂN BẰNG 44
141. LĂN XÚC XẮC 45
142. CHUYỂN HÀNG 46
143. GHÉT NHAU NÉM ĐÁ. 47
144. NỐI DÂY 48
145. MY LAST INVENTION 49
146. CÂY KHUNG NHỎ NHẤT 50
147. MẠNG MÁY TÍNH 51
148. DẴY ĐƠN ĐIỆU TĂNG DÀI NHẤT 52
149. LUỒNG CỰC ĐẠI TRÊN MẠNG 53
150. BỘ GHÉP CỰC ĐẠI 54
151. BỘ GHÉP ĐẦY ĐỦ TRỌNG SỐ CỰC TIỂU 55
152. TUYỂN NHÂN CÔNG 56
153. DÀN ĐÈN 57


máy xi và máy xi+1 có dây cáp mạng nối chúng) Hãy nối thêm một số ít nhất các dây cáp mạng sao cho hai máy bất kỳ trong phòng máy có thể truyền tin được cho nhau. Dữ liệu: Vào từ file văn bản NET.INP Dòng 1: Chứa hai số m, n (1 £ m, n £ 100); Các dòng tiếp theo, mỗi dòng chứa thông tin về một đoạn cáp đã có sẵn: gồm 4 số x1, y1, x2, y2 thể hiệu cho cáp mạng nối hai máy ở toạ độ (x1, y1) và (x2, y2). (|x1 - x2| + |y1-y2| = 1). Kết quả: Ghi ra file văn bản NET.OUT Dòng 1: Ghi số cáp mạng cần nối thêm (c) c dòng tiếp theo, mỗi dòng ghi 4 số u1, v1, u2, v2 cho biết cần thêm cáp nối giữa hai máy ở toạ độ (u1, v1) và (u2, v2) Các số trên một dòng của Input/Output file cách nhau ít nhất một dấu cách. Ví dụ: NET.INP NET.OUT 2 3 0 0 0 1 1 0 2 0 1 0 1 1 2 0 2 1 0 1 1 1 1 1 2 1 1 2 2 2 0 3 1 3 4 0 2 1 2 1 2 1 3 1 1 1 2 1 3 2 3 Giới hạn thời gian: 1 giây 148. DẴY ĐƠN ĐIỆU TĂNG DÀI NHẤT Cho dãy số nguyên dương a = (a1, a2, ..., an) (1 £ n £ 10000; 1 £ ai £ 10000) Hãy tìm dãy chỉ số dài nhất i1, i2, ..., ik thoả mãn: 1 £ i1 < i2 < ... < ik £ n ai1 < ai2 < ... < aik Dữ liệu: Vào từ file văn bản INCSEQ.INP Dòng 1: Chứa số n Dòng 2: Chứa n số a1, a2, ..., an Kết quả: Ghi ra file văn bản INCSEQ.OUT Dòng 1: Ghi số k Dòng 2: Ghi k số i1, i2, ..., ik Các số trên một dòng của Input/Output file cách nhau ít nhất một dấu cách Ví dụ: INCSEQ.INP INCSEQ.OUT 8 1 2 8 9 5 6 7 9 6 1 2 5 6 7 8 Giới hạn thời gian: 1 giây 149. LUỒNG CỰC ĐẠI TRÊN MẠNG Cho một mạng G = (V, E) là đồ thị có hướng với n điểm và m cung, 1 là điểm phát và n là điểm thu. Từ 1 chỉ có cung đi ra và từ n chỉ có cung đi vào. Mỗi cung (u, v) của mạng được gán một số nguyên dương c(u, v) là khả năng thông qua của cung đó. Một luồng cực đại trên mạng là một cách gán cho mỗi cung (u, v) một số nguyên f(u, v) thoả mãn: i) f(u, v) £ c(u, v) ("(u, v)ÎE) ii) ("vÎV) iii)Giá trị luồng = là lớn nhất có thể. Hãy tìm luồng cực đại trên mạng G Dữ liệu: Vào từ file văn bản MAXFLOW.INP Dòng 1: Chứa số đỉnh n và số cung m của đồ thị G (2 £ n £ 100) m dòng tiếp theo, mỗi dòng chứa ba số u, v, c(u, v) thể hiện cho một cung (u, v) và khả năng thông qua của cung đó là c(u, v) Kết quả: Ghi ra file văn bản MAXFLOW.OUT Dòng 1: Ghi giá trị luồng tìm được Các dòng tiếp theo, mỗi dòng chứa ba số x, y, f(x, y) thể hiện (x, y) là một cung và luồng gán cho cung (x, y) là f(x, y) (Những cung nào không có luồng (f(x, y) = 0) không cần phải ghi vào Output file). Các số trên một dòng của Input / Output file ghi cách nhau ít nhất một dấu cách. Ví dụ: MAXFLOW.INP 6 8 1 2 5 1 3 5 2 4 6 2 5 3 3 4 3 3 5 1 4 6 6 5 6 6 MAXFLOW.OUT 9 1 2 5 1 3 4 2 4 3 2 5 2 3 4 3 3 5 1 4 6 6 5 6 3 150. BỘ GHÉP CỰC ĐẠI Cho đồ thị hai phía G = (XÈY, E); Các đỉnh của X ký hiệu là x1, x2, ..., xm, các đỉnh của Y ký hiệu là y1, y2, ..., yn. Một bộ ghép trên G là một tập các cạnh ÎE đôi một không có đỉnh chung. Yêu cầu: Hãy tìm bộ ghép cực đại (có nhiều cạnh nhất) trên G. Dữ liệu: Vào từ file văn bản MATCH.INP Dòng 1: Chứa hai số m, n (1 £ m, n £ 300) Các dòng tiếp, mỗi dòng chứa hai số nguyên dương i, j cho biết thông tin về một cạnh (xi, yj)ÎE. Kết quả: Ghi ra file văn bản MATCH.OUT Dòng 1: Ghi số cạnh trong bộ ghép cực đại tìm được (K). K dòng tiếp theo, mỗi dòng ghi thông tin về một cạnh được chọn vào bộ ghép cực đại: Gồm 2 số u, v thể hiện cho cạnh nối (xu, yv). Các số trên một dòng của Input / Output file cách nhau ít nhất một dấu cách. Ví dụ: MATCH.INP 4 5 1 1 1 4 2 1 2 2 2 4 3 2 3 3 4 2 4 3 MATCH.OUT 4 1 1 2 4 3 3 4 2 151. BỘ GHÉP ĐẦY ĐỦ TRỌNG SỐ CỰC TIỂU Cho đồ thị hai phía G = (XÈY, E); Các đỉnh của X ký hiệu là x1, x2, ..., xn, các đỉnh của Y ký hiệu là y1, y2, ..., yn. Mỗi cạnh của G được gán một trọng số không âm. Một bộ ghép đầy đủ trên G là một tập n cạnh ÎE đôi một không có đỉnh chung. Trọng số của bộ ghép là tổng trọng số các cạnh nằm trong bộ ghép. Yêu cầu: Hãy tìm bộ ghép đầy đủ có trọng số cực tiểu của G Dữ liệu: Vào từ file văn bản MATCH.INP Dòng 1: Chứa số n (1 £ n £ 200) Các dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, c cho biết có một cạnh (xi, yj) và trọng số cạnh đó là c (0 £ c £ 200). Kết quả: Ghi ra file văn bản MATCH.OUT Dòng 1: Ghi trọng số bộ ghép tìm được n dòng tiếp, mỗi dòng ghi hai số (u, v) tượng trưng cho một cạnh (xu, yv) được chọn vào bộ ghép. Các số trên một dòng của Input / Output file cách nhau ít nhất một dấu cách. Ràng buộc: Luôn tồn tại ít nhất một bộ ghép đầy đủ trên G. Ví dụ: MATCH.INP 4 1 1 0 1 2 0 2 1 0 2 4 2 3 2 1 3 3 0 4 3 0 4 4 9 MATCH.OUT 3 1 1 2 4 3 2 4 3 152. TUYỂN NHÂN CÔNG Có n công việc cần thực hiện và r loại thợ. Thợ loại i có thể không làm được việc j hoặc làm được với chi phí là cij. Một phép phân công là một cách chọn ra n thợ và giao cho mỗi thợ làm đúng một việc sao cho có thể thực hiện tất cả n công việc. Giả sử đã có sẵn m thợ hãy tìm cách tuyển thêm một số ít nhất thợ để có thể thực hiện phép phân công. Nếu có nhiều cách tuyển thoả mãn yêu cầu trên thì chỉ ra cách tuyển có tổng chi phí thực hiện các công việc (trên phép phân công tối ưu) là cực tiểu. Dữ liệu: Vào từ file văn bản ASSIGN.INP Dòng 1: Chứa ba số m, n, r (1 £ m, n, r £ 300) Dòng 2: Chứa m số, số thứ k là loại của thợ thứ k trong m thợ đã có Các dòng tiếp theo, mỗi dòng ghi ba số i, j, cịj cho biết loại thợ i có thể làm được việc j với chi phí cij (0 £ cij £ 10000) Các số trên một dòng của Input file cách nhau ít nhất một dấu cách Kết quả: Ghi ra file văn bản ASSIGN.OUT Dòng 1: Ghi số thợ cần thêm và chi phí phép phân công tối ưu n dòng tiếp theo, dòng thứ i ghi loại thợ được giao thực hiện việc i Ràng buộc: Mỗi việc có ít nhất một loại thợ có thể thực hiện Ví dụ: ASSIGN.INP ASSIGN.OUT ASSIGN.INP ASSIGN.OUT 10 4 6 1 3 5 5 5 5 5 5 5 5 1 1 10 1 2 10 1 3 10 3 1 10 3 2 10 3 3 10 2 2 9 2 1 8 4 2 6 4 3 5 6 4 0 2 25 1 3 4 6 1 2 3 1 1 1 10 1 2 30 3 1 1 3 2 25 2 2 40 1 31 3 1 153. DÀN ĐÈN Cho một bảng vuông kích thước mxn được chia thành lưới ô vuông đơn vị, tại mỗi ô của bảng có một trong các ký hiệu: ".": Ô trống "+": Ô có chứa một đèn chưa bật sáng "*": Ô có chứa một đèn đã bật sáng Hai đèn đã bật sáng bất kỳ không nằm cùng hàng hoặc cùng cột. Yêu cầu: Hãy bật sáng thêm một số nhiều nhất các đèn sao cho: số đèn sáng trên mỗi hàng cũng như trên mỗi cột của bảng tối đa là 1. Dữ liệu: Vào từ file văn bản GRID.INP Dòng 1: Chứa hai số m, n (1 £ m, n £ 200) cách nhau ít nhất một dấu cách m dòng tiếp theo, dòng thứ i chứa n ký tự liên tiếp, ký tự thứ j là ký hiệu ô (i, j) của bảng Kết quả: Ghi ra file văn bản GRID.OUT Dòng 1: Ghi số đèn có thể bật thêm m dòng tiếp theo, dòng thứ i ghi n ký tự liên tiếp, ký tự thứ j là ký hiệu ô (i, j) của bảng sau khi đã bật sáng thêm các đèn Ví dụ: GRID.INP GRID.OUT 4 5 +..*. ++.+. .++.. .++.. 3 +..*. *+.+. .*+.. .+*.. 154. CO VÒNGTHEM Cho N số nguyên A1, A2, ..., AN. Các số được bố trí theo thứ tự theo chiều kim đồng hồ trên một vòng tròn. Cho hai phép biến đổi: R(i) - Phép co phải: Thay Ai bằng Ai - Ai+1 và xoá Ai+1 L(i) - Phép co trái: Thay Ai bằng Ai - Ai-1 và xoá Ai-1 Lưu ý: Ai-1 và Ai + 1 ở trên được hiểu là các phần tử đứng liền trước, liền sau Ai trong vòng tròn theo chiều kim đồng hồ (1 £ i £ N). VD R(N) là phép thay hai số AN và A1 bằng AN - A1 Sau mỗi bước co, các phần tử được đánh số lại theo chiều kim đồng hồ bắt đầu từ phần tử có chỉ số nhỏ nhất còn lại được đánh số 1. Sau N - 1 lần co trên, vòng tròn chỉ còn một số nguyên R. Hãy xác định có tồn tại cách sử dụng thứ tự hai phép co trên để từ vòng tròn ban đầu chỉ còn lại số R hay không. Nếu có thì chỉ ra một cách biến đổi. Dữ liệu vào đặt trong file văn bản PRESS.INP Dòng đầu: 2 số nguyên N, R theo đúng thứ tự cách nhau 1 dấu trống ( 1 £ N £ 100), (-10000 £ R £ 10000). Dòng thứ i trong số N dòng tiếp theo: chứa số nguyên Ai ( -120 £ Ai £ 120). Kết quả ra đặt trong file văn bản PRESS.OUT Chứa thông báo NO SOLUTION nếu vô nghiệm, trong trường hợp có nghiệm thì mỗi dòng xác định một bước biến đổi: Đầu dònglà một trong hai ký tự {L, R} tiếp đó là dấu trống, sau đó đến vị trí i mà tại bước đó ta thực hiện phép co phải R(i) hay co trái L(i). Ví dụ: PRESS.INP PRESS.OUT 5 6 1 6 8 12 5 R 4 L 2 R 3 R 1 1 6 8 12 5 1 6 8 7 5 8 7 8 2 6 155.CẦU TÀUTHEM Một cảng biển có M cầu tàu. Tại một thời điểm, mỗi cầu tàu chỉ có thể tiếp nhận không quá 1 tàu. Theo kế hoạch, trong khoảng từ thời điểm P tới hết thời điểm Q giờ (0 £ P< Q £ 72) có N tàu sẽ cập bến. Tàu thứ i có lịch trình đậu ở cảng bắt đầu từ đầu thời điểm Ai đến hết thời điểm Bi. Tàu đã vào cầu tàu nào thì sẽ đậu ở đó trong suốt thời gian nằm cảng. Hãy lập chương trình kiểm tra xem cần ít nhất bao nhiêu cầu cảng trống để có thể phục vụ các tàu theo đúng lịch của mình. Nếu số cầu tàu không đủ thì có thể đề xuất thay đổi thời điểm Ai của một số tàu (giữ nguyên thời gian cần đậu và thời điểm rời cảng không muộn hơn Q) để đảm bảo phục vụ hết các tàu. Tuy vậy, đối với các tàu này cần phải trả thêm phụ phí bao gồm 2 phần, phần cố định và phần tỷ lệ với lượng thời gian chênh lệch giữa hai thời điểm đầu cũ và mới. Phần cố định là rất lớn so với phần tỷ lệ thời gian. Dữ liệu vào đặt trong file văn bản SEAPORT.INP Dòng đầu: ghi 4 số nguyên P, Q, M, N (0 < N £ 100) N dòng sau: Mỗi dòng ghi 2 số nguyên Ai, Bi Các số trên 1 dòng ghi cách nhau 1 dấu trống. Kết quả: Ghi ra file văn bản SEAPORT.OUT Dòng đầu tiên: Số cầu tàu tối thiểu cần có để phục vụ các tàu theo đúng lịch trình. Dòng thứ 2 ghi số 0 nếu không cần điều chỉnh lịch, chứa số -1 nếu không thể điều chỉnh lịch để có thể phục vụ tất cả các tàu và chứa số K > 0, nếu cần và có thể điều chỉnh được các lịch trong đó K là số tàu cần điều chỉnh lịch. K dòng tiếp theo: mỗi dòng 3 số nguyên i, Ai, và Ai mới ứng với một tàu cần điều chỉnh lịch. Các số trên 1 dòng cách nhau ít nhất 1 dấu cách. Ví dụ: SEAPORT.INP SEAPORT.OUT 0 12 3 5 8 12 5 9 2 6 4 8 1 7 4 1 2 5 7
File đính kèm:
cac_thuat_toan_phan_2.doc