公式

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.

投稿日時:
最終更新: