Official

B - Savings Editorial by en_translator


First, we will estimate the maximum possible answer.
In this problem, \(N \le 10^9\). Clearly the answer is less than \(10^9\), but is it actually that large?
With some observation we can see that, for example, after the \(1000\)-th day, the money increases by \(1000\) or more yen. So, at this rate, the money will reach \(10^9\) no later than the \((10^6+1000)\)-th day.
Such a number of days can be simulated by one-day-by-one for loop fast enough than the time limit.
The implementation can be simpler with a infinite loop like while(1), escaping from the loop instantly once the amount of money reaches \(N\) yen. Please also refer to the sample code.

Sample code with Octave:

n = scanf('%d', 'C');

i = 1;
money = 0;

while 1
  money += i;
  if money >= n
    break;
  end
  i++;
end

printf('%d\n',i);

Sample code with PHP:

<?php
$n = fgets(STDIN);

for($i = 1 ; ; $i++){
  $n -= $i;
  if($n <= 0){
    printf("%d\n",$i);
    break;
  }
}
?>

BONUS! Solve the problem for \(N \le 10^{18}\).

Hint In fact, the money in the piggy bank on the \(N\)-th day is \(\frac{(N+1) \times N}{2}\).
Solution When \(X<Y\), the amount of money on the \(X\)-th day is always less than the amount of money on the \(Y\)-th day.
Therefore, it can be solved with a binary search against “is the answer greater than \(X\)?”
Sample code in Go

package main

import "fmt"

func f(n int64) int64 {
  return (n*(n+1))/2
}

func main() {
  var n,ng,ok,mid int64
  fmt.Scan(&n)
  ng = 0
  ok = 3000000000
  for (ok - ng) > 1 {
    mid = (ok + ng) / 2
    if f(mid) < n {
      ng = mid
    } else {
      ok = mid
    }
  }
  fmt.Println(ok)
}

posted:
last update: