یک میز چوبی داریم که $n$ میخ باریک تا نیمه بر روی سطح آن کوبیده شدهاند. برای مشخص کردن نقاط روی سطح میز از مختصات $(x,y)$ آنها استفاده میکنیم. یک نخ نازک هم به شکل خط شکستهای روی سطح میز قرار گرفته است، به طوری که در طول مسیرش $x$ آن افزایش مییابد. به عبارتی دیگر برای تمام نقاط آن میتوان با داشتن مختصهی $x$ به طور یکتا مختصهی $y$ نخ را در صورت وجود تعیین کرد. دو سر نخ از درون دو سوراخ ریز به زیر میز رفتهاند. اگر دو سر نخ را از زیر میز بکشیم، طول نخ روی میز تا اندازهای کاهش مییابد که از روی میخی عبور نکرده باشد. به عنوان مثال اگر در وضعیت اولیه، نخ از بالای یک میخ عبور کرده باشد(با مختصهی $y$ بیشتر)، کشیدن آن نمیتواند باعث شود که در وضعیت پایانی، نخ از پایین همان میخ عبور کند. واضح است که اگر نخ را کاملا بکشیم، وضعیت نهایی طوری خواهد بود که طول نخ در بین حالتهای مجاز (بدون عبور از میخها)، کمینه باشد. میخواهیم شکل نخ را در وضعیت نهایی(پس از کشیدن آن تا جای ممکن) محاسبه کنیم.
به عنوان مثال، در شکل زیر میخها با دایرههای سیاه و سوراخها با دایرههای سفید نشان داده شدهاند. شکل بالایی نشاندهندهی وضعیت اولیهی نخ است و شکل پایین وضعیت نهایی نخ را پس از کشیده شدن نمایش میدهد.
برنامهای بنویسید که: