# 4384 : Fire on Field

제한시간
1000 ms
메모리제한
512 MB
해결횟수
2 회
시도횟수
4 회

### 문제

We define A as a sequence of positive integers like the following.

Let A = 1, A = 1. For a positive integer i ≥ 2, A[i] is the smallest positive integer under the condition that no three terms A[i − 2k], A[i − k], and A[i] form an arithmetic progression for any integer k > 0 such that i − 2k ≥ 0, that is, A[i] − A[i − k] ≠ A[i − k] − A[i − 2k].

The sequence is uniquely determined like the following sequence: A = 1, A = 1, A = 2, A = 1, A = 1, A = 2, A = 2, A = 4, A = 4, etc. The sequence element A cannot be 1 since otherwise A = 1, A = 1, A = 1 form an arithmetic progression; here i = 2 and k = 1. If A is any integer larger than one, then the condition is satisfied. Therefore, A should be 2 which is the smallest positive integer among the possible ones. Similarly, it is easy to know that A = 1. The sequence element A cannot be 3 since otherwise A − A[4 − 2] = A[4 − 2] − A[4 − 2 × 2] ; here i = 4 and k = 2. Other natural numbers like 1, 2 and 4 are also possible for A, but the smallest one is 1. Therefore, A = 1.

This sequence is called “fire on field” or “forest fire” since the scatter plot of the sequence looks like spreading fire on a field. See the figure below. Given a non-negative integer n, write a program to output A[n].​

### 입력형식

Your program is to read from standard input. The input consists of one line containing one non-negative integer n (0 ≤ n ≤ 1,000).

### 출력형식

Your program is to write to standard output. Print exactly one line. The line should contain A[n].

`5`

`2`

`8`

`4`

`100`

`4`

### 출처

ICPC 2019 Asia Regional – Seoul Problem A ICPC , ICPC Regionals, Korea

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP