ای سی ام (Association for Computing Machinery) یک مسابقه برنامه نویسی است که هر ساله در دنیا برگزار می شود . در این مسابقات تیم ها در قالب هایی ۳ نفره شرکت می کنند و به هر تیم یک دستگاه رایانه جهت برنامه نویسی داده ی شود . نحوه ی سنجش تیم ها به این گونه است که در مسابقات حدودا ۸ سوال محاسباتی و الگوریتمی می دهند هر تیمی سوال های بیشتری در مدت زمان کم تری با خطای کم تری حل کند رتبه ی بهتری کسب می کند .
چگونه در این مسابقات شرکت کنیم؟
برای رسیدن به مسابقات جهانی ای سی ام شما باید در مسابقات منطقه ای شرکت کنید و در صورت گرفتن نتیجه خوب می توانید به مسابقات جهانی بروید . دانشگاه شریف هر ساله مسابقات ای سی ام منطقه ای را در ایران برگزار می کند که در آن هرسال بهترین تیم های ایران و منطقه مثل هندوستان و روسیه و … در آن حظور دارند ، برای شرکت در مسابقات منطقه ای می توانید به سایت acm.blog.ir بروید .
هدف از ای سی ام چیست ؟
سوال اصلی در هر کاری این است که ما چرا باید در آن کار شرکت کنیم؟
این سوال در مورد ACM به طور جدی تری مطرح است، زیرا یک مسئله ی فوق برنامه در دوران دانشجویی محسوب می شود که می تواند وقت و انرژی دانشجو را نیز بگیرد.آیا ما تنها به خاطر مزیت های پیروزی در مسابقات ACM در آن شرکت می کنیم؟ در این صورت فرق ACM با المپیاد کامپیوتر چیست؟ و اگر ما در این مسابقات پیروز نشویم، چه چیزهایی بدست آورده ایم و چیزهایی از دست داده ایم؟ و مهم تر از آن در هدف اکثر تیم های شرکت کننده وجود دارد.برخلاف مسابقات المپیاد کامپیوتر که در آن هدف تنها استفاده از مزیت های پیروزی در این مسابقات است و در صورت باخت در آن جز اندکی علم خاص، چیز دیگری برای ما باقی نمی ماند، در مسابقات ACM هدف خود مسابقات است و نه پیروزی در آن! این بدان معنا است که شما در مسابقات ACM برخلاف المپیاد، باید از خود مسابقات لذت ببرید، از کد زدن لذت ببرید و از فکری که پشت این کدها است؛ نه تنها برای پیروزی در این مسابقات و درج این پیروزی در رزومه ی خود. گرچه ACM مزیت های قراردادی زیادی دارد، ولی هدف اصلی آن این مزیت فلسفی و ذاتی آن است.
با شرکت در ای سی ام چه چیز به دست می آوریم؟
با شرکت در مسابقات ای سی ام علاوه بر لذتی که در آماده شدن و کد زدن و فکر کردن است به دو چیز خیلی مهم دیگر هم دست پیدا می کنیم ۱ – طراحی الگوریتم ۲ – کد زدن سریع
سوال های ACM سوال های خشک و کلیشه ای برنامه نویسی نیستند بلکه سوال هایی هستند که جنبه محاسباتی و الگوریتمی دارد پس با تسلط بر این سوال ها الگوریتم و ذهن خود را به شدت تقویت می کنید.
چه طور برای ACM مسابقات آماده شویم و منابع ای سی ام چیست ؟
قبل از نوشتن راه های آماده شدن برای ای سی ام به این نکته که کلید اصلی موفقیت در ای سی ام است توجه کنید : ای سی ام (acm) یک مسابقه گروهی است و هدف اصلی برگزار کنندگان آن انجام کار گروهی است ، پس هر کاری که می خواهید کنید باید گروهی صورت بگیرد و راز موفقیت یک گروه قوی بودن افراد یک گروه نیست بلکه یک دست بودن افراد تیم است پس پیش از هر کاری یک تیم خوب درست کنید .
بهترین روش برای آمادگی در مسابقات ای سی ام عضویت در سایت هایی هست که در مورد این کار اند و تعداد زیادی سوال اس سی ام در آن است مانند :
– http://sharecode.ir/ (دارنده این سایت یک ایرانی است)
– http://codeforces.com/ (سایت خیلی مطرحی در این زمینه است)
و … که یک سرچ می توانید پیدا کنید . عجله نکنید به خوبی اتعداد زیادی از ین سایت ها را بگردید و آنچه را که مناسب سلیقه تیمتان است پیدا کنید چون هر کدام از این سایت ها روشی خاص خود را دارند.
و البته کتاب هایی زیادی هم در این مورد هستند که معروف ترینشان کتاب programming challenges است که یک جورایی کتاب رسمی مسابقات است که معرفی آن را در لینکی که به آن داده ام آمده است .
تیم های موفق در این مسابقات تیم هایی هستند که معمولا از سال اول آغاز دانشگاه استارت شروع کار را می زنند پس تیمتان را از همین روزها درست کنید و به حل سوال ها به صورت گروهی بپردازید.
یک مساله دیگر که هست یک توهم و فکر کاذب بین بعضی ها جا افتاده است که فکر می کنند فقط تیم های دانشگاه شریف در این مسابقات رتبه می آورند و سایر تیم ها دیگر هیچ شانسی ندارند در حالی چنین چیزی نیست واقعیت این است هر تیمی کار بیشتری کرده باشد برنده است نکته جالب توجه این است که تیم ای سی ام دانشگاه بو علی سینا همدان از نظر رتبه جهانی مقام هایی دارد که هیچ دانشگاهی در ایران ندارد .
پس کار تیمیتون رو از همین امروز شروع کنید اگر می خواهید لذت ببرید از دوران دانشگاهیتون .
Stand on the shoulders of giants
در زیر سه سوال با سطح آسان از مسابقات ای سی ام آورده ام که با زیبایی و شیوه ی سوال های ای سی ام آشنا شوید :
HangOver
Time Limit: 1 Second Memory Limit: 32768 KB
How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We’re assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + … + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below
Input
The input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Each test case is a single line containing a positive floating-point number c whose value is at least 0.01 and at most 5.20; c will contain exactly three digits.
Output
For each test case, output the minimum number of cards necessary to achieve an overhang of at least c card lengths. Use the exact output format shown in the examples.
Sample Input
1.00 3.71 0.04 5.19 0.00
Sample Output
3 card(s) 61 card(s) 1 card(s) 273 card(s)
Collatz Conjecture
Time Limit: 10 Seconds Memory Limit: 131072 KB
The Collatz conjecture which is also known as the 3n+1 conjecture is a very well known and old conjecture in mathematics. The conjecture is as follows. Take any natural number n. If n is even, divided by two to get n/2 and if n is odd number greater than 1, triple it and add one to obtain 3n+1. Repeat this process to get a sequence of natural numbers known as the Hailstone sequence. The conjecture is that no matter what number you start, you always reach 1. The hailstone sequence for n=3 is “3,10,5,16,8,4,2,1″. Paul Erdos said “Mathematics is not yet ripe for such problems” and offered $500 for its solution. Now it’s time to show Erdos that the Collatz conjecture can be proved for small numbers in 11th Iran Internet Programming Contest. You are to write a program that computes the length of the Hailstone sequence for the given n.
Input
There are multiple test cases in the input. Each test case consists of a line containing a non-negative integers 0≤n≤۱۰۰٫ The input terminates with “۰” which should not be processed.
Output
For each test case, output the length of the Hailstone sequence in one line.
Sample Input
1 2 3 0
Sample Output
1 2 8
Shuffling Strings
Time Limit: 10 Seconds Memory Limit: 131072 KB
Suppose S1 and S2 are two strings of size n consisting of characters A through H (capital letters). We plan to perform the following step several times to produce a given string S. In each step we shuffle S1 and S2 to get string S12. Indeed, S12 is obtained by scanning S1 and S2 from left to right and putting their characters alternatively in S12 from left to right. The shuffling operation always starts with the leftmost character of S2. After this operation, we set S1 and S2 to be the first half and the second half of S12, respectively. For instance, if S1=ABCHAD and S2=DEFDAC, then S12=DAEBFCDHAACD, and for the next step S1=DAEBFC and S2=DHAACD. For the given string S of size 2n, the goal is to determine whether S12=S at some step.
Input
There are multiple test cases in the input. Each test case starts with a line containing a non-negative integers 0≤n≤۱۰۰ which is the length of S1 and S2. The remainder of each test case consists of three lines. The first and the second lines contain strings S1 and S2 with size n, respectively, and the last line contains string S with size 2n. The input terminates with “۰” which should not be processed.
Output
For each test case, output -1 if S is not reachable. Otherwise, output the minimum number of steps to reach S. To make your life easier, we inform you that the output is not greater than 50 for the given input.
Sample Input
4 AHAH HAHA HHAAAAHH 3 CDE CDE EEDDCC 0
Sample Output
2 -1
