Easy102. ĐƯỜng đi thoát mê cung danh cho nguoi moi bat dau hoc Tin hoc 4
tải về 438.29 Kb.
|
- Điều hướng trang này:
- 149. LUỒNG CỰC ĐẠI TRÊN MẠNG
- 150. BỘ GHÉP CỰC ĐẠI
- 151. BỘ GHÉP ĐẦY ĐỦ TRỌNG SỐ CỰC TIỂU
- 152. TUYỂN NHÂN CÔNG
- 153. DÀN ĐÈN
148. DẴY ĐƠN ĐIỆU TĂNG DÀI NHẤTCho 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:
Dữ liệu: Vào từ file văn bản INCSEQ.INP
Kết quả: Ghi ra file văn bản INCSEQ.OUT
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ụ:
Giới hạn thời gian: 1 giây 149. LUỒNG CỰC ĐẠI TRÊN MẠNGCho 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) iii)Giá trị luồng =
Kết quả: Ghi ra file văn bản MAXFLOW.OUT
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ụ:
150. BỘ GHÉP CỰC ĐẠICho đồ thị hai phía G = (XY, 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
Kết quả: Ghi ra file văn bản MATCH.OUT
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ụ:
151. BỘ GHÉP ĐẦY ĐỦ TRỌNG SỐ CỰC TIỂUCho đồ thị hai phía G = (XY, 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
Kết quả: Ghi ra file văn bản MATCH.OUT
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ụ:
152. TUYỂN NHÂN CÔNGCó 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
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
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ụ:
153. DÀN ĐÈNCho 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:
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
Kết quả: Ghi ra file văn bản GRID.OUT
Ví dụ:
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:
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).
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ụ:
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ụ:
Каталог: Portals Portals -> Phan Chau Trinh High School one period test no 2 Name: English : 11- time : 45 minutes Class: 11/ Code: 211 Chọn từ hoặc cụm từ thích hợp A, B, C, d để điền vào chỗ trống trong đoạn văn sau Portals -> PHẦn I: thông tin cơ BẢn về ĐẠi hàn dân quốc và quan hệ việt nam-hàn quốc I- các vấN ĐỀ chung Portals -> Năng suất lao động trong nông nghiệp: Vấn đề và giải pháp Giới thiệu Portals -> LẤy ngưỜi học làm trung tâM Portals -> BÀi tậP Ôn lưu huỳnh hợp chất lưu huỳnh khí sunfurơ so Portals -> TỜ trình về việc ban hành mức thu phí tham gia đấu giá quyền sử dụng đất Portals -> CỘng hòa xã HỘi chủ nghĩa việt nam độc lập – Tự do – Hạnh phúc Portals -> GIẤY Ủy quyền tham dự Đại hội đồng Cổ đông thường niên năm 2016 tải về 438.29 Kb. Chia sẻ với bạn bè của bạn:
|
(vV)
là lớn nhất có thể.
