DEV Community

JaeHonity
JaeHonity

Posted on

Coding Test - Snail wants to climb

https://www.acmicpc.net/problem/2869

test1

Image description

In the beginning, I thought it's so simple test because one while loop can solve it.

But after I failure the test cases, I check one more time and they want "0.25" second of optimization.

Spoiler

I found the math logic.

each day, Snail climbs up and fell down, but other way, Snail is fell down and climb up.

So there's this logic is available.

n = days

-fall * (n - 1) + climb  * n >= max
-fall * n + fall + climb * n >= max
-fall * n + climb * n >= max - fall
(climb-fall) * n >= max - fall
n = (max - fall) / (climb - fall)
Enter fullscreen mode Exit fullscreen mode

and without loop, just one time of calculation is solving the problem!

Top comments (0)