[AOJ] No. 0409 床

2019年12月8日

問題

方針

タイルの増加数

タイルの増加数に着目すると、\( 1^2, 2^2, 3^2, 5^2, 8^2, \cdots \) と増加しているので、\( x \) 方向と \( y \) 方向にタイルの辺がフィボナッチ数ずつ増えていることが分かります。フィボナッチ数は、\(F_0 = 1, \ F_1 = 1\) とし、

\[ F_n = F_{n – 1} + F_{n – 2} \]

と計算することで得られます。

タイルの増加する方向

タイルは右、上、左、下の周期で増加していることに注目します。ここで、\( i \) 番目のタイルの増加した領域を \( a_i \leq x < b_i \wedge c_i \leq d_i\) とすると、初期値は \( a_0 = 0, b_0 = 1, c_0 = 0, d_0 = 1 \) です。これを更新することで、この領域に入るタイルの色が分かります。

コード

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int x, y;
    cin >> x >> y;
    int xl = 0;
    int yl = 0;
    int xr = 1;
    int yr = 1;
    int F[100000]{};
    F[1] = 1;
    F[2] = F[1] + F[0];
    for (int i = 1; i < 100000; i++) {
        F[i + 1] = F[i] + F[i - 1];
        if (xl <= x && x < xr && yl <= y && y < yr) {
            int ans = i % 3;
            if (ans == 0) ans = 3;
            cout << ans<< "\n";
            return 0;
        }
        if (i % 4 == 1) {
            xl = xr;
            xr += F[i + 1];
            yr = yl + F[i + 1];
        } else if (i % 4 == 2) {
            xl = xr - F[i + 1];
            yl = yr;
            yr += F[i + 1];
        } else if (i % 4 == 3) {
            xr = xl;
            xl -= F[i + 1];
            yl = yr - F[i + 1];
        } else {
            xr = xl + F[i + 1];
            yr = yl;
            yl -= F[i + 1];
        }
    }
    return 0;
}