خود را محک بزنید! (سوالات بین المللی ACM)

[zayens]

ACM International Collegiate Programming Contest


من تصمیم دارم برخی سوالات مسابقه برنامه نویسی ACM دانشگاه شریف را در این تاپیک قرار بدم

البته از اسم شریف نترسید چون کد نویسی این برنامه ها نه طولانیه و نه خیلی سخت

پس از حل این سوالات در همین تاپیک کد برنامه را قرار خواهیم داد (دوستان اگر مایل بودن و مهارت کافی داشتن کدهاشون را در همین تاپیک قرار بدن)

صورت سوال اول:

سوال اول خیلی راحته:

برنامه ای که مینویسیم باید به این صورت باشه که کاربر ، اعدادی را (طبق روال خاصی که بعدا میگم) وارد میکند (مثلا در یک تکست باکس) و برنامه، ماتریس این اعداد را در صورت وجود ایجاد میکنه

باید توجه داشت که پیداکردن ماتریس مورد نظر بسیار راحته (یعنی بصورت دستی راحت میشه ماتریس را ساخت) و اصل کار کد نویسی اون هست

اما نحوه پیدا کردن ماتریس

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

2 3
8 10
5 6 7
4
0 2 > 2
2 1 = 3
2 3 > 2
2 3 < 5

اینها مقادیر ورودی است که پس از تایپ اون توسط کاربر باید یک ماتریس 2 در 3 را بده که مقادیر آرایه هاش در زیر اومده:

2 3 3
3 3 4

البته این ورودی ناقصه که مثال کاملش را در آخر میگم ولی در هر حال معنی اعداد بصورت زیره:

خط اول: در خط اول باید 2 عدد با یک فاصله وارد شده باشه

عدد اول تعداد سطرها و عدد دوم تعداد ستونهای ماتریس مورد نظر است(در مثال بالا ماتریس ما 2 سطر و 3 ستون باید داشته باشد)

خط دوم: جمع سطرهای ماتریس(در مثال بالا8 جمع همه آرایه های سطر اول و 10 مجموع همه اعداد در آرایه های سطر دوم است)

خط سوم: خط سوم مربوط به جمع ستونهای ماتریسه (درمثال بالا 5 جمع همه آرایه های ستون اول و 6 جمع همه آرایه های ستون دوم است و 7 برای ستون 3 است)

پس تا اینجا با 3 خط اطلاعات لازم را بدست آوردیم

اما باید محدودیت ها را هم برای این که بفمیم چه آرایه ای چه عددی را داره وارد شده باشه:

در مثال بالا 4 یعنی این محدودیت ها در ادامه 4 خط خواهد بود

پس از این هر خط دقیقا از 3 عدد تشکیل شده . یک علامت > = < که راهنمایی میکنه که آرایه ها چه اعدادی باید باشند .

در مثال بالا اومده:

2 1 = 3

این یعنی آرایه واقع در سطر 2 و ستون 1 دقیقا برابر 3 است

یا مثلا

2 3 < 5

یعنی آرایه واقع در سطر 2 و ستون 3 کمتر از 5 است

*لازم به ذکر است که اگر بخواهیم بیان کنیم که مثلا «همه ی» سطرها یا همه ستونها عددشون فلان است از صفر استفاده میکنیم (مثال:)

0 2 > 2

یعنی آرایه «همه» سطرها در ستون 2 (و یا بهتر بگم : کل ستون دو) آرایه هاش بیشتر از 2 باید باشد

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

یه مطلب دیگه و اون هم این که کاربر میتونه چندین سوال را وارد کنه که در این صورت، جواب هم باید به ترتیب سوالات و با فاصله یک سطر محاسبه بشه

برای این که برنامه بفهمه چند تا سوال وارد خواهد شد، قبل از سطر اول، باید تعداد سوالات مشخص بشه و نیز کاربر باید بعد هر سوال یک سطر خالی بذاره:

پس با این حساب، کامل شده ی مثال بالا در زیر اومده که چون خط ابتدایی عدد 2 است، دارای دو سوال است و برنامه در آخر باید 2 ماتریس را ایجاد کنه:

2

2 3
8 10
5 6 7
4
0 2 > 2
2 1 = 3
2 3 > 2
2 3 < 5

2 2
4 5
6 7
1
1 1 > 10

جواب ها(خروجی مساله) به صورت زیر خواهد بود:

2 3 3
3 3 4

IMPOSSIBLE

این هم از متن اصلی سوالA.rar