- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
گويند که در زمان‌هاى قديم پسرى بود به نام کچل‌خان. اين پسر آن‌قدر تنبل بود که حاضر نبود از جايش تکان بخورد. گفته‌اند که فقط يک چيز به تنبلى اين پسر مى‌چربيد و آن هم چيزى نبود جز سيب. کچل‌خان هر روز از صبح تا شب يک جا مى‌نشست و جُم نمى‌خورد مگر اينکه سيب مى‌ديد. يک روز مادر کچل‌خان که ديگر از دستش عاصى شده بود، گفت: «کچل‌خان تو ديگه براى خودت مردى شدى؛ تا کى مى‌خواى اين‌قدر تنبلى کنى؟» و کچل‌خان در حالى که سرش را تکان مى‌داد گفت « سيب، سيب»؛ فکرى به ذهن مادرش خطور کرد: «اگر از اينجا تا در شهر رو سيب بچينم کچل‌خان دنبال سيب‌ها مى‌ره و من میتونم در شهر رو روش ببندم.»
در تاريخ آمده که شهر کچل‌خان تا ميدان داشته که توى هر ميدان يک درخت سيب بوده و بين بعضى از ميدان‌ها کوچه بوده. به دليل بافت قديمى شهر و کوچه‌هاى باريک، اين کوچه‌ها يک‌طرفه هستند (حتی براى آدم‌هاى پياده)! در زمان اتفاق افتادن داستان روى بعضى از درخت‌ها تعدادى سيب قرار داشته است.
بعد مادر کچل‌خان فکر کرد که «براى اين کار مى‌تونم تعدادى از سيب‌هاى درخت‌هاى ميدون‌ها رو بچينم و توى بعضى ميدون‌هايى که سيب ندارن بگذارم؛ کافيه که يک مسير که در هر ميدونش حداقل يک سيب باشه (چه روى درخت و چه روى زمين) بين ميدون کنار خونه و ميدون کنار در شهر درست بشه.» و مادر کچل‌خان ناراحت شد، چون درخت‌هاى سيب بلند بودن و با اينکه پسرش به راحتى ازشون سيب مى‌چيد ولى اين کار براى مادر سخت بود. پس مادر کچل‌خان فکر کرد که «بايد تعداد سيب‌هايى که مى‌چينم رو کمينه کنم.» پس مادر کچل‌خان رفت که خباز رو استخدام کنه که سيب‌ها رو براش بچينه ولى خباز گفت: «من بايد از قبل بدونم که چند تا سيب قراره بچينم.» و مادر گشت و گشت تا شما رو پيدا کرد که برايش يک برنامه بنويسيد که بگويد دست‌کم چند تا سيب بايد چيده شود؛ يک‌طرفه بودن کوچه‌ها تنها براى کچل‌خان مهم است والا خباز مى‌تواند در جهت‌هاى مختلف از آن‌ها گذر کند.
اطلاعیه: می‌توان از میدانی که هیچ جاده خروجی ندارد سیب چید.
اطلاعیه جدید: می‌توان از میدانی که هیچ جاده‌ای ندارد (نه ورودی دارد و نه خروجی) سیب چید.
ورودی
در سطر اول ورودى ، يعنى تعداد ميدان‌هاى شهر آمده است. میدان‌ها از تا شماره‌گذاری شده‌اند. در هريک از سطر بعد به ترتیب میدان‌ها اینگونه توصیف شده‌اند: اولين عدد تعداد سيب‌هاى روى درخت اين ميدان است. دومين عدد تعداد کوچه‌هايى که از اين ميدان خارج مى‌شوند است و بعد از آن شماره‌ى ميدان‌هايى که اين کوچه‌ها به آن منتهى مى‌شود آمده است. در آخرين سطر ورودى هم به‌ترتيب شماره‌ى ميدان‌هاى کنار خانه‌ى کچل‌خان و کنار در شهر آمده‌اند.
تعداد‌سیب‌ها روی همه‌ی درختان حداکثر و تعداد کوچه‌های شهر حداکثر ۵۰۰۰۰ است.
خروجی
درصورتى که بيرون کردن کچل‌خان از شهر ممکن بود، در تنها سطر خروجى کمترين تعداد سيبى که بايد چيده شود را بنويسيد. درصورتى هم که اين کار ممکن نبود، در تنها سطر خروجى بنويسيد No Solution
مثال
ورودی نمونه ۱
خروجی نمونه ۱
ورودی نمونه ۲
خروجی نمونه ۲
ارسال پاسخ برای این سؤال