سوال
با یاد خدا،
سلام بچه‌ها؟ خوبین؟
یه چند وقتی بود اینجا سوت و کور شده بود. برای همین تصمیم گرفتم دوتا سوال برنامه نویسی بذارم. سطح سوال‌ها متفاوته. ولی در مجموع در حد امتحان‌های عملی دوره تابستون هستند. زمان ما (یادش بخیر) امتحان‌های عملی دوره تابستون ۲ تا سوال بود با ۵ ساعت وقت. فکر کنم دوره تابستون امسال هم همین‌جوری بود. برا همین می‌تونید این دوتا سوال رو مثل یه امتحان تو ۵ ساعت حل کنید.
اگه نتونستید سوال‌ها رو حل کنید ناامید نشید. این سوال‌ها نسبت به سوال‌های مرحله ۳ (امتحان برنامه نویسی قبل دوره تابستون)، الگوریتمی‌تر و بالطبع سخت‌تر اند. اگه از الان شروع به تمرین کردید که سال دیگه وارد دوره بشید توصیه می‌کنم که کنار مباحثی مثل ترکیبیات و گراف، حتما الگوریتم و برنامه نویسی رو هم کار کنید. خصوصا اینکه امتحان مرحله ۳ هم اضافه شده و علاوه بر اون تکلیف مدال‌ها تو تابستون معلوم می‌شه و برای همین بار عملی دوره تابستون هم بیشتر شده. خب دیگه پند و اندرز بسه. اینم سوال‌ها:
-------------------------------------------------------------------------------
سوال ۱: مرتب سازی۱.
خیکوله قرار است یک جایگشت از اعداد ۱ تا n را مرتب کند. برای این کار او از یک ماشین مرتب‌سازی کمک می‌گیرد. این ماشین به این شکل کار می‌کند که در ورودی‌اش یک کارت که روی آن دو عدد a و b نوشته شده است قرار داده می‌شود. سپس ماشین جای عنصر aام و عنصر bام جایگشت را عوض می‌کند. مثلا اگر جایگشت کنونی باشد و در ورودی کارت (4, 5) را قرار دهیم، جایگشت به این شکل در می‌آید: .
به خیکوله m تا کارت داده شده است. او می‌خواهد بداند با کارت‌هایی که دارد چندتا جایگشت از اعداد ۱ تا n را می‌تواند مرتب کند؟ او می‌تواند از هر کارت به تعداد دلخاوه استفاده کند.
ورودی: در خط اول n و m آمده. در m خط بعدی اعداد روی کارت‌ها آمده است.
خروجی: در تنها سطر خروجی یاقیمانده‌ی جواب مساله را بر ۱۰۰۰۰۰۷ چاپ کنید.
محدودیت‌ها: (n , m
-------------------------------------------------------------------------------
سوال ۲: مرتب‌سازی۲.
این بار خیکوله با یک مساله‌ی مرتب‌سازی دیگر مواجه شده است. به او یک دنباله‌ی n تایی از اعداد صحیح داده‌اند و از او خواسته‌اند که این دنباله را مرتب کند. برای این کار او می‌تواند در هر مرحله یک عدد از دنباله را برداشته و به هر جای دیگر از دنباله منتقل کند. مثلا برای مرتب کردن دنباله‌ی او می‌تواند در یک حرکت عدد ۵ را از ابتدای دنباله به انتهای آن ببرد.
خیکوله می‌خواهد بداند برای مرتب کردن دنباله‌ی داده شده حداقل چند حرکت نیاز دارد؟
ورودی: در خط اول n و در n خط بعدی اعداد دنباله به ترتیب آمده‌اند.
خروجی: در تنها سطر خروجی حداقل تعداد حرکت مورد نیاز برای مرتب کردن دنباله‌ی داده شده را بنویسید.
محدودیت‌ها: در ۷۰ درصد تست‌ها n
-------------------------------------------------------------------------------
محدودیت زمان برای هردوتا سوال ۱ ثانیه هست. یعنی برنامه‌تون باید کمتر از یک ثانیه تموم بشه. حافظه‌ای هم که می‌تونید بگیرید حداکثر ۱۶ مگابایته.
-------------------------------------------------------------------------------
سوال اول رو خودم طرح کردم. سوال دوم رو هم یه جایی دیده بودم. به نظر خودم سوال‌های خوبی‌اند. اگه حلشون کردید توصیه می‌کنم کدش رو هم بزنید. ورودی، خروجی و محدودیت‌ها رو دقیق گفتم که اگه وقت شد تست‌دیتا براشون درست کنم تا بتونید کدهاتون رو جاج کنید (یعنی برنامه‌تون رو تست کنید و بهش نمره بدید). خب دیگه! نصف شب شد! من برم بخوابم.
شب خوش!
- ۸۹/۰۵/۱۶