UVa11231 - Black and white painting(Math theorm)

題目大意

給予你一個 n * m 的西洋棋棋盤(黑白相間棋盤)，並且會讓你知道右下角的顏色是白色還是黑色，試問你可以在這個棋盤內，找到幾個 8 * 8 的面積，且這面積有限制，右下角棋格必須是白色。

題目連結

重點觀念

• 由簡單開始思考，不斷收斂

分析

我們從簡單的方式開始思考

• 在不考慮右下角棋格是白色的情況下，答案會是 \((n-7) * (m-7)\)
• 我們畫張圖來理解

  • 

  • 假設 n = 5, m = 5，要找 3 * 3 面積，且右小角必須是白色
  • 每一排最多會有三個，3 * 3 面積
  • 其中 x，我們設定是 3 * 3 面積，右小角為黑色，就是我們不可計入的面積
• 在畫第二張圖理解

  • 

  • 我們可以知道 x 的部分，我們不能計入，那我們將所有的 x 往下移
  • 會發現其比例似乎約為 1/2
  • 但第三排第二個還是 x，這樣算法不精確
  • 可以發現，每兩排的 x，可以完整組完一排 x。
• 因此我們只要知道突出的那排，會有幾個 x 就好。
  • 可以從規律得出，每兩排的 x 都只會差 1。
  • 每一排最右邊是白色時，則那排的 x 會少 1。
• 因此就能推出公式 (((n-7) * (m-7) + c) / 2)

參考連結

UVa11231 - Black and white painting by uva
UVa11231 - Black and white painting by pritishthakkar

心得

很久沒有這樣推規律，算數學了。不得不說，真的很快樂。
但也有點浪費時間，也有點痛苦XD。

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define int long long
using namespace std;

int32_t main()
{
    int n, m, c;
    while(cin >> n >> m >> c && n != 0 && m  != 0){
        cout << (((n-7) * (m-7) + c) / 2) << "\n";
    }

    return 0;
}