ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1223. Chernobyl’ Eagle on a Roof

Is my algorithm correct? If not give me a hint!
Послано Vlad Ionescu 10 июл 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!
Послано sylap 29 авг 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)