Giả sử có một sàn được chia thành lưới có n hàng và m cột. Sàn này cần được chiếu sáng bằng đèn. Một đèn, nếu đặt ở ranh giới của hai ô, có thể chiếu sáng hai ô. Nếu đèn đặt ở ranh giới dọc, nó chiếu sáng ô bên trái và bên phải; nếu đặt ở ranh giới ngang, nó chiếu sáng ô phía trước và phía sau. Cho n và m, hãy tìm số đèn tối thiểu cần thiết để chiếu sáng toàn bộ sàn.
Ví dụ, nếu đầu vào là n = 5, m = 3, thì đầu ra sẽ là 8.
Các bước thực hiện
Để giải quyết bài toán này, chúng ta thực hiện theo các bước sau:
res := (n * m + 1) / 2 return res
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; #define N 100 int solve(int n, int m) { int res = (n * m + 1) / 2; return res; } int main() { int n = 5, m = 3; cout<< solve(n, m); return 0; }Đầu vào
5, 3
Đầu ra
8