مسابقات ACM

[mahdi_sun]

سلام من پیشنهاد دارم دوستانی که در مسابقات ACM (مسابقات جهانی برنامه نویسی دانشجویی که همه ساله در نقاط مختلف دنیا به طور جداگانه برگزار می شود و تیم های برتر در دور نهایی با هم رقابت می کنند )تجربه ی شرکت در مسابقات را دارند تجربیات خود را در اختیار دیگران قرار بدهند مثل نحوه ی تقسیم وقت بین سوالات و ....
پیشنهاد دیگر این که سوالات سالهای قبل رو با جواب یا بدون جواب بنویسید تا جوانتر ها با سطح سوالاتی که در این مسابقات می آد آشنا بشوند.
امید وارم این کار مفید واقع بشه.

[404_3140]

می تونید به خود سایت ACM مراجعه کنید. سوالها اونجا هست. حتی تست کیس هاش.

از طرفی این سایت هم هست که سوال هایی توش هست و داره اضافه هم می شه به مرور زمان، توش ثبت نام کنید و سوالاتشو حل کنید. هز چند وقت یه باز هم مسابقات آزمایشی داره

[mahdi_sun]

همان طور که گفتم این مسابقات در مرحله اول به صورت منطقه ای برگزار می شود که ایران از این لحاظ در منطقه ی غرب آسیا قرار می گیرد که تقریبا هر ساله دانشگاه شریف میزبان این مسابقات است و در صد بسیار زیادی از تیم ها نیز ایرانی هستند و 2 یا 3 تیم خارجی شرکت می کنند امسال از بین چند هزار نفر شرکت کننده فقط 90 تیم به مرحله ی پایانی صعود کردند که سهم منطقه ی ما 4 تیم بود مسابقات نهایی 6 تا 10 آپریل در دانشگاه آلبرتا کانادا برگزار می شود.
البته هدف من ار این متن بیشتر بیان مباحث علمی قضیه بود و اگر مایل باشید از فردا سوالات و جواب بعضی از آنها را که مربوط به سالهای قبل و برای مناطق مختلف است را قرار می دهم.
امید وارم مفید واقع شود.

[mahdi_sun]

برای شروع کار یکی از سوالات آسون رو که مربوط به مسابقات سال 82 یا 83 می شه رو می زارم البته به صورت عکس بود و زیاد حال تایپش رو نداشتم شرمنده.
اما سوال فکر کنم واضح است ولی اگر کسی احتیاج به راهنمایی داشت در خدمت هستیم.
فعلا به قول یکی از بچه ها بای تا های!!!

[mahdi_sun]

با عرض معذرت مثل اینکه عکس نمایش داده نمی شد از این به بعد دیگه سوالات رو تایپ می کنم.
این هم سوال ما:

فرض کنید n طناب هم اندازه داریم و می خواهیم با استفاده از آنها یک شی سنگین را بلند کنیم. به هر طناب یک وزن پاره شدن t نسبت می دهیم. یعنی اینکه اگر بخواهیم شی سنگین تر از t را با آن بلند کنیم طناب پاره می شود.
اما ما می توانیم یک شی را با چندین طناب(به صورت موازی) با هم بلند کنیم در این صورت فرض می کنیم اگر وزن شی w باشد و از k طناب استفاده کنیم باید هر طناب وزنی برابر w/k را تحمل کند یعنی برای هر طناب t>w/k باشد.مثلا با طناب هایی با وزن پاره شدن 1و3و10 حداکثر می توان یک شی با وزن 3 را بدون پاره شدن طنابی بلند کرد در حالی که یکی از طنابها به تنهایی شی با وزن 10 را تحمل می کند.
وزن پاره شدن n طناب داده شده است وظیفه شما آن است که وزن سنگین ترین شی را بیابد که بتوان آن را با بستن زیر مجموعه ای از طناب ها بلند کرد.

[404_3140]

 

1.sort mikonim,tori ke : a[0]<=a[1]<=..<=a[n-1]

2.for(int i=0;i<n;i++)

 b[i]=(n-i)*a[i];

3.ans=max(b[i] ha);

chera?khodetoon fek konin

[mahdi bg]

سلام

با عرض معذرت مثل اینکه عکس نمایش داده نمی شد از این به بعد دیگه سوالات رو تایپ می کنم.
این هم سوال ما:

فرض کنید n طناب هم اندازه داریم و می خواهیم با استفاده از آنها یک شی سنگین را بلند کنیم. به هر طناب یک وزن پاره شدن t نسبت می دهیم. یعنی اینکه اگر بخواهیم شی سنگین تر از t را با آن بلند کنیم طناب پاره می شود.
اما ما می توانیم یک شی را با چندین طناب(به صورت موازی) با هم بلند کنیم در این صورت فرض می کنیم اگر وزن شی w باشد و از k طناب استفاده کنیم باید هر طناب وزنی برابر w/k را تحمل کند یعنی برای هر طناب t>w/k باشد.مثلا با طناب هایی با وزن پاره شدن 1و3و10 حداکثر می توان یک شی با وزن 3 را بدون پاره شدن طنابی بلند کرد در حالی که یکی از طنابها به تنهایی شی با وزن 10 را تحمل می کند.
وزن پاره شدن n طناب داده شده است وظیفه شما آن است که وزن سنگین ترین شی را بیابد که بتوان آن را با بستن زیر مجموعه ای از طناب ها بلند کرد.

سوالش خیلی خیلی ساده است
لطفا فرمت فایل ورودی و خروجی رو هم بذارین؟
اگر وزنی که طناب ها می تونن نگه دارن مرتب شده باشه با O(n) میشه
مسلئه رو حل کرد
و اگر وزنی که طناب ها می تونن نگه دارن مرتب شده نباشن با o(nlogn) میشه
مسلئه رو حل کرد

[mahdi bg]

سلام

می تونید به خود سایت ACM مراجعه کنید. سوالها اونجا هست. حتی تست کیس هاش.

از طرفی این سایت هم هست که سوال هایی توش هست و داره اضافه هم می شه به مرور زمان، توش ثبت نام کنید و سوالاتشو حل کنید. هز چند وقت یه باز هم مسابقات آزمایشی داره

چرا دیگه عوض نمی گیره؟
همش پیغام میده "افزودن کاربر با خطا متوقف شد"

[empoly]

سلام خسته نباشید
من خودم زمانی خیلی تو حال و هوای ACM بودم(خیلی خوبه، خدا را شکر کنید چون عالمیه، هیچ جای دیگه پیدا نمی شه) خلاصه این که الان به دلیل مشغله های زیاد فرصت ندارم ولی چند تا پیشنهاد دارم باشد که آنها را بخوانید اگر کمکتان کرد که ما را دعا کنید و اگر تنها وقتتان را گرفت من حقیر را ببخشید:
1- سوالات را به همان شکل انگلیسی که هست قرار دهید( نیاز نیست حتما عکسش نمایش داده بشه، همون انگلیسی را کپی کنید یا لینک بدهید). خلاصه بزارید بچه ها با متن انگلیسی challenge داشته باشند.
2- برای هر سوال یک وقتی را بذارید مثلا دو روز و بعد از اون در مورد جواب بحث کنید.
3- فرمت ورودی و خروجی را هم در اختیار همه قرار دهید (فایل های ورودی و خروجی) که شامل همون تست کیس های آورده شده در صورت سوال باشه.
4- پس از اتمام وقت مزبور متن فارسی را قرار دهید و درباره ی منظور سوال بحث کنید. سوال هایی یافت می شند که نکته ی اون ها منظور سوال هست از اونجا به بعدش آسونه.
5- بهترین و بهینه ترین جواب را هم در سایت قرار دهید تا همه اشکالات خودشون را بفهمند.
6- برای برخی از سوال ها لازم می شه که روش ها و تکنیک هایی بررسی شوند سعی کنید با معرفی منابع و خوندن اونها راههای جدید و جالب را بیاموزید.(دکتر قدسی یک کتاب در زمینه ی الگوریتم ها داره که می تونه مفید باشه)
7- اگه از سوالاتی استفاده کنید که توی سایت ها یی که مسابقات برگزار می کنند و به صورت آنلاین سوالات را کامپایل می کنند بهتره چون زحمت تست کردن پاسخ بچه ها هم میفته گردن اون سایت ها . یکی از این سایتها اینه:acm.zju.edu.cn ولی تعداد دیگری هم وجود داره.
8- این هایی که گفتم همه پیشنهاد بودند ممکنه بگید اگه بخواهیم این طوری کار کنیم که هفته ای یه سوال هم حل نمی شه ولی می خوام بهتون بگم تو این راه باید زمان زیادی بزارید و نظم زیادی هم داشته باشید به مرور زمان سرعت پیشرفتتون زیاد می شه.
----------------------------------------------------------------------------------------------------------------
امیدوارم تو کارتون موفق باشید. من دیگه شاید موفق به سر زدن به این پست نشم ولی اگه خواستید با من تماس بگیرید :
ایمیل:molla_ahmadi@yahoo.com
بلاگ: blog.itpars.ir

[mahdi_sun]

سلام ببخشید که چند وقتی نبودم تلفن قطع بود و به علت تعطیلی مخابرات نمی تونستم کاری بکنم دیگه ایرانه دیگه.......!
منم قبول دارم سوال قبلی ساده بود این رو گذاشتم تا بگم سوالات این مسابقات خیلی هم سخت نیست مخصوصا در مرحله مقدماتی
حالا سوال بعدی که به سفارش دوستان زبان اصلی گذاشتم با فرمت ورودی و خروجی یک سمپل هم داشت که چون جدولی بود به هم می ریخت نگذاشتم در ضمن سوال سوال اول سال 85 شریف هست فعلا بای :

Problem A. Team Arrangement
Barry Bennett, the coach of the Bings football team, wants to arrange his team for an important match against the Bangs. He decides on the formation he wants to play, for example 4-4-2, meaning that there will be four defenders, four midfielders, and two strikers (and of course, one goalkeeper). Your task is to determine the players who will play. For each available player, we know his role (e.g. midfielder). For each role, the players are selected in ascending order of their numbers. When the players are selected, you must determine the captain too, who is the player with the longest record in the team play. In case two players have the same record, the one with bigger number is chosen. Note that the captain is chosen among the players that are selected in the arrange.
Input (filename: A.in)
The input consists of multiple test cases. The first 22 lines of each test case contain the data for the 22 available players in this format: number name role year1–year'1 year2–year'2 ...
number is the player number (unique positive integer less than 100). name is a string of at most 20 letters. role is a single character among G, D, M, S, for goalkeeper, defender, midfielder, and striker respectively. Each yeari –year'i pair (yeari  year'i) shows the player has been a member of the team between the specified years (inclusive). The years are in four-digit format. There is at least one and at most 20 such pairs, and the same year is not repeated more than once in the list. There is a 23rd line describing the desired formation, like 4-4-2 in that format. Note that there are only three numbers in the formation (so, 4-3-2-1 is not valid), none of them is zero, and their sum is always 10. The input is terminated by a line containing a single 0.
Output (Standard Output)
For each test case, output a list of 11 players chosen in the arrange. Each line must contain the player number, his name and his role, separated by single blank characters. The players must be sorted according to their role, in the order of goalkeeper, defenders, midfielders, and strikers. The players with the same role are sorted according to ascending order of their numbers. There is an exception that the captain always comes as the first player in the entire list. If it is not possible to arrange the team conforming to the desired formation, write a single line containing IMPOSSIBLE TO ARRANGE in the output. There should be a blank line after the output for each test case.

[ICEMAN]

به نظر من یه بخش برای مسابقات و ... داشته باشیم بد نیست
مطرح کردن سوال ها و بحث برای جواب ها و ...

[mahdi_sun]

سلام
ببخشید که دیر به دیر می یام مشغول عزاداری بودیم و زیاد وقت نمی شد شب ها بیام از پاسخ های پر محبت دوستان معلومه دوستان از خوندن سوال بلند انگلیسی خوششون نمی یاد به همین دلیل سوال کوتاه انتخاب کردم.
سوالات چند سال اخیر منطقه شمال شرق امریکای شمالی رو گرفتم توش دنبال یه سوال خوب می گشتم که به یه سوال رسیدم که فکر می کنم سوال خوبی باشه اما فکر می کنم جا برای کامل تر شدن داره سوال برای سال 2005 هست اگه نظری دارین بگین و دوباره من رو به خاطر دیر به دیر اومدنم ببخشید اما سوال اینه :

Who's the Smartest?
We'd like to write a list of people, ordered so that no one appears in the list before anyone he or she is less smart than. The input will be a list of pairs of names, one pair per line, where the first element in a pair names a person smarter than the person named by the second element of the pair. That is, each input line looks like:
<smarter-person> <less-smart-person>

For example:
Einstein Feynmann
Feynmann Gell-Mann
Gell-Mann Thorne
Einstein Lorentz
Lorentz Planck
Hilbert Noether
Poincare Noether

(We don't mention computer scientists for obvious reasons.) There is no limit to the number of lines of input. Your output should be a list of all the distinct input names, without duplicates, one per line, ordered as described above. For example, given the input shown above, one valid output would be:
Einstein
Feynmann
Gell-Mann
Thorne
Lorentz
Planck
Hilbert
Poincare
Noether

Note that the "smarter than" relation supplied as input will not, in general, specify a total order that would allow us to write out the desired list in strictly decreasing order of smartness. For example, the following output is also valid for the input shown above:
Hilbert
Einstein
Feynmann
Gell-Mann
Poincare
Thorne
Lorentz
Planck
Noether

[whitehat]

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

[molla652003]

منم موافقم , یه سری کد سوال های حل شده از مسابقات ACM دانشگاه شریف هم دارم.
اگه کسی پایه هست بشینیم همه اش رو حل کنیم بگه تا چند نفری با هم کار کنیم , وگرنه تک نفری اصلا حال نمیده !

سوال ها رو حل می کنیم , بعد یه مقدار در مورد الگوریتم اش توضیح میدیم و کدش رو در اختیار هم می زاریم , چطوره ؟