Codeforces 50A Domino piling Solution & Explanation

Difficulty : 800

Problem Description

You are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. You are asked to place as many dominoes as possible on the board so as to meet the following conditions:

1. Each domino completely covers two squares.

2. No two dominoes overlap.

3. Each domino lies entirely inside the board. It is allowed to touch the edges of the board.

Find the maximum number of dominoes, which can be placed under these restrictions.

Input

In a single line you are given two integers M and N — board sizes in squares (1 ≤ M ≤ N ≤ 16).

Output

Output one number — the maximal number of dominoes, which can be placed.

Examples

Solution

Consider the following scenarios:

• If both M and N are even, each 2 x 1 domino tile can perfectly cover 2 squares without any leftover squares, so you can directly divide by 2.
• If either M or N is odd, you can place a 2 x 1 domino tile in one direction to cover the odd rows or columns, and the remaining squares will still be in even rows or columns, which can be handled by the method mentioned above, directly dividing by 2.

In summary, regardless of whether M and N are even or odd, each 2 x 1 domino tile can ensure the coverage of 2 squares, so you can directly divide by 2 to calculate the maximum number of dominoes without encountering any mismatched situations. This is because the shape of the domino tiles is compatible with the arrangement of the squares.

C# Solution

Solution1

string[]arr = Console.ReadLine().Split(' '); //split by space
int m = int.Parse(arr[0]);
int n = int.Parse(arr[1]);

Console.WriteLine(m*n/2); 

Java Solution

Solution1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] arr = scanner.nextLine().split(" ");
        
        int m = Integer.parseInt(arr[0]);
        int n = Integer.parseInt(arr[1]); 
        
        System.out.println(m*n/2);
    }
}

Python3 Solution

Solution1

arr = input().split(' ')
m = int(arr[0])
n = int(arr[1])

print(int(m*n/2))

Python divide operator (/) will always return a float number, providing a decimal result.

However, if you need an integer result, you should use the floor division operator (//). The floor division ensures that the result is rounded down to the nearest integer.

JavaScript Solution

Solution1

var arr = readline().split(' ');
var m = parseInt(arr[0]);
var n = parseInt(arr[1]);

print(Math.floor(m*n/2));

Similar to Python, we need to ensure that we don’t end up with a floating-point number when performing the calculation.

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts or clicking ads, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Problem – 50A – Codeforces

Random Codeforces Posts