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:
- 138. DI CHUYỂN RÔ-BỐT
- 139. TRẠM NGHỈ
137. PHỦCho một đồ thị vô hướng G = (V, E) có n đỉnh và m cạnh, không có đỉnh cô lập Hãy chọn ra một tập ít nhất các cạnh để tất cả các đỉnh của đồ thị đều là đầu mút của ít nhất một cạnh trong tập đã chọn Dữ liệu: Vào từ file văn bản COVER.INP
Kết quả: Ghi ra file văn bản COVER.OUT
Ví dụ:
138. DI CHUYỂN RÔ-BỐTCho một đồ thị có hướng G gồm n đỉnh và m cung, hai con Rô-bốt đứng tại hai đỉnh nào đó. Yêu cầu: Chuyển nhanh nhất hai con Rô-bốt đến gặp nhau tại một đỉnh của đồ thị, biết rằng cả hai con Rô-bốt chỉ được chạy theo các cung định hướng và không được dừng lại cho tới lúc gặp nhau tại một đỉnh nào đó. Thời gian Rô-bốt đi qua một cung bất kỳ luôn là 1 đơn vị thời gian Dữ liệu: Vào từ file văn bản RMOVE.INP
Kết quả: Ghi ra file văn bản RMOVE.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 có phương án thực hiện yêu cầu trên Ví dụ:
139. TRẠM NGHỈMột toán kỵ sĩ bỏ ngựa đi thám hiểm một khu rừng và đến khi trời tối, họ muốn đi về những trạm nghỉ. Rất may là các kỵ sĩ đều có bản đồ khu rừng trong tay, nhờ đó có thể xác định chính xác vị trí của họ, các trạm nghỉ, các khu vực có thú dữ và tất nhiên cả vị trí của các con ngựa (nơi họ đã bỏ lại). Mỗi kỵ sĩ sẽ phải chọn cho mình một con ngựa, một trạm nghỉ và dùng còi siêu âm gọi con ngựa đó về trạm nghỉ đã chọn. Mỗi trạm nghỉ chỉ đủ chỗ cho một kỵ sĩ và một con ngựa. Giả sử rằng có m trạm nghỉ, n kỵ sĩ, n con ngựa và bạn là một trong số những kỵ sĩ đó. Hãy vạch ra hành trình cho các kỵ sĩ và các con ngựa để thời gian tính từ lúc bắt đầu cho tới khi tất cả các con ngựa và các kỵ sĩ về tới trạm nghỉ tương ứng là nhỏ nhất. Bản đồ khu rừng được mã hoá bằng một lưới ô vuông đơn vị kích thước pxq. Trên mỗi ô ghi một trong 5 ký hiệu:
Với 1 đơn vị thời gian, mỗi kỵ sĩ và mỗi con ngựa có thể thực hiện một bước đi. Nhìn trên bản đồ, mỗi bước đi của một kỵ sĩ là một phép di chuyển từ ô đang đứng sang một trong các ô kề cạnh, bước đi này được mã hoá bằng một trong 4 ký hiệu {E, W, S, N}. Mỗi bước đi của một con ngựa là một phép di chuyển như một nước đi của quân mã theo luật cờ, bước đi này được mã hoá bằng một trong 8 ký hiệu {1, 2, 3, 4, 5, 6, 7, 8}. Các kỵ sĩ cũng như các con ngựa không được đi tới ô có thú dữ hay đi ra ngoài bản đồ. Các ký hiệu tương ứng với các hướng đi được chỉ ra trong hình dưới đây:
Dữ liệu: Vào từ file văn bản HORSEMAN.INP
Kết quả: Ghi ra file văn bản HORSEMAN.OUT
Ràng buộc:
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:
|
