A를 다음과 같은 양의 정수의 수열로 정의합니다.

A[0] = 1, A[1] = 1이라고 하자. 양의 정수 i ≥ 2에 대해 A[i]는 세 항 A[i − 2k], A[i − k], A[i]가 i − 2k ≥ 0을 만족하는 정수 k > 0에 대한 등차 수열을 형성하지 않는 조건 하에서 가장 작은 양의 정수이다. 즉, A[i] − A[i − k] ≠ A[i − k] − A[i − 2k]이다.

수열은 다음 수열과 같이 고유하게 결정됩니다. 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 등. 수열 요소 A[2]는 1일 수 없습니다. 그렇지 않으면 A[0] = 1, A[1] = 1, A[2] = 1이 등차 수열을 형성합니다. 여기서 i = 2이고 k = 1입니다. A[2]가 1보다 큰 정수이면 조건이 충족됩니다. 따라서 A[2]는 가능한 정수 중 가장 작은 양의 정수인 2여야 합니다. 마찬가지로 A[3] = 1임을 쉽게 알 수 있습니다. 시퀀스 요소 A[4]는 3이 될 수 없습니다. 그렇지 않으면 A[4] − A[4 − 2] = A[4 − 2] − A[4 − 2 × 2]가 됩니다. 여기서 i = 4이고 k = 2입니다. 1, 2, 4와 같은 다른 자연수도 A[4]에 가능하지만 가장 작은 수는 1입니다. 따라서 A[4] = 1입니다.

이 시퀀스는 "들판의 불" 또는 "산불"이라고 불립니다. 시퀀스의 산점도가 들판에 불이 번지는 것처럼 보이기 때문입니다. 아래 그림을 참조하세요.

음이 아닌 정수 n이 주어졌을 때 A[n]을 출력하는 프로그램을 작성하세요.

#4384 upload 4 done 2 how_to_reg 2

Fire on Field timer 1s memory 512MB

#4384

Fire on Field 1s 512MB