URI (BEECROWD) - 1428 - Procurando Nessy - Ad-Hoc - C e C++

Nesse post eu trago a solução do problema "Procurando Nessy"! Esse foi bem fácil. É um problema da categoria ad-hoc no Beecrowd. Veja abaixo a minha resposta!

Plataforma: URI (BEECROWD)

Problema: 1428

Enunciado:

O mostro do lago Ness é um animal não-identificado misterioso que, dizem, habita o Lago Ness, um grande lago localizado na cidade de Inverness, no norte da Escócia. Nessie é geralmente categorizado como um tipo de mostro de lagos.

Tradução livre de trecho de https://en.wikipedia.org/wiki/Loch_Ness_Monster.

Em julho de 2003, a rede BBC fez uma grande investigação sobre o Lago Ness, usando 600 sonares separados. Nenhum vestígio de nenhum "mostro marítimo" (isto é, um grande animal, conhecido ou desconhecido) foi encontrado no lago. A equipe da BCC concluiu que Nessie não existe. Agora, nós queremos repetir este experimento.

Dada uma grade de n linhas e m colunas representando o lago, 6 ≤ n, m ≤ 10000, encontre o menor número de sonares que você precisa colocar no lago de tal forma que podemos controlar todas as posições da grade, com as seguintes condições:

Um sonar ocupa uma posição da grade; O sonar controla sua própria posição, além das suas posições adjacentes;

As posições nas bordas da grade não precisam ser controladas, pois Nessie não conseguiria se esconder nelas (ela é grande demais para isso).

Considere as seguintes figuras (ver especificação original do problema):

Nas figuras, X representa um sonar, e as posições escuras representam as posições controladas por sonares. A última figura exemplifica uma solução para o problema.

Linguagens: C e C++

Solução:

Para cada valor de n e m lidos, basta imprimir o terço dos valores multiplicado. É importante apenas converter o valor da divisão para inteiro. Os códigos abaixo, em C e C++, adotam a mesma estratégia de solução.

Código em C:

#include <stdio.h>

int main() {

    int t, n, m;
    scanf("%d", &t);
    
    while (t--) {
        scanf("%d %d", &n, &m);
        printf("%d\n", ((int) n/3) * ((int) m/3));
    }

    return 0;
}

Código em C++:

#include <iostream>

using namespace std;

int main() {

    int t, n, m;
    cin >> t;
    
    while (t--) {
        cin >> n >> m;
        cout << ((int) n/3) * ((int) m/3) << endl;
    }

    return 0;
}