فرض میکنیم تعداد طبقات برابر n باشد .

با یه تخم مرغ اول یه نفر یه سری از طبقات رو چک میکنه فرض کنید بیشترین فاصله بین دو طبقه ی چک شده برابر x باشد حالا اگر در اینجا تخم مرغ بشکند کاندیدای ما x-1 طبقه ی بین هستند و باید از پایین شروع کنیم و دونه دونه طبقات رو چک کنیم پس 1-x مرحله لازم است (بدیهی اگر یدونه یدونه نریم و تخم مرغ بشکند نمیفهمیم کدام طبقه بوده)

پس تعداد مراحل لازم حداقل1-n/x+x مرحله می باشد که مینیمم این تابع زمانی اتفاق میافتد که x برابر جزر n باشد پس ما با دوبرابر جذر n منهای یک می توانیم طبقه ی مورد نظر را پیدا کنیم و این مینیم حالت است !

قبلا مشابه رو دیده بودم :) lol

اول اینجا را بخونید اگه میخواید !!! :

دقت کنید که فرض کنید طبقه ی A جواب مسئله باشد یعنی اگر تخم مرغ رو از A بندازیم میشکند و قبل از A تخم مرغ نمیشکند ! پس اگر ما تخم مرغ رو از طبقه ای انداختیم و سالم ماند هم میتوانیم ازش استفاده کنیم هم اینکه می فهمیم A بالاتر قرار دارد !

حال الگوریتم که با آن تعداد بتواند :

میاییم طبقات را به دسته های رادیکالی تقسیم میکنیم یعنی اگر 100 طبقه داریم به 10 دسته ی 10 تایی متوالی تقسیم میکنیم حال می آییم تخم مرغ را از اولین طبقه ی هر دسته پرتاپ میکنیم ( حداکثر رادیکال n مرحله) حال اولین جایی که تخم مرغمان شکست میفهمیم A قبل از اینجا و بعد از جایی که انداختیم و سالم ماند قرار دارد یعنی رادیکال n-1 طبقه حال این دسته را از اول دونه دونه میشماریم که میشود رادیکال n منهای 1 مرحله پس با آن تعداد توانستیم یعنی 10000 طبقه را با تنها و تنها 199 تومن ببخشید 199 بار میتوانیم !!

اثبات کمینه بودن : فرض کنید اولین جایی که اولین تخم مرغ شکست بزرگترین دسته ی متوالی که هیچ کدام امتحان نشده اند برابر x باشد پس حداقل n/x بار انجام داده ایم !! حال یک تخم مرغ برایمان مانده و کاندیدای ما حداقل x-1 تا طبقه می باشد پس .....(متن بالا :) )

جوابش میشه کوچکترین N بطوری که N.(N+1)/2 بزرگ تر از تعداد طبقاتمون بشه ، مثلا برای 100 طبقه مثال میزنم که برابر میشه با 14 ، اینجوری عمل میکنیم که اول از طبقه 14 میندازیم ، بعد از طبقه 14+13 بعد از 14+13+12 و . . . حالا اگر در مرحله iام بشکنه N-i تا طبقه مونده که اونارو هم یکی یکی امتحان میکنیم از پایین.

نگفته که میخوایم تخم مرغ سالم داشته باشیم در نتیجه دو طبقه دو طبقه میریم بالا تا جایی که تخم مرغ اول بشکنه بعد دو طبقه داریم که کاندائن که یکیشون معلوم نیست هنوز با تخم مرغ بعدی اونو امتحان میکنیم واسه بالاتر از دو بهینست بعد بگم که تقریبا جواب بالایی هاست