B - Setsubun 解説 by en_translator
To solve the problem, use a for loop to simulate eating \((N+i)\) beans on year \(i\).
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin >> n >> k;
for(int i=0;;i++){
k-=(n+i);
if(k<=0){
cout << i << "\n";
break;
}
}
return 0;
}
But why is this solution valid?
The constraints of this problem is \(1 \le N,K \le 10^8\).
The case requiring the longest years is to start eating beans from age \(1\) until eating \(10^8\) or more beans.
Meanwhile, if he keeps eating beans for \(10^5\) years starting from year \(1\), he will eat about \(5 \times 10^9\) beans.
Therefore, eating a total of \(K\) or more beans will always happen within the next \(10^5\) year.
Performing \(10^5\) iterations in the loop finishes fast enough compared to the execution time limit of two seconds.
投稿日時:
最終更新: