| تبليغات | X |
مسِئله ی K : برج هانوی
مساله «برج هانوی» از سه میله با نام های A و B و C تشکیل می شود که n دیسک با قطر های مختلف ( و ارتفاع های یکسان ) در میله ها قرار دارند. در ابتدای کار تمام دیسک ها به صورت مرتب شده بر اساس قطرشان ( طوری که کم قطرترین دیسک بالاترین و بزرگ ترین دیسک پایین ترین باشد ) روی میله A قرار دارند.
یک حرکت «مجاز» در این مساله برداشتن بالاترین دیسک از یک میله( میله مبدا )و قرار دادن آن در میله ای دیگر( میله مقصد ) است بطوری که هیچ گاه یک دیسک روی دیسکی با قطر کوچکتر قرار نگیرد. با این وصف ، یک حرکت را می توان با دو حرف بزرگ انگلیسی نمایش داد که حرف اول میله مبدا و حرف دوم میله مقصد است. برای مثال حرکت AB یعنی برداشتن بالاترین دیسک میله A و قرار دادن آن روی تمام دیسک های میله B ( در صورت وجود ). دقت کنید که حرکت AB تنها زمانی مجاز است که میله A حداقل یک دیسک داشته باشد و بعلاوه یا میله B خالی باشد یا قطر بالاترین دیسک میله A ( که جابجا می شود ) از قطر بالاترین دیسک میله B کمتر باشد.
با شروع از حالتی که تمام دیسک ها بصورت مرتب در میله ی A قرار دارند ( نظیر شکل بالا )، بازی هنگامی تمام می شود که تمام دیسک ها به همین ترتیب در میله B قرار بگیرند ( و میله های A و C خالی باشند ) یا تمام دیسک ها به همین ترتیب در میله ی C قرار بگیرند ( و میله های A و B خالی باشند ).
هوشنگ برای حل کردن این معما ، الگوریتم زیر را در پیش می گیرد. او ابتدا یک جایگشت از تمام 6 حرکت موجود در نظر می گیرد ( مثلا جایگشت CB ، AC ، BA ، BC ، AB ، CA از چپ به راست ) ، سپس در هر مرحله سمت چپ ترین حرکت مجاز از حرکات این جایگشت را انجام می دهد. علاوه بر این ، او هبچ وقت دوست ندارد یک دیسک را در دو حرکت متوالی جابجا کند و از این رو اگر یک حرکت ( بعد از حرکت اول ) از مقصد حرکت قبلی آغاز شود ، او این حرکت را غیر مجاز تلقی می کند. برای مثال اگر جایگشت نمونه ی گفته شده را روی میله های شکل در نظر بگیریم ، اولین حرکت هوشنگ AB خواهد بود ( چرا که CA بدلیل خالی بودن میله C غیر مجاز است ) و حرکت دوم او AC خواهد بود: CA غیر مجاز است چون C هنوز خالی است؛ AB غیر مجاز است چون دیسک با قطر 2 را نمی توان روی دیسک با قطر 1 ( که در حرکت اول به B منتقل شده ) قرار داد؛ BC نیز غیر مجاز است چرا که دیسک رویی B در حرکت قبلی تکان خورده و هوشنگ دوست ندارد یک دیسک را در 2 حرکت متوالی جابجا کند و از این رو سمت چپ ترین حرکت مجاز ، AC است!
می توان اثبات کرد که الگوریتم هوشنگ همیشه پایان می یابد! آنچه از شما خواسته می شود این است که با دانستن تعداد دیسک ها و استراتژی هوشنگ( جایگشتی از 6 حرکت ممکن )، مشخص کنید که هوشنگ چند جابجایی انجام می دهد تا بازی تمام شود.
ورودی
در سطر اول ورودی ، تعداد تست داده می شود. سپس هر تست در 2 خط داده می ش.د که خط اول تنها یک عدد n را داشته و در خط دوم یک جایگشت از حرکات ممکن بصورت 6 رشته 2 حرفی ( معتبر و دو به دو متمایز) داده می شود.
خروجی
به ازای هر تست ورودی ، در یک سطر تعداد حرکاتی که هوشنگ می کند را بنویسید.
محدودیت ها
می دانیم که N<=۱ و N<=۳۰ و جواب خروجی هیچ تستی از 10 به توان 18 بیشتر نبست.
مسئله ی G : پله بازی
یک صفحه m در n در نظر بگیرید که خانه های آن مانند صفحه ی بازی مار و پله با اعداد 1 تا mn شماره گذاری شده اند. فردی در ابتدا در خانه ی 1 ایستاده است و می خواهد با تعدادی حرکت به خانه ی mn برود. k نردبان نیز وجود دارند که هر نردبان میان دو خانه ی متفاوت جدول قرار دارد.. در هر حرکت فرد می تواند یکی از این دو کار را بکند:
1- اگر نردبانی وجود دارد که یک سرآن در خانه ی فعلی است به سر دیگر برود ، به شرط اینکه شماره ی خانه ی مقصد بزرگتر از شماره ی خانه ی فعلی وی باشد.
2- به خانه ای که شماره اش دقیقا یکی بیشتر از خانه ی فعلی است برود.
تعداد راه های متفاوت برای پیمودن جدول چقدر است؟
ورودی
ورودی شامل چندین نمونه از مسئله است.
هر نمونه شامل تعدادی خط است. در اولین خط ، 3 عدد طبیعی m ، n و k به ترتیب آمده اند.
( m<=10 & n<=10 & k<=20 ). در k خط بعدی در هر خط یک جفت عدد طبیعی آمده است که دو سر یک نردبان را نشان می دهند، هر دو از mn کمترند و اختلافشان حداقل 2 است. پس از آخرین نمونه ورودی خطی شامل "0 0 0" آمده است. دو سر هیچ نردبانی از جدول یکی نیستند، به عبارت دیگر تمام اعدادی که بعد از خط اول می آیند ، متمایزند. بدین ترتیب نردبان تکراری هم در ورودی وجود ندارد.
خروجی
به ازای هر نمونه مسئله ی ورودی ، یک خط در خروجی بنویسید که شامل تعداد راه های پیمودن جدول است.
(برای مشاهده خروجی و ورودی نمونه ، فایل PDF مساله را دانلود کنید)
مسئله ی F : جاده ها
در هنگام بازجویی اداره پلیس از یک فرد مظنون ، او ادعا کرده است که در یک روز مشخص ، چهار جاده به طول های a ، b ، c و d را که به ترتیب اضلاع یک چهار ضلعی راست را تشکیل می دهند ، پیموده است. در این مسئله به یک چهار ضلعی راست گفته می شود اگر دو خاصیت زیر را داشته باشد:
1- دو ضلع موازی داشته باشد(که به آنها قاعده می گویمم و به دو ضلع دیگر ساق می گوییم)
2- دو زاویه روبرو نداشته باشد که هر دو حاده (کمت از 90 درجه ) باشند.
توجه کنید که طبق این تعریف مستطیل ها راست اند اما متوازی الاضلاع هایی که مستطیل نباشند ، راست نیستند.
اکنون اداره پلیس می خواهد بداند که آیا شکلی با این مشخصات وجود دارد یا نه. مظنون ترتیب پیمایش جاده ها را نیز مشخص کرده است.
در هر خط ورودی ، به ترتیب چهار عدد طبیعی a ، b ، c و d آمده اند. همه ی اعداد ورودی از 1000 کمترند. به ازای هر خط از ورودی یک خط در خروجی چاپ کنید. اگر چهارضلعی راستی با این مشخصات وجود دارد که d و b قاعده های آن و a و c ساق های آن باشد ، در خروجی عبارت "YES" و در غیر اینصورت "NO" بنویسید.
آخرین خط ورودی شامل جهار عدد صفر است.تعداد خطوط ورودی از 10000 کمتر است.
تذکر: لزومی ندارد که d از b کوچکتر باشد.
(برای مشاهده خروجی و ورودی نمونه ، فایل PDF مساله را دانلود کنید)
مسئله ی D : نمودار
نمودار هیستو گرام تعدادی داده ی عددی ، نموداری است که شامل ستون مستطیلی است. هر ستون متناظر با یک بازه از اعداد ، مثلا [1,3) است. ارتفاع هر ستون متناسب با تعداد داده های درون بازه متناظر آن ستون است. در این مسئله شما باید برنامه ار بنویسید که نمودار هیستوگرام تعدادی داده را رسم کند. داده ها در بازه ی [A,B] قرار دارند و نمودار در خروجی باید شامل دقیقا D ستون باشد. البته D در ورودی داده شده است و می دانیم B-A بر D بخشپذیر است. ارتفاع هر ستون با تعداد داده هایی است که در بازه ی متناظر آن ستون قرار دارند. اگر داده ای در مرز دو بازه قرار داشت ، فقط در درون سمت چپی محسوب می شود. برای روشن شدن بیشتر مساله ، بی ورودی و خروجی نمونه توجه کنید. اعداد تکراری ممکن است به عنوان داده بیایند. خود A و B هم ممکن است به عنوان داده بیایند.
ورودی
ورودی شامل تعدادی تست است و پس از آخرین تست خطی با چهار صفر آمده است. هر تست به این شکل است:
در خط اول ورودی ، به ترتیب N ، D ، A و B آمده اند. در N سطر بعدی اعدادی که باید نمودار آنها کشیده شود آمده اند. پس از هر تست(حتی تست آخر) یک خط خالی بگذارید. تمام داده ها در بازه ی [A,B] قرار دارند.
خروجی
قبل از چاپ نمودار در هر تست ، ابتدا خطی شامل "Case #x:" در خروجی بنویسید که در این عبارت به جای x ، شماره ی تست را بنویسید(x لزوما یک رقمی نیست!!). سپس خروجی را مانند آنچه در خروجی نمونه آمده است چاپ کنید. توجه کنید که باید پس از هر تست (حتی تست آخر) یک خط خالی چاپ کنید.
محدودیت ها
N < =50 & N >= 2
A < B & B < 10000 & A>-10000
|
ورودی نمونه |
خروجی نمونه |
|
10 4 0 20 1 4 4 3 5 12 19 19 20 10 7 10 0 10 0 1 5 9 9 9 10 0 0 0 0 |
Case #1: |# |# # |# ## |#### + - - - - Case #2: | # | # | # |# # # # + - - - - - - - - - - |
(برای مشاهده بهتر خروجی و ورودی نمونه ، فایل PDF مساله را دانلود کنید)
مسئله ی B : سرباز ها
در یک پادگان احتمالا نظامی ، n سرباز در یک سطر ایستاده اند. با صدای سوت ؛ هر یک از این سرباز ها 90 درجه می چرخد؛ بعضی به راست و بعضی به چپ. ازاینجا بازی شروع می شود. در هر مر حله ، اگر دو سرباز رو بروی هم ایستاده باشند ، هر دو عقب گرد می کنند. توجه کنید که در هر مرحله ممکن است چند سرباز با هم عقب گرد کنند ولی یک سرباز حداکثر یک بار عقب گرد می کند.
می توان نشان داد که پس از تعدادی مرحله بازی تمام می شود؛ یعنی دیگر هیچ دو سربازی رو به روی هم نیستد. برنامه ای بنویسید که تعداد مراحل بازی را مشخص کند.
ورودی
در هر سطر ، رشته ای از کاراکتر های "<" و ">" آمده است. هر یک از این کاراکترها مشخص کننده یک سرباز است. کاراکتر > به معنی گردش به راست و کاراکتر < به معنی گردش به چپ(در هر مرحله ، دو سربازی که به صورت >< هستند ، بصورت <> می شوند). فاصله ای میان کاراکتر ها نیست.
خروجی
به ازای هر سطر ورودی یک سطر در خروجی بنویسید که شامل تعداد مراحل بازی است.
محدودیت ها
طول رشته ورودی (یعنی همان n) حداکثر 10000 است.
(برای مشاهده خروجی و ورودی نمونه ، فایل PDF مساله را دانلود کنید)
مسئله ی A : معدل گیری
پس از چند هفته امتحانات پی در پی ، امروز کارنامه ی بچه های مدرسه به آنها تحویل داده شد! همه ی نمرات و ضرایب هر درس در کارنامه مشخص شده است ، اما معدل در کارنامه درج نشده است. بچه های مدرسه در محاسباتشان همیشه اشتباه می کنند ، بنابراین از شما خواسته اند ، برنامه ای بنویسید که معدل هر یک از کارنامه ها را بدست آورد.
ورودی
شامل اطلاعات تعدادی کارنامه است. هر کارنامه شامل 3 خط است ، در خط اول یک عدد طبیعی n ، تعداد دروس ، آمده است. می دانیم n بین 2 و 25 است(خود این مقادیر هم می تواند بشود). در خظ دوم n عدد صحیح آمده است که ضرایب دروس 1 تا n هستند. در خط سوم نیز n عدد صحیح بین 0 تا 20 آمده است که نمرات دروس 1 تا n هستند.
پس از آخرین کارنامه ، یک خط اضافه آمده است که فقط شامل عدد 0 است.
خروجی
به ازای هر کارنامه در ورودی ، یک خط در خروجی چاپ کنید که معدل کارنامه را گرد شده به دقیقا 2 رقم اعشار نمایش می دهد. توجه کنید که مثلا اگر جواب دقیقا 19 باشد ، شما باید در خروجی "19.00" چاپ کنید.
(برای مشاهده خروجی و ورودی نمونه ، فایل PDF مساله را دانلود کنید)
