ICPC 2019 Asia Regional – Seoul Problem A- Fire on Field > 문제은행 : 정보올림피아드&알고리즘




4384 : Fire on Field

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

문제

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

 

Let A[0] = 1, A[1] = 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[0] = 1, A[1] = 1, A[2] = 2, A[3] = 1, A[4] = 1, A[5] = 2, A[6] = 2, A[7] = 4, A[8] = 4, etc. The sequence element A[2] cannot be 1 since otherwise A[0] = 1, A[1] = 1, A[2] = 1 form an arithmetic progression; here i = 2 and k = 1. If A[2] is any integer larger than one, then the condition is satisfied. Therefore, A[2] should be 2 which is the smallest positive integer among the possible ones. Similarly, it is easy to know that A[3] = 1. The sequence element A[4] cannot be 3 since otherwise A[4] − 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[4], but the smallest one is 1. Therefore, A[4] = 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 , 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