trang chủ / đề bài / icpc23_mn_d

Phát hiện nguy hiểm

Đề bài

Mô tả

Một vùng đất được mô tả bởi lưới ô vuông kích thước n×n. Các hàng được đánh số từ 1 đến n từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái sang phải. Ô ở hàng i, cột j gọi là ô (i,j). Qua khảo sát, mỗi ô có một sức chịu tải nhất định: ô (i,j) có sức chịu tải là số nguyên dương aij.

Một robot xuất phát từ ô (1,1) và cần đến ô (n,n), mỗi bước di chuyển sang một ô kề cạnh. Giả sử robot có trọng lượng G; khi đó một ô có sức chịu tải nhỏ hơn G được coi là nguy hiểm. Mọi ô trên đường đi đều được tính, kể cả ô xuất phát (1,1) và ô đích (n,n).

Nhiệm vụ của bạn là giải một trong hai bài toán sau:

  1. Cho trọng lượng G của robot, tìm đường đi sao cho số ô nguy hiểm mà robot đi qua là ít nhất. In ra số ô nguy hiểm trên đường đi đó.
  2. Với lưới đã cho, tìm trọng lượng lớn nhất của robot sao cho nó có thể đến ô (n,n) mà không đi qua ô nguy hiểm nào.

Dữ liệu vào

Dòng đầu tiên chứa số 1 hoặc 2: bài toán cần giải.

Nếu dòng đầu tiên là 1, dòng thứ hai chứa hai số nguyên n và G. Nếu dòng đầu tiên là 2, dòng thứ hai chứa một số nguyên n.

Dòng thứ i trong n dòng tiếp theo chứa n số nguyên ai1,ai2,…,ain: hàng thứ i của lưới.

Dữ liệu ra

In ra một số nguyên là kết quả của bài toán tương ứng.

Ràng buộc

  • 1≤n≤500
  • 1≤G≤109
  • 1≤aij≤104

Ví dụ

Input Output Giải thích
1
5 6
7 1 3 4 6
6 2 1 7 5
2 6 7 2 3
4 2 1 1 7
9 1 6 1 6
3 Đường đi qua các ô có sức chịu tải 7,6,2,6,7,2,3,7,6 chỉ có 3 ô nhỏ hơn 6 (các ô 2, 2, 3).
2
5
7 1 3 4 6
6 2 1 7 5
2 6 7 2 3
4 2 1 1 7
9 1 6 1 6
2 Từ ô (1,1) và ô (2,1), mọi hướng đi tiếp đều phải qua một ô có sức chịu tải 1 hoặc 2; đường đi ở ví dụ trên có mọi ô ≥2.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0