[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] 1094. C.幼稚國王的獎賞

[IOJ] 19. 啦啦啦

[IOJ] 14. 費氏數列問題