ACM

مسابقات ACM                       

انجمن جهانی ACM ، قدیمی ترین و معتبر ترین انجمن تخصصی در زمینه کامپیوتر است. این انجمن فعالیت­های گوناگونی برای ترویج و توسعه علوم و مهندسی کامپیوتر و فناوری اطلاعات و ارتباطات اعم از انتشار نشریات تخصصی، برگزاری همایشها، برگزاری مسابقات برنامه نویسی و غیره انجام می­دهد.

این انجمن با هدف شناسایی و تشویق استعدادهای برجسته در زمینه طراحی الگوریتم و برنامه نویسی، همه ساله مسابقه­ای با نام (ICPC (International Collegiate Programming Contest در سطح جهان برگزار می­کند. این مسابقه یک مسابقه دانشجویی است که تیمهای برنامه نویسی از دانشگاه­های سراسر دنیا در آن شرکت می­کنند.این مسابقه در دو مرحله برگزار می شود. تیم ها ابتدا در مسابقات منطقه ای با هم مبارزه می کنند و تیم های برتر هر منطقه به مسابقات فینال جهانی راه پیدا می کنند و در آنجا برترین تیمهای برنامه نویسی دانشجویی جهان مشخص می­شوند. این مسابقات در قالب تیمهای 3 نفره برگزار می­شود. حامی مسابقات شرکت IBM است.

چند نمونه سوال از مسابقات ACM

مسئله لیوان های وارونه

n لیوان رو میزی قرار دارن که تعدادی از اونها به صورت وارونه هستن. ما هر بار اجازه داریم وضعیت سه لیوان رو هم زمان عوض کنیم. یعنی اگه وارونه بودن درستشون کنیم و اگه درست بودن وارونه کنیم. شما باید برنامه ای بنویسید که مشخص کنه آیا با این شرایط امکان داره همه لیوانها رو تو وضعیت درست قرار داد؟ اگه جواب مثبته ، چطور؟

سطر اول فایل ورودی n رو نشون می ده که از 4 کمتر نیست. سطر بعدی شماره لیوانهایی رو مشخص می کنه که وارونه هستن. انتهای شماره ها با صفر مشخص می شه.

هر سطر فایل خروجی یه مرحله از کار رو نشون می ده. یعنی شماره سه لیوانی رو که تغییر وضعیت می دن.

از مثال زیر هم می تونید کمک بگیرید:

ورودی مسئله

 4

2 4 0

 خروجی مسئله

 1 2 3

1 3 4

 

 

مسئله شاسی برق

تو یه اتاق m تا شاسی برق داریم که به n چراغ متصل هستن. ممکنه بعضی شاسی ها به چند چراغ متصل باشن. هر بار فشار دادن یه شاسی باعث می شه که وضعیت چراغهای متصل به اون تغییر پیدا کنه. یعنی چراغهای روشن خاموش می شن و بالعکس. در ابتدای کار بعضی از چراغها روشن هستن. می خوایم ببینیم آیا می شه با فشار دادن تعدادی از این شاسی ها همه چراغها رو روشن کنیم؟

سطر اول فایل ورودی به ترتیب اعداد n و m رو نشون می ده. m سطر بعدی با شماره چراغهایی که به شاسی ها متصل هستن پر می شه. مثلا سطر اول نشون می ده که کدوم چراغها به شاسی شماره 1 متصل هستن و ... آخر این سطرها با صفر مشخص می شه. و در آخر سطری قرار داره که شماره چراغهای روشن رو مشخص می کنه. این سطر هم با صفر تموم می شه.

هر سطر فایل خروجی شامل یه شماره شاسی خواهد بود که باید فشار داده بشه. اگه امکان روشن کردن تمامی چراغها نبود ، عبارت No Solution توی فایل خروجی نوشته بشه. مثلا:

ورودی مسئله

6 4

1 3 4 0

2 6 0

3 4 5 0

5 6 0

2 3 4 6 0

 

 

خروجی مسئله

1

3

 

 

مسئله بست اعشاری اعداد

همونطور که می دونید هر عدد به فرم کسری رو می شه به فرم اعشاری نوشت. اما بعضی کسرها فرم اعشاری نامتناهی دارن که اصطلاحا بهشون گفته می شه کسر با بسط متناوب (توجه داشته باشید که امکان نداره بسط اعشاری یه کسر غیرمتناوب باشه). حالا باید برنامه ای بنویسید که فرم کسری عدد رو دریافت کنه و فرم اعشاری رو چاپ کنه.

سطر اول فایل ورودی عدد n رو مشخص می کنه که تعداد ورودیهاست. n سطر بعدی رو n عدد کسری تشکیل می دن که صورت و مخرج اونها با فضای خالی از هم جدا شدن. توجه داشته باشید که قدرمطلق مقادیر صورت و مخرج بیشتر از ۶۰۰۰۰ نیست.

هر سطر فایل خروجی بسط اعشاری یه عدد ورودی رو مشخص می کنه. قسمت متناوب عدد باید داخل کروشه قرار بگیره. مثلا:

 

ورودی مسئله:

3

89 250

356 999

353 990

 
خروجی مسئله:

0.365

0.[365]

 

 

مساله عدد دراماتیک:
به یه عدد صحیح مثبت n_دراماتیک گفته می شه ، اگه حاصلضرب اون عدد در n ، از یکبار چرخش ارقامش به سمت راست حاصل بشه. مثلا اعداد 102564 و 128205 اگه در 4 ضرب بشن ، جواب بصورت 410256 و 512820 در می یاد. پس هر دو عدد 4_دراماتیک هستن.

حالا شما باید برنامه ای بنویسید که اعداد تک رقمی و غیر صفر n و k رو بگیره ، و کوچکترین عدد مثبت n_دراماتیک رو که رقم یکانش k هست پیدا کنه! اگر همچین عددی موجود نبود ، صفر رو نتیجه بده.

سطر اول فایل ورودی برنامه تعداد موارد آزمایشی رو مشخص می کنه ، و در سطرهای بعدی زوج اعداد n و k قرار می گیرن. مثلا اگه فایل ورودی به صورت زیر باشه:

2

4    5

2    1

فایل خروجی باید اینطور باشه:

128205
0

 

مسئله 4

 

هر فرمول ترتیبی از یک رقم غیر منفی و عملگرهای  + و - میباشد. هیچ فاصلهای(Space) بین کاراکترهای فرمول قرار ندارد. فرض کنید که فرمولها به طریق صحیح نوشته شده اند. وظیفه شما خیلی ساده است: هر فرمول را ارزیابی کرده و نتیجه را بنویسید!

ورودی مسئله:
ورودی شامل چندی نمونه آزمایشی(Test Case) میباشد. هر Test Case در یک خط قرار می گیرد و هر خط شامل چندین Test Case می باشد که بوسیله Space از هم جدا شده اند.آخرین خط فایل ورودی تنها شامل # می باشد.

جروجی مساله:
برای هر Test Case فرمول را ارزیابی کرده و نتیجه را در یک خط فایل خروجی بنویسید. نتایج فرمولهایی که در یک خط قرار دارند را با یک Space از هم جدا کنید.


مثال ورودی:

1+3+5+7-4 1-2+2
1 6-2 2 1+2

مثال خروجی:

12 1
1 4 2 3