غلطه کلن گذاشتم این باگو نزنید

مسئله رو یه جور دیگه تبدیل می کنم :(به هر طبقه یه عدد متناظر می کنیم که شمار طبقه است )

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

دو حالت داره یا $k> log(n)$

که این میشه $ log(n)$

در غیر اینصورت

$order=\frac{n}{2^{k-1}}+(k-1)$

شاید یکم باگ داشته باشه

جواب با توجه به اونی که قبلتر دادم تقریبا واضحه با این وجود توضیح میدم. فرض کنیم حداکثر تعداد طبقاطی که میتونیم حل کنیم با i تخم مرغ و j حرکت برابر باشه با dp_i_j ، حالا آپدیتش واضحه دیگه؛ تخم مرغ رو از جایی میندازیم که در صورت شکستنش ، تعداد طبقات مشکوک رو با یک تخم مرغ کمتر و یک انداختن کمتر حل کنیم ، پس dp_i_j میشه:

for(k = 1,k < j) dp_i-1_k +1

یک مثال هم میزنم ، مثلا فرض کنیم 3 تا تخم مرغ و 5 تا حرکت داریم ؛ اولی رو از جایگاه 11 میندازیم ، اگه شکست که 10 تا خونه رو با 2 تخم مرغ و 4 حرکت میتونیم اگر نشکست هم میریم از طبقه 18 میندازیم اگر شکست 6 خونه رو میتونیم با 2 تخم مرغ و 3 حرکت بزنیم و . . . در نهایت میشه 25.

قسمت الف: میشه با یه ایده داینامیک دو بعدی دیگه هم (متفاوت با چیزی که توی نظرات مطرح شد) حلش کرد :

dp[i][j] = min (d[k-1][j-1]) + i/k که i تعداد طبقات و j تعداد تخم مرغ هاست و sqrt(i)<= k <=i

در واقع k به این معنی است که تخم مرغ رو در طبقات k , 2k , 3k , ... می اندازیم. و اول جایی که شکست پس جواب قطعا بین یکی از این ضرایب k هست که باید ادامه گشتن رو با یک تخم مرغ کم تر اونجا ادامه بدیم (که در واقع میشه k-1 طبقه باقی مانده) . پس روی تمام حالات ممکن k چک می کنیم ببنیم کدوم جواب کم تری تولید می کنه. با کمی دقت معلوم میشه که k همیشه بهتره یکی از اعداد بیش تر از جذر تعداد طبقات باشه.

i/k هم به خاطر اینه که در بدترین حالت ممکن تا طبقه i/k بریم (پرتاب انجام بدیم). پس بیش ترین مقدار هزینه ای که در این مرحله میدیم i/k هست.

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

لینک کدم