معرفی مسابقات ای سی ام ACM و آمادگی برای آن

acm-team

ای سی ام   (Association for Computing Machinery)  یک مسابقه برنامه نویسی است که هر ساله در دنیا برگزار می شود . در این مسابقات تیم ها در قالب هایی ۳ نفره شرکت می کنند و به هر تیم یک دستگاه رایانه جهت برنامه نویسی داده ی شود . نحوه ی سنجش تیم ها به این گونه است که در مسابقات حدودا ۸ سوال محاسباتی و الگوریتمی می دهند هر تیمی سوال های بیشتری در مدت زمان کم تری  با خطای کم تری حل کند رتبه ی بهتری کسب می کند .

چگونه در این مسابقات شرکت کنیم؟

برای رسیدن به مسابقات جهانی ای سی ام شما باید در مسابقات منطقه ای شرکت کنید و در صورت گرفتن نتیجه خوب می توانید به مسابقات جهانی بروید . دانشگاه شریف هر ساله مسابقات ای سی ام  منطقه ای را در ایران برگزار می کند که در آن هرسال بهترین تیم های ایران و منطقه مثل هندوستان و روسیه  و … در آن حظور دارند ، برای شرکت در مسابقات منطقه ای می توانید به سایت  acm.blog.ir  بروید .

هدف از ای سی ام چیست ؟

سوال اصلی در هر کاری این است که ما چرا باید در آن کار شرکت کنیم؟

این سوال در مورد  ACM به طور جدی تری مطرح است، زیرا یک مسئله ی فوق برنامه در دوران دانشجویی محسوب می شود که می تواند وقت و انرژی دانشجو را نیز بگیرد.آیا ما تنها به خاطر مزیت های پیروزی در مسابقات ACM در آن شرکت می کنیم؟ در این صورت فرق ACM با المپیاد کامپیوتر چیست؟ و اگر ما در این مسابقات پیروز نشویم، چه چیزهایی بدست آورده ایم و چیزهایی از دست داده ایم؟ و مهم تر از آن در هدف اکثر تیم های شرکت کننده وجود دارد.برخلاف مسابقات المپیاد کامپیوتر که در آن هدف تنها استفاده از مزیت های پیروزی در این مسابقات است و در صورت باخت در آن جز اندکی علم خاص، چیز دیگری برای ما باقی نمی ماند، در مسابقات ACM هدف خود مسابقات است و نه پیروزی در آن! این بدان معنا است که شما در مسابقات ACM  برخلاف المپیاد، باید از خود مسابقات لذت ببرید، از کد زدن لذت ببرید و از فکری که پشت این کدها است؛ نه تنها برای پیروزی در این مسابقات و درج این پیروزی در رزومه ی خود. گرچه ACM  مزیت های قراردادی زیادی دارد، ولی هدف اصلی آن این مزیت فلسفی و ذاتی آن است.

با شرکت در ای سی ام چه چیز به دست می آوریم؟

با شرکت در مسابقات ای سی ام علاوه بر لذتی که در آماده شدن و کد زدن و فکر کردن است به دو چیز خیلی مهم دیگر هم دست پیدا می کنیم ۱ – طراحی الگوریتم ۲ – کد زدن سریع

سوال های ACM  سوال های خشک و کلیشه ای برنامه نویسی نیستند بلکه  سوال هایی هستند که جنبه محاسباتی و الگوریتمی دارد پس با تسلط بر این سوال ها الگوریتم و ذهن خود را به شدت تقویت می کنید.

img_9006

چه طور  برای ACM مسابقات آماده شویم و منابع ای سی ام چیست ؟

قبل از نوشتن راه های آماده شدن برای ای سی ام  به این نکته  که کلید اصلی موفقیت در ای سی ام است توجه کنید : ای سی ام (acm) یک مسابقه گروهی است و هدف اصلی برگزار کنندگان آن انجام کار گروهی است ، پس هر کاری که می خواهید کنید باید گروهی صورت بگیرد و راز موفقیت یک گروه قوی بودن افراد یک گروه نیست بلکه یک دست بودن افراد تیم است پس پیش از هر کاری یک تیم خوب درست کنید .

بهترین روش برای آمادگی در مسابقات ای سی ام عضویت در سایت هایی هست که در مورد این کار اند و تعداد زیادی سوال  اس سی ام در آن است مانند :

http://sharecode.ir/  (دارنده این سایت یک ایرانی است)

http://projecteuler.net/

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

ACM

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

Sample Output

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

Sample Output

 

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

Sample Output

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۳۶ comments

  • سلام من سوال داشتم می توانم بپرسم که چگونه باید برنامه نویسی را یاد بگیرم من یک بچه ۱۴ ساله هستم و خیلی به برنامه نویسی علاقه دارم وقت کمی تجربه و کمک می خواهم

  • عالی بود ممنون

  • سلام خیلی ممنونم از مطالب خوبتون ، ببخشید من سوال داشتم ، مسابقه ACM فقط مخصوص دانشجو های رشته مهندسی نرم افزار هست؟ ، رشته تحصیلی من ریاضیات و کاربرد ها هست ولی اشنایی با ++C و جاوا دارم ، من هم میتونم در مسابقه شرکت کنم؟

  • عالیه..دقیقا کد و جوابش کجاس؟ کجای سایته کدفرسه؟

    • فرهاد دلیرانی

      سوال ها مال خیلی وقت پیشه، لینک سوال ها رو ندارم ولی توی سایت کدفورس می تونی بری به بخش problemset اونجا سوال ها هست و وقتی هم به صفحه ی هر سوال بری می تونی جواب بقیه را هم ببینی

  • سلام،من به زبان c++ خیلی واردم. ولی رشته دانشگاهیم تجربیه. میخواستم بپرسم می تونم توی گروه شرکت کنم؟

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

    • فرهاد دلیرانی

      بله بسیار قوی است و کتابخانه های خیلی خوبی دارد فقط کند است – به همین دلیل سوال هایی که سرعت خیلی مهمه را با سی پلاس حل می کنند و سوال هایی رو که برنامه نویسیش با کلاس های جاوا آسان تره با جوا می نویسند

      • خیلی ممنون از اینکه پاسخگوی سوالات بچه ها هستید ، واقعا برای بچه ها انرژی مثبت هستید، حداقل برای من که اینطور . انشاا… در زندگی کاریتونم موفقت باشید .

  • سلام بی زحمت سوالات مسابقه یACMبرنامه نئیسیو برای دانود تو وبلاگتون بزارید

  • سلام
    در مسابقات ACM برای پیاده سازی حل مسئله از بین دو زبان C و C++ شما کدوم زبان رو پیشنهاد میکنید؟
    با تشکر

    • فرهاد دلیرانی

      هر دو زبان های قوی هستن ولی به نظرم کار با سی پلاس پلاس خیلی راحت تره مثلا string سی پلاس پلاس در خیلی از موارد کار باهاش آسان تره تا char * در سی . STL سی پلاس پلاس هم پیاده سازی و سرعت را به شدت زیاد می کند ، در اس تی ال انواع ساختمان داده ها و الگوریتم ها را دارید فقط باید از آن استفاده کنید و برای مسابقه ای که سرعت خیلی خیلی مهم است چنین چیزی غیر قابل چشم پوشی است!
      به نظر من سی پلاس پلاس خیلی بهتره برای این کار ولی نه این سی پلاس پلاسی که فقط از حلقه و دستور چاپ استفاده می شود! بلکه سی پلاسی که با تمام بخش های ضروری اش برای مسابقه آشنا باشید و به راحتی بتوانید از کتابخانه های مختلفش استفاده کنید در مسابقه.

  • سلام من الان کلاس هفتمم (دوم راهنمایی قدبم)الان دارن از ما ازمون مسابقات ریاضی ای سی ام میگیرن که پس فرداست من هم ثبت نام کردم دنبال یه سری تست برای اماده سازی هستم

    • محمد جمالی

      CodeForces یکی دیگر از سایت های مختص به برنامه نویسی است که پایه آن را روس ها تشکیل می دهند.

      اما این سایت تفاوتی با سایت هایی مثل UVa دارند که مسابقه محوری است. این سایت هر چند وقت یکبار مسابقاتی برگزار می کند که کاربران با توجه به عملکرد در آن ها رتبه بندی می شوند.

      همچنین پس از مسابقه با ارسال پاسخ می توانید ورودی هایی که داور به برنامه می دهد، پاسخ برنامه خود و پاسخ صحیح را مشاهده کنید و اگر برنامه تان اشتباه بود، اشتباهش را متوجه شوید. این ویژگی خیلی به تمرین برای برنامه نویسی کمک می کند.

      در زیر نشانی این سایت را مشاهده می کنید:

      http://www.codeforces.com

  • سلام من یکم تو سوال هنگ اور گیر کردم میشه یه زره راجع بهش برام توضیح بدید

    • فرهاد دلیرانی

      سلام ، می گه اگر یک کارت داشتیم یک دومش را در از لبه میز بیرون می گذاریم ، اگر دو کارت داشتیم کارت دوم را روی کارت اول می گذاریم بطوری که کارت دوم یک سومش از کارت اول بیرون باشد و دفعه بعد یک چارم کارت بعد از کارت دوم بیشتر باشد.
      در ورودی اندازه طولی که از میز بیرونه داده می شود و ما باید حساب کنیم برای رسیدن به آن طول چندتا کارت را روی هم بگذاریم

  • با سلام
    من تصمیم دارم در مسبقات acm دانش اموزی شرکت کنم (من دوم دبیرستانم) الان زبان های
    php
    java script
    C++
    رو بلدم به ترتیبی که بلدم نوشتم یعنی php رو از همه بهتر خوندم و c++ رو ….
    البته وقت دارم که c++ رو بهتر یاد بگیرم میخواستم بدونم اصلا می تونم نوی مسابقه شرکت کنم و اگه می تونم می شه چند منبع (سایت،کتاب،….) به من معرفی کنید با شکر

    • فرهاد دلیرانی

      سلام ، یک مسابقه ای سی ام دانش آموزی داریم که اطلاعات زیادی در موردش ندارم که می تونی تو اون شرکت کنی ،یک نکته ای هم که هست اینه اونایی که معمولا تو ای سی ام مقام میارن معمولا از دبیرستان کار کردن و در دانشگاه نتیجشو می گیرند.درای سی ام با زبان سی و سی پلاس پلاس و جاوا می شه کد زد که با توجه به قدرت و سرعت، ++C گزینه خیلی خوبی است . بهترین کار اینه که سوال های زیادی از نمونه سوال های موجود حل کنی و با امکانات و کتابخانه های زبان برنامه نویسی آشنا بشی ،در مطلب یک سری سایت معرفی کردم که می تونی نمونه سوال ازش بگیری و کد بفرستی براشون و ببینی کد درسته یا نه ،که این کار به شدت قدرت پیاده سازیتو در برنامه نویسی به شدت بالا می بره، استفاده از کتاب های الگورتم هم خوبه ،از اونجایی که من سطح شما رو نمی دونم نمی تونم چیزی پشنهاد کنم ولی با یک سرچ می تونید کلی کتاب پیدا کنید که با توجه به نیازتون می تونید یکی انتخاب کنید.

  • نمیشه از طرف دانشگاهی شرکت نکرد؟ یه تیم آزاد؟ متاسفانه هیچ راهی برای شرکت دانشگاهی نداریم. گویا محدودیت سنی هم داره؟

  • کی گفته المپیادیا فقط برای مزیتش می خونن.والا اونا هم علاقه دارند و اکثرا کسایی هستن که کنکور بخونن راحت رتبه میارن اما میرن دنبال علاقشون.مثل خودم و دوستایی که میبینم و المپیادین.البته مشخصه ه خب دوست دارن از اون مزیت ها هم استفاده کنن .متشکر که خوندید! .

    • فرهاد دلیرانی

      من خودم یکی از طرف دارای شدید المپیاد هستم ،درسته مقام نیاوردم ولی دستی در المپیاد دارم 🙂 . می خواستم یکم افراد به سمت ای سی ام هدایت کنم یخورده زیاده روی کردم!

  • میشه راجعبه سوال آخر توضیح بدید ( یا معنیش کنید ؟)

    دقیقا متوجه نشدم چی میگه

    • فرهاد دلیرانی

      می گه دوتا رشته با اندازه طولش می دهند و با یک رشته دیگر.و شما دو رشته را با هم یکی در میان ترکیب می کنید و مقایسه کنید می بینید اون یکی رشته شده یا نه اگر شده بود تعداد مراحلی را که تا حالا انجام داده اید را در خروجی چاپ می کنید اگر نه رشته حاصله را نصف می کنید و با دو رشته جدید همین کار را می کنید این کار را می کنید رشته نورد نظر به دست بیاد اگر رشته مورد نظر به دست اومد که تعداد مراحل را چاپ می کنید اگر نه این کار را ۵۰ بار می کنید اگر نشد منفی یک را بر می‌گرداند. به متن سوال توجه شود ترکیب کردن s1 با. S2. ترتیب خاصی دارند و تجزیه کردن رشته حاصله نیز ترتیب خاصی دارد.

  • #include “stdafx.h”
    using namespace std;

    #include
    #include

    int ShufflingStrings(int n)
    {
    int i= 1;

    while (n != 1)
    {
    if (!(n%2))
    n /= 2;
    else
    n = (n*3)+1;

    i++;
    }
    return i;
    }

    void main()
    {
    int result[3],i=0;

    for (i = 0; i < 3; i++)
    scanf_s("%d",&result[i]);

    for (i = 0; i < 3; i++)
    printf("%d\n",ShufflingStrings(result[i]));

    char a = getchar();
    }

  • #include
    #include
    int OverHang(float limit)
    {
    float result = 0, n = 2;
    while (result 0.00);
    while (j<(i-1))
    result[j++] = OverHang(limit[j]);
    for (j = 0; j < i-1; j++)
    printf("%d card(s)\n",result[j]);
    getchar();
    }

  • الگوریتم شماره یک :

    #include
    #include
    int OverHang(float limit)
    {
    float result = 0, n = 2;
    while (result 0.00);
    while (j<(i-1))
    result[j++] = OverHang(limit[j]);
    for (j = 0; j < i-1; j++)
    printf("%d card(s)\n",result[j]);
    getchar();
    }

Leave a Reply

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *