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: