[Codeforces] 735C. Tennis Championship

題目連結:http://codeforces.com/problemset/problem/735/C
我覺得這其實滿有趣的(?,我自己是半猜出跟費式數列有關,感覺好像是要找到最大的$i$使得$\sum_{j=0}^{i}F_j \leq n$,但一直不知道為什麼。看了題解才知道原來其實就是我們想想看如果要贏$n$場比賽,那勢必自己要贏$n-1$場,並且找一個贏過$n-2$場的人來打會最好,所以就得到$F_n = F_{n-1}+F_{n-2}$的費式數列公式了XDD。
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	long long n; cin>>n;
	long long prepre = 0, pre=1, cnt = 0;
	int ans;
	for(ans=0;cnt<n;ans++){
		long long cur = prepre+pre;
		prepre=pre;
		pre=cur;
		cnt+=prepre;
		cerr<<cnt<<'\n';
	}
	cout<<ans-1<<'\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology