Bài 1. ConGian
Link cham: 8.R.congian.dt | uCode.vn - Lập trình tương lai của bạn
. Một lưới NxN ô vuông gồm có N hàng và N cột. Các hàng được đánh số từ 1 đến N (từ trên xuống) và các cột đánh số từ 1 đến N( từ trái qua). Một con gián xuất phát từ ô (1,1) và muốn bò đến ô có đặt thức ăn là (X , Y). Người ta đặt các chướng ngại vật để gián không được đi qua ở các ô đánh số 1; các ô không đặt chướng ngại vật được đánh số 0 và gián có thể đi qua các ô này. Từ ô đang đứng, gián chỉ có thể di chuyển đến 3 ô kề cạnh: một ô bên dưới và hai ô ở hai bên. Gián không thể bò ra ngoài đường biên của lưới.
Yêu cầu: Tìm đường đi ngắn nhất của gián.
Dữ liệu vào: file CONGIAN.INP gồm:
- Dòng đầu ghi số 3 số nguyên dương: N, X, Y (N£3000; X £N; Y £N ).
- N dòng tiếp theo mỗi dòng ghi N số nguyên 0 hoặc 1, mỗi số cách nhau một khoảng trắng.
(Riêng số đầu tiên của dòng thứ nhất và số thứ Y của dòng X ghi số 0).
Dữ liệu ra: file CONGIAN.OUT gồm:
- Một số nguyên dương là số các ô mà gián đi qua ( kể cả ô xuất phát và ô đích). Trong trường hợp vô nghiệm phải in ra số 0.
| CONGIAN.INP | CONGIAN.OUT |
|---|---|
| 5 3 4 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | 6 |
Bài 2. Bảo vệ nông trang
Link cham: 2.Bai2.dt | uCode.vn - Lập trình tương lai của bạn
Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân HP muốn đặt người canh gác trên các ngọn đồi này.
Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt 1 người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm N (1 < N <= 1000) hàng và M (1 < M <= 1000) cột. Mỗi phần tử của ma trận là độ cao Hij so với mặt nước biển (0 <= Hij <= 10000) của ô (i, j). Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ. Đỉnh đồi là 1 hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ X không quá 1 và chênh lệch tọa độ Y không quá 1.
Dữ liệu vào từ file Bai2.inp:
- Dòng thứ nhất chứa hai số nguyên M và N.
- M dòng tiếp theo là ma trận thể hiện bản đồ nông trại.
Kết quả ghi ra file Bai2.out:
- Chứa một số nguyên duy nhất là số lượng đỉnh đồi.
| Bai2.inp | Bai2.out |
|---|---|
| 8 7 4 3 2 2 1 0 1 3 3 3 2 1 0 1 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 2 2 1 1 0 0 1 1 1 2 1 0 | 3 |
Ví dụ:
Ràng buộc:
- Có 30% số test ứng với 30% số điểm của bài có 1<M,N<=100.
- Có 30% số test ứng với 30% số điểm của bài có 100<M,N<=500.
- Có 40% số test ứng với 40% số điểm của bài có 500<M,N<=1000.
Bài 3. Kinh doanh
Link cham: 6.Kinhdoanh.dt | uCode.vn - Lập trình tương lai của bạn
Nam từ nhỏ đã tỏ ra là một cậu bé rất có khả năng làm kinh doanh. Ước mơ lớn nhất của cậu là có thể xây dựng được một nhà máy chế biến nông sản vừa để kinh doanh, vừa để phục vụ cho mọi người trong vùng quê của mình. Quê Nam có tổng số n ngôi làng, được đánh số từ 1, 2, ..., n. Hai ngôi làng i và j (1≤ i, j ≤ n; i ≠ j) có thể có nhiều con đường đi hai chiều nối với nhau. Với số tiền ban đầu mà Nam có, Nam quyết định thực hiện hai việc sau:
- Mở một con đường nối trực tiếp giữa hai ngôi làng bất kỳ trong n ngôi làng trên.
- Xây dựng một nhà máy chế biến nông sản trên một ngôi làng nào đó trong n ngôi làng trên.
Yêu cầu: Hãy cho biết sản phẩm của nhà máy mà Nam xây dựng có thể bán nhiều nhất cho bao nhiêu ngôi làng. Biết rằng ngôi làng mà Nam xây dựng nhà máy và những ngôi làng có đường đi đến ngôi làng mà Nam xây dựng nhà máy đều có thể mua hàng của Nam.
Dữ liệu vào: Từ tệp văn bản KINHDOANH.INP:
- Dòng 1 chứa hai số nguyên dương n và m (1 ≤ n ≤ 10000; 0 ≤ m ≤ 10000), n là số ngôi làng của quê Nam, m là số đường nối trực tiếp giữa hai ngôi làng với nhau;
- M dòng sau mỗi dòng chứa hai số nguyên dương i và j (1 ≤ i, j ≤ n, i ≠ j) thể hiện ngôi làng i và j có con đường hai chiều.
Kết quả: Ghi vào tệp KINHDOANH.OUT gồm một số nguyên dương duy nhất là số ngôi làng lớn nhất có thể mua được sản phẩm của Nam.
Ví dụ:
| KINHDOANH.INP | KINHDOANH.OUT | KINHDOANH.INP | KINHDOANH.OUT | |||
| 10 1 1 2 | 3 | 5 2 1 4 2 3 | 4 |
Bài 4. Ketxe
Link cham: 9.R.ketxe.dt | uCode.vn - Lập trình tương lai của bạn
Sống trong một thành phố lớn có mật độ dân số cao và giao thông phức tạp, ông Bình rất lo về nạn kẹt xe ảnh hưởng đến cuộc sống của mình. Mỗi sáng thức dậy công việc đầu tiên của ông Bình là nghe bản tin giao thông của thành phố. Ông Bình rất lo là con đường quen thuộc hàng ngày đi đến cơ quan bị kẹt xe thì ông không biết phải chọn con đường nào để thay thế sao cho ông có thể đến cơ quan sớm nhất có thể.
Bản đồ thành phố là gồm có N nút giao thông và M con đường hai chiều nối các nút giao thông này. Độ dài của mỗi con đường là một số nguyên dương. Nhà ông Binh ở nút giao thông 1, cơ quan ông bình ở nút giao thông N. Để thuận tiện cho việc đi lại, ông Bình đang tìm hiểu các con đường ngắn nhất dẫn từ nhà ông Bình đến cơ quan. Bạn hãy giúp ông Bình thực hiện công việc kho khăn này.
Input:
Dòng thứ nhất ghi hai số nguyên N và M (1 ≤ N ≤ 5000, 1 ≤ M ≤ 20000)M dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương U, V, L ( con đường nối U đến V với độ dài L, L ≤ 32000).
Output: Ghi hai số là độ dài đường đi ngắn nhấn và số lượng đường đi ngắn nhất.
Subtask 1( 2 điểm): n ≤ 20
Subtask 2 (2 điểm): n ≤ 100, m ≤ 1000
Subtask 3 (3 điểm): n ≤ 5000, m ≤ 20000
Ví dụ:
| Ketxe.inp | Ketxe.out |
|---|---|
| 3 3 1 2 3 1 3 4 2 3 1 | 4 2 |



Bình luận