[AOJ] No. 0409 床

問題

方針

タイルの増加数

タイルの増加数に着目すると、\( 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 \) です。これを更新することで、この領域に入るタイルの色が分かります。

コード

 

 

AOJ, 数学

Posted by ヤマカサ