ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1223. Chernobyl’ Eagle on a Roof

Is my algorithm correct? If not give me a hint!
Posted by Vlad Ionescu 10 Jul 2003 09:42
I thought that  tha fastest way we could determine the floor was a
binary search. For each i=1,n as long as we have enough eggs we do
the binary search and stop when we visited both i and i-1. If we are
left with only one egg we can't risk breaking without knowing the
floor it so we start from the value just below the smallest value we
know the egg hasn't broken and check all of them until we break the
egg. For each binary search we count how many tests we did and just
select the largest one (worst case). The complexity is O(N*log2 N).
Is this correct or am I mistaken somewhere?
And can anyone give me some test cases please?
Re: Is my algorithm correct? If not give me a hint!
Posted by sylap 29 Aug 2013 02:53
Yes, binary search is good when you have enough eggs. But what if you don't have enough eggs? Then when you have 1 egg left you need to check all floors, from 1st to the topmost floor.

For example:
Case eggs=100 and floors=100
Then you will do 7 experiments
I will do 7 experiments too

But case eggs=2 and floors=100
Then you will do about ~1+50 experiments
But I will do 14 (i'm too lazy to write how, sorry)