Coded both our algorithms. I win by a nose (more visible at larger building sizes -- 1k floors, etc.) Code quality is an abomination, please excuse exploratory programming:
Gist of my approach: dynamically recalculate number of steps to go with each jump we take, using the same approach that you do (find smallest k such that k(k + 1) / 2 > n), rather than assuming it decreases monotonically. This has superior performance around some boundary conditions.
Instructions for running script:
ruby hn.rb patio11 debug 100
ruby hn.rb stormy debug 100
Debug on or off as desired, 100 is size of building.
Then, leave off debug flags, and diff the outputs.
Do you mean "incrementally by 1 each iteration" where you wrote "monotontically", in your reference to Stormbringer's algorithm?
Mathematically, I do not see how any solution could beat Stormbringer's, by considering the cases where tolerance = k+0.5 and tolerance = ((kk +k)/2+0.5, which shows that the set of tolerances for a building of height > (kk+k)/2 requires >= k+1 drops to validate. But I have not been quite formal in my analysis.
http://dl.dropbox.com/u/751473/hn.rb
Gist of my approach: dynamically recalculate number of steps to go with each jump we take, using the same approach that you do (find smallest k such that k(k + 1) / 2 > n), rather than assuming it decreases monotonically. This has superior performance around some boundary conditions.
Instructions for running script:
ruby hn.rb patio11 debug 100
ruby hn.rb stormy debug 100
Debug on or off as desired, 100 is size of building.
Then, leave off debug flags, and diff the outputs.