結果

問題 No.2363 k-bonacci
ユーザー ID 21712
提出日時 2025-05-04 23:11:35
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,695 bytes
コンパイル時間 10,791 ms
コンパイル使用メモリ 248,368 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-04 23:11:48
合計ジャッジ時間 12,206 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"


func main() {
	var n int
	Scan(&n)
	// K = 2
	// A[2] = 1, A[3] = 1, A[4] = 2, A[5] = 3, A[6] = 5, A[7] = 8
	// A[8] = 13, A[9] = 21, A[10] = 34, A[11] = 55
	// K = 3
	// A[3] = 1, A[4] = 1, A[5] = 2, A[6] = 4, A[7] = 7, A[8] = 13
	// A[9] = 24, A[10] = 44, A[11] = 81, A[12] = 149
	// K = 4
	// A[4] = 1, A[5] = 1, A[6] = 2, A[7] = 4, A[8] = 8, A[9] = 15
	// A[10] = 29, A[11] = 56, A[12] = 108, A[13] = 208
	// K = 5
	// A[5] = 1, A[6] = 1, A[7] = 2, A[8] = 4, A[9] = 8, A[10] = 16
	// A[11] = 31, A[12] = 61, A[13] = 120, A[14] = 236
	//
	// A[i] = A[i-1]*2-A[i-K-1]
	//      = (A[i-2]*2-A[i-K-2])*2-A[i-K-1]
	//      = A[i-2]*4-A[i-K-1]-A[i-K-2]*2
	//      = (A[i-3]*2-A[i-K-3])*4-A[i-K-1]-A[i-K-2]*2
	//      = A[i-3]*8-A[i-K-1]-A[i-K-2]*2-A[i-K-3]*4
	//      = (A[i-4]*2-A[i-K-4])*8-A[i-K-1]-A[i-K-2]*2-A[i-K-3]*4
	//      = A[i-4]*16-A[i-K-1]-A[i-K-2]*2-A[i-K-3]*4-A[i-K-4]*8
	//
	// A[i]-A[i-K-1] = A[i-1]*2
	// A[i]-A[i-1] = A[i-1]-A[i-K-1]
	// A[i-1]-A[i-K-1] = A[i-2]+A[i-3]+...+A[i-K]
	// A[i-1] = A[i-2]+A[i-3]+...+A[i-K]+A[i-K-1]
	//
	// K=2, A[2*K] = A[4] = 2 = 2^1
	// K=3, A[2*K] = A[6] = 4 = 2^2
	// K=4, A[2*K] = A[8] = 8 = 2^3
	// K=5, A[2*K] = A[10] = 16 = 2^4
	// K=6, A[2*K] = A[12] = 32 = 2^5
	// K=7, A[2*K] = A[14] = 64 = 2^6
	// K=64, A[2*K] = A[128] = 2^63 ??
	//
	// 収束が早いのでK=64まで全探索ぽそう
	//
	
	if n == 1 {
		Println(2)
		return
	}
	
	for k := 2; k <= 64; k++ {
		a := make([]int, k+1)
		a[k], a[0] = 1, 1
		i := k+2
		for {
			a[i%len(a)] = a[(i+len(a)-1)%len(a)]*2 - a[i%len(a)]
			if a[i%len(a)] == n {
				Println(k)
				return
			} else if a[i%len(a)] > n {
				break
			}
			i++
		}
	}
	Println(-1)
}
0