Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1428
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1428
Searching for Nessy
EspañaTimelimit: 1
The Loch Ness Monster is a mysterious and unidentified animal said to inhabit Loch Ness, a large deep freshwater loch near the city of Inverness in northern Scotland. Nessie is usually categorized as a type of lake monster.
https://en.wikipedia.org/wiki/Loch_Ness_Monster
In July 2003, the BBC reported an extensive investigation of Loch Ness by a BBC team, using 600 separate sonar beams, found no trace of any "sea monster" (i.e., any large animal, known or unknown) in the loch. The BBC team concluded that Nessie does not exist. Now we want to repeat the experiment.
Given a grid of n rows and m columns representing the loch, 6 ≤ n, m ≤ 10000, find the minimum number s of sonar beams you must put in the square such that we can control every position in the grid, with the following conditions:
- One sonar occupies one position in the grid; the sonar beam controls its own cell and the contiguous cells;
- The border cells do not need to be controlled, because Nessie cannot hide there (she is too big).
For example,
where X represents a sonar, and the shaded cells are controlled by their sonar beams; the last figure gives us a solution.
Input
The first line of the input contains an integer, t, indicating the number of test cases. For each test case, there is a line with two numbers separated by blanks, 6 ≤ n, m ≤ 10000, that is, the size of the grid (n rows and m columns).
Output
For each test case, the output should consist of one line showing the minimum number of sonars that verifies the conditions above.
| Sample Input | Sample Output |
|
3 |
4 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < = b; ++i)
#define RFOR(i, b, a) for (int i = b; i >= a; --i)
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REPIT(c, it) for (list::iterator it = c.begin(); it != c.end(); it++)
#define MAX 30
#define INF 0x3F3F3F3F
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long int64;
typedef pair < int, int> ii;
typedef vector<int> vi;
int main()
{
ios::sync_with_stdio(false);
double a, b;
int c;
cin >> c;
while (c--) {
cin >> a >> b;
cout << int(ceil((double(a - 2) / 3.0)) * ceil((double(b - 2) / 3.0))) << "\n";
}
return 0;
}
Input
6 6
7 7
9 13
Output
4
12
#2 Code Example with Javascript Programming
Code -
Javascript Programming
//// READING FILE | STREAMS ////
const { createReadStream } = require("node:fs")
const { createInterface } = require("node:readline")
class LineReader {
/**
* @param {import("node:fs").PathLike} path
* @param {BufferEncoding} encoding
* @return {import("node:readline").ReadLine}
*/
static createReadLineInterface(path, encoding = "utf8") {
const readStreamOptions = {
encoding: encoding,
flags: "r",
emitClose: true,
autoClose: true
}
return createInterface({
input: createReadStream(path, readStreamOptions),
crlfDelay: Infinity,
terminal: false
})
}
/**
* @param {import("node:fs").PathLike} path
* @param {BufferEncoding} encoding
*/
static create(path, encoding) {
const RLI = LineReader.createReadLineInterface(path, encoding)
let EOF = false
const nextLineGenerator = (async function* () {
for await (const line of RLI)
yield line
})()
RLI.once("close", () => { EOF = true })
return {
hasNextLine: () => !EOF,
nextLine: async (/** @type {unknown} */ fn) => {
const { value } = (await nextLineGenerator.next())
return (typeof fn === "function") ? fn(value) : value
},
close: () => RLI.close()
}
}
}
async function main() {
const output = []
const PATH = "/dev/stdin"
const ENCODING = "utf8"
const lineReader = LineReader.create(PATH, ENCODING)
const numTestCases = Number.parseInt(await lineReader.nextLine(), 10)
for (let i = 0; i < numTestCases && lineReader.hasNextLine(); i += 1) {
const [N, M] = (await lineReader.nextLine())
.split(" ", 2)
.map(value => Number.parseInt(value, 10))
output.push(Math.trunc(N / 3) * Math.trunc(M / 3))
}
if (lineReader.hasNextLine())
lineReader.close()
console.log(output.join("\n"))
}
main()
Input
6 6
7 7
9 13
Output
4
12
#3 Code Example with Python Programming
Code -
Python Programming
for g in range(int(input())):
a, b = [int(x) for x in input().split()]
print((a//3) * (b//3))
Input
6 6
7 7
9 13
Output
4
12