Problem Solving►UVa

UVa 696 - How Many Knights

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

給棋盤 M x N ，問能放幾個西洋棋的騎士。

Solution

可以分成三種狀況：(o 為騎士)

  1. 1 x N or M x 1：此時可以整排放滿
    ooooooooooo
  2. 2 x N or M x 2：採用這種放法，四格四格交錯放。
    ooxxooxxo..
    ooxxooxxo..
  3. M x N 都超過 2 時就用這種，會比四格四格放來的多：
    oxoxoxoxo
    xoxoxoxox
    oxoxoxoxo

Code

UVa 696
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int M, N;
    while (scanf("%d%d", &M, &N) && (M || N))
    {
        int a = min(M, N), b = max(M, N), ans;

        if (a == 1)
            ans = b;
        else if (a == 2)
        {
            int c = b % 4;
            if (c)
                ans = (b / 4) * 4 + (c > 1 ? 4 : 2);
            else
                ans = (b / 4) * 4;
        }
        else
            ans = (a * b + 1) / 2;
        printf("%d knights may be placed on a %d row %d column board.\n", ans, M, N);
    }

    return 0;
}