Codeforces 50A 骨牌堆疊 – 翻譯與解答

難易度 : 800

英文原文如下

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.

中文翻譯

你有一個尺寸為 M × N 的長方形棋盤，同時你擁有無限量的標準骨牌，每張骨牌的尺寸是 2 × 1。你可以旋轉這些骨牌。你的任務是在滿足以下條件的情況下，盡可能多地放置骨牌：

1. 每張骨牌完全覆蓋兩個方塊。
2. 沒有兩張骨牌重疊。
3. 每張骨牌都完全位於棋盤內，允許接觸到棋盤的邊緣。

找出在這些限制下可以放置的最大骨牌數目。

輸入

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

在一行中會給予你兩個整數 M 跟 N  – 棋盤的大小 (1 ≤ M ≤ N ≤ 16)

輸出

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

輸出一個數字 – 骨牌能擺放的最多數量

範例

解題思路

考慮以下情境：

如果 M 和 N 都是偶數，每個 2 x 1 的多米諾骨牌可以完美覆蓋 2 個方塊，沒有多餘的方塊，因此你可以直接除以 2。

如果 M 或 N 中有一個是奇數，你可以沿一個方向放置一個 2 x 1 的多米諾骨牌以覆蓋奇數的列或行，剩下的方塊仍然處於偶數的列或行，這可以使用上面提到的方法處理，直接除以 2。

總結一下，無論 M 和 N 是否都是偶數或其中一個是奇數，每個 2 x 1 的多米諾骨牌都可以確保覆蓋 2 個方塊，所以你可以直接除以 2 來計算最多可以放多少個多米諾骨牌，而不會出現不匹配的情況。這是因為多米諾骨牌的形狀與方塊的排列是相容的。

意思就是直接將 M*N除2取整數就好

C# 跟 JAVA 中 整數相除會自動捨去並回傳整數

但 Python跟JS中就必須要對double進行取整的動作

C#解決方案

方案1

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解決方案

方案1

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解決方案

方案1

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

print(int(m*n/2))

JavaScript解決方案

方案1

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

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

結論

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Problem – 50A – Codeforces

一些其他的文章