[UVa #11044] Searching for Messy

문제 설명

문제 링크
$n * m$ 크기의 호수가 있을 때 한 번에 $3 * 3$크기의 지역을 탐색 가능한 sonar beam으로 탐색할 때 전체 호수를 탐색하려면 몇 개의 sonar beam이 필요한가.
단, 호수의 제일 가에는 탐색할 필요가 없다.(nessy가 숨어있지 못한다.)

알고리즘

원래 사이드를 탐색해야한다면
$((n+2)/3)*((m+2)/3)$
개의 sonar beam이 필요하나 사이드는 탐색할 필요가 없으므로
$(n/3)*(m/3)$
개의 sonar beam이 필요하다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 1000000000

int t;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> t;

    for (int tc = 1; tc <= t; ++tc) {
        int n, m;
        cin >> n >> m;

        cout << (n / 3) * (m / 3) << '\n';
    }
}