سلام
[attachment=8400]
سلام این سوال تقریبا با یه خرده تغییر توی یکی از مسابقات ACM اومده بود که باید الگوریتمش رو مینوشتی ولی توی کتاب مقسمی روش حل بهینه اون آورده شده
اول پنکیکی رو پیدا میکنیم که کوچکترین شماره رو داشته باشه کفگیر رو زیر اون قرار میدیم و به همرا تمام پنکیک های بالایش وارون میکنیم که به این ترتیب پنکیک با شماره کوچکتر روی همه قرار میگیره حالا اگه دقیقا کفگیر رو زیر پایین ترین پنکیک قرار بدیم و همه رو وارون کنیم با این کار کوچکترین پنکیک دقیقا زیر هم قرار میگیره .
خب در مرحله بعدی دیگه با زیری ترین پن کیک که همون کیچکترین هستش کاری نداریم و N-1 پنکیک بالای اون رو به همین ترتیب با دو تا وارون جای مناسبش قرار میدیم.
فقط در مرحله N-1 پنکیک N-1 رو با وارون کردن جای خودش قرار بدیم تنها پنکیکی که با این پنکیک وارون میشه N هستش که اینم خود به خود جای خودش قرار میگیره و دیگه نیازی به وارون کردن نداره
پس تعداد عملیات وارون میشه ۲N-1