[AOJ] No. 0556 タイル (Tile)

2019年11月27日2019年12月4日

問題

方針

上下左右対称であることを利用して解きます。\( 1 \leq x \leq \lceil \dfrac{N}{2} \rceil \) かつ \( 1 \leq y \leq \lceil \dfrac{N}{2} \rceil \) かつ \( y \leq x \) の領域を考えます。これは、タイルを \( 4 \) 分割し、左下のタイルにおいて、右下の三角形の領域を表していることになります。この領域では、\( y \) の値によって色が簡単に求まります。例えば、\( y \) が \( 3 \) の倍数であればタイルの色が黄色であることが分かります。

次に、座標を上記の領域に動かすことを考えます。\( x \) 座標については、左右対称なので、\( \lceil \dfrac{N}{2} \rceil < x \) のとき、\( N – x \) と移動させることができます。

次に、\( y \) 座標について、\( \lceil \dfrac{N}{2} \rceil < y \) のとき、\( N – y \) と移動させることができます。さらに、\( x < y \) のときは、\( x \) と \( y \) を入れ替えれば良いです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll N;
    int K;
    cin >> N >> K;
    ll a[K], b[K];
    for (int i = 0; i < K; i++) {
        cin >> a[i] >> b[i];
    }
    for (int i = 0; i < K; i++) {
        ll x = a[i];
        ll y = b[i];
        if (x > (N + 1) / 2) {
            x = N - a[i] + 1;
        }
        if (y > (N + 1) / 2) {
            y = N - b[i] + 1;
        }
        if (y > x) {
            y = x;
        }
        //cout << x << " " << y << "\n";
        if (y % 3 == 1) {
            cout << "1";
        } else if (y % 3 == 2) {
            cout << "2";
        } else {
            cout << "3";
        }
        cout << "\n";

    }
    return 0;
}