صفحه ۳۰
مرحله سوم برگزار شد! اما سوالات
سلام
مرحله سوم هم برگزار شد!
امتحان تو سه روز برگزار شد که روز اول یک امتحان آزمایشی گرفتند و نتیجش هیچ تاثیری تو انتخاب افراد برتر نداشت! روز دوم و روز سوم هم هرکدوم یک امتحان اصلی داشت.
اکثر سوالها تو المپیادهای داخلی و خارجی اینطوریه که باید یه برنامهای بنویسی و برنامهت رو بفرستی برای سیستم!
اما خوب بعضی موقعها هم اینطوری نیست! بعضی سوالها اینطوریه که یک یا چند ورودی بهت میدند و میگند خروجی به ازای این ورودیها چی میشه! اصلا هم کاری به این ندارند که چجوری این خروجی رو در آوردی! اسم قشنگی هم داره.. به اینجور سوالها میگند Output Only !
تو این امتحان هم تمام سوالها به صورت Output Only بود. یعنی در واقع شما رو مجبور به نوشتن برنامه نمیکنند.. اما خودتون مجبور میشید برنامه رو بنویسید!
تو این امتحان به هرکی یه عدد ∆ دادند که برای هرکی یکتاست،، بعد ازتون میخوان که جواب رو نسبت به ∆ بدست بیارید! چیز بامزهایه کلا!
اما سوالها!
۳ تا آزمون با ۳تا عنوان متفاوت برگزار شد که میتونید برید بگیریدشون:
آزمون آزمایشی ، آزمون اصلی اول ، آزمون اصلی دوم
سوال چهارم آزمون اصلی دوم ، فایل marysub.txt رو به صورت ضمیمه داشت که برای حل سوال بهش نیاز میشه!
حل سوالات آزمون اصلی اول هم موجوده! میتونید بگیریدش
بچههایی که سال دومی بودند و قبول نشدند حواسشون جمع باشه که به راحتی میتونند جبران کنند. کسایی که الآن مرحله۲ و مرحله۳ رو قبول شدند چیز زیادی بیشتر از شما ندارند! جز اینکه فقط و فقط یک امتحان رو بهتر دادند!
اما اگه شما تابستون رو به بطالت بگذرونید انوقت اونها چیزها از شما بیشتر خواهند داشت! چون اونها توی دورهی تابستون چیزای زیادی یاد میگیرند
خلاصه سعی کنید وقتتون هدر ندره! این تابستون برای شما خیلی ارزش داره!
«پاینده باشید!»
۱۳۸۹/۰۴/۰۴ · ۱۰:۰۰
نتایج آمد
بالاخره پس از مدت ها انتظار ،نتایج اعلام شد.
به همه خسته نباشید می گم و به اونایی که قبول شدن تبریک می گم.
کسایی
که فکر می کردن قبول می شن ولی اسمشون تو لیست نیست ، بدونن که هنوز امیدی
هست! بله ، منظورم اعتراضه. هر سال چند نفری با اعتراض قبول می شن ، شاید
شما امسال یکی از اونا باشید!
یکپست قدیم شازززهست که سابقهی موفق یک المپیادی توی اعتراض هستش. برید و بخونید تا با
روند اعتراض بیشتر آشنا بشید! فقط خواهشنا وسط کار، ناامید نشید! ناامیدی
کار رو خیلی خراب میکنه. برای اعتراض کردن نیاز به روحیهی بسیار قوی
دارید!فرم تجدید نظری که باشگاه داده رو پرینت کنید، پرش کنید؛ و فکس کنید به یکی از این شماره هایی که باشگاه داده:44447353 یا44437577 یا44450802.
اگه سوالی داشتید می تونید با باشگاه تماس بگیرید.
شماره تماسهای باشگاه: 44450800 (روابط عمومی) ؛ 44450810 (مدیریت آموزش)
به همون روابط عمومی تماس بگیرید بهتره!
و اما کسایی که اسمشون تو لیست هست.. میدونم چقدر
خوشحالی! (اگه خوشحال نیستی خیلی کسل کنندهای!) ببین تو الآن سد بزرگ
مرحله۲ رو شکوندی، اما هنوز راه ادامه داره.. مرحله ۳!
توسایت رسمی المپیاد کامپیوتر ایران یه
توضیحاتی جدید راجع به این مرحله۳ که قراره برگزار بشه دادند. برید خوب و
با دقت بخونید تا یه اطلاعات خوبی راجع به این آزمون بدست بیارید یکم!
یه نکتهی خیلی مهم:اگه به کسی قول دادید مهمونش کنید؛ مهمونش کنید! نپیچونید! D:امیدوارم تو مرحله بعدی هم موفق باشید!
اگه خوشحالید یا ناراحت.. خودتون رو کنترل کنید. «آری؛ زندگی این است!»
سربلند باشید
۱۳۸۹/۰۳/۲۳ · ۱۵:۴۱
جواب پست قبل + آزمون برنامه نویسی + سوال
آقا بازهم معذرت به خاطر اینکه دیر پست زدم، مخصوصا از حسام. راستش قرار بود این پست رو تقریبا یه هفته پیش بزنم و توش لینک راهحل سوال هایی که حسام تو پست قبل گفته بود رو بذارم اما به خاطر یه سری مشکلات به تاخیر افتاد. خباین لینکراه حل دوتا سوالیه که حسام تو پست قبلی نوشته بود. با تشکر از مهران.
---------------------------------------------------------------------------------------------------------
در مورد آزمون برنامه نویسی. من چندبار سعی کردم از کمیته در مورد شکل این آزمون بپرسم، یکی از دلایل تاخیر تو پست زدن هم همین بود. چون میخواستم وقتی اطلاعات کامل بدست آوردم پست بزنم. احتمالا تا دو-سه روز آینده تو خود سایتhttp://www.inoi.irاطلاعیه مربوط به این آزمون رو میزنند. اما تا الان میدونم که به احتمال زیاد این امتحان مثل امتحانیه که تو دوره ده روزه بهمنماه برگزار شد. یعنی سوالهاش اون قالبی که من و حسام تو پستهای قبل گفتیم نداره و خیلی سادهتره. برای اینکه بیشتر آشنا شید توصیه میکنم سوالهای آزمون بهمنماه رو بخونید. احتمال زیاد تا فردا-پسفردا اینجا میذارمشون. فعلا تو ادامه این پست چندتا سوال مشابه این آزمون میذارم. (سوال دومی رو جواد عابدی طرح کرده).
---------------------------------------------------------------------------------------------------------
۱- عدد تغییر در یک دنباله از اعداد صفر و یک را تعداد جفتهای صفر و یک مجاور هم در آن دنباله تعریف میکنیم. اگر همهی دنبالههای ۱۳ بیتی (دنبالههای ۱۳ تایی از اعداد صفر و یک) که عدد تغییرشان بزرگتر مساوی ۳ است را به ترتیب الفبایی مرتب کنیم، ۳۸۹ امین دنباله را پیدا کنید.
۲- عدد طبیعی n را گلابی میگوئیم، اگر به ازای هر عدد طبیعی مثل m که m
---------------------------------------------------------------------------------------------------------
خب دیگه! رفع زحمت کنم!
در پناه حق!
۱۳۸۹/۰۳/۱۸ · ۱۳:۳۶
چندتا چیز
سوال رو که حل کردید و کدش رو هم زدید، mail کنید به E-mail من به نشانیه:
hessamjudge [at] gmail [dot] com
بعد چندتا نکته رو توجه داشته باشید:
۱. فایل کدتون رو پیوند کنید و متن کد رو توی میل ننویسید (خیلی سخت میشه اون موقع!)
۲. اگه با Dev کد میزنید حواستون باشه آخر کار که خواستید برای من بفرستید اون getch و conio.h رو پاک کنید که تو compiler من compile error نشه
۳. اول کدتون دو خط اضافه کنید: خط اول user: unknown// خط دوم task: perm// یا task: chcase// این space ها رو همون جاهایی که زدم شمام بزنید که برای من دردسر نشه! مرسی. اگه خط دوم نوشتید
task: perm// یعنی این کد مربوط به سوال اول میشه! اگه نوشتید task: chcase// یعنی این کده سوال دوم هستش
همین! بعد وقتی کد رو فرستادید سیستم به صورت اتوماتیک عمل نمیکنه، کاملا دستیه. پس صبر کنید تا من چک میل کنم! و بعد جواب رو براتون میل میکنم
اما سوال ها
سوال اول: perm (یک ثانیه، ۱۶ مگابایت)
برنامهای بنویسید که عدد n را از ورودی بخواند و تمام اعدادی را که میتوان با ارقام آن ساخت را در خروجی چاپ کند
ورودی:
ورودی شامل یک خط است که در آن خط عدد n آمده است.
خروجی:
تمام اعدادی را که میتوان با ارقام n ساخت (که شامل خود n نیز میشود) را از کوچک به بزرگ، و هرکدام در یک خط چاپ کند.
محدودیتها:
n عددی طبیعی و حداکثر ۱۰٫۰۰۰٫۰۰۰ است و در ارقام n صفر یافت نمیشود
ورودی نمونه:
سوال دوم: chcase (یک ثانیه، ۸مگابایت)
رمزگشایی این رشتههای رمزگذاری شده به این شکل است که هرجا در رشتهی رمزگذاری شده به ۱ رسیدیم باید از آنجا به بعد کلمات انگلیسی کوچک را به بزرگ تبدیل کنیم (و این کار را تا آنجایی ادامه میدهیم که به ۳ برسیم) ، و هرجا به ۲ رسیدیم از آنجا به بعد کلمات بزرگ انگلیسی را به کوچک باید تبدیل شوند (و این کار را تا آنجایی ادامه میدهیم که به ۴ برسیم)
اگر بین ۱ و ۳ در کاراکترها ۲ و ۴ ای وجود داشته باشد، کاراکتر های بین ۲ و ۴ باید به حروف کوچک انگلیسی تبدیل شوند و کاراکترهایی که بین ۱ و ۳ هستند ولی بین ۲ و ۴ نیستند باید به حروف بزرگ انگلیسی تبدیل شوند
سوال دوم فهمش یکم سخته! چند بار از روش بخونید شاید فهمیدید !
۱۳۸۹/۰۳/۰۵ · ۱۹:۳۰
آزمون مقدماتی برنامهنویسی + برنامهنویسی + سوال
سلام بچهها! حالتون خوبه؟ ما هم خوبیم. خداروشکر!
این پست در موردآزمون مقدماتی برنامه نویسیاست. قبول دارم یه کم دیر این پست رو میزینم. راستش ما، هم درگیر امتحان نهایی هستیم هم منتظر بودیم تا کمیته نوع و سطح سوالات این امتحان رو معلوم کنه بعد پست بزنیم اما فعلا خبری نیست. قراره وقتی کمیته درمورد نوع سوالات و نحوه امتحان تصمیم قطعی گرفت، توضیحاتش رو تو سایتhttp://www.inoi.irبذاره. ما هم اگه خبردار شدیم اینجا مینویسیم. حالا فعلا تو این پست یه سری توضیحات کلی درمورد آزمونهای برنامه نویسی و خود برنامه نویسی مینویسم تا ببینیم چی میشه.
------------------------------------------------------------------------------------------------------
به طور کلی تو امتحانهای برنامه نویسی شما مثلا ۵ ساعت وقت دارید و به شما چندتا سوال داده میشه که هر کدوم به این شکل هستند:
برنامه ای بنویسید که از ورودی استاندارد (همون صفحه کلید) ورودی مسئله را بخواند و با توجه به صورت سوال خروجی برنامه را محاسبه کند و آن را در خروجی استاندارد (همون صفحه نمایشگر) چاپ کند! (میبینید که چقدر سوالها ساده است!)
این لینک۳ تا سوال برنامه نویسی به زبان فارسی داره که البته سوالاش خیلی سخته و امتحان شماخیلیاز این آسونتر خواهد بود. این لینک رو گذاشتم فقط برای اینکه ببینید قالب کلی سوال ها چیجوریه. (راستش لینک دیگهای دم دستم نبود که سوالهاش فارسی باشه).
زمان ما همه امتحان ها تو linux بود اما از سال ما به بعد تو دوره تابستون با بچهها تو windows کار میکردن و تو دوره نقره-طلا بهشون linux یاد میدادند. احتمالا این امتحان شما هم توی windows هستش. برنامههاتون رو هم باید به زبان ++C بنویسید.
------------------------------------------------------------------------------------------------------
اما درمورد برنامه نویسی. من اول میخواستم بیام یه کم مقدمات برنامهنویسی رو توضیح بدم ولی دیدم تو وبلاگ خیلی سخته. اما به طور کلی اگه شما میخواید برنامه نویسی رو از صفر شروع کنید بهتره از یکی که بلده بخواید بهتون مقدماتش رو یاد بده. منظورم اینه که اگه بخواید خودتون از رو کتاب یا با اینترنت یاد بگیرید خیلی وقتتون رو میگیره و بهتره که یکی (مثلا یکی از دوستاتون یا یکی از معلمهاتون) پای کامپیوتر مقدماتش رو بهتون یاد بده. اما اگه چیزای اولیه رو بلدید، دیگه باید کمکم خودتون بقیه چیزها رو با اینترنت و کتاب یاد بگیرید. یعنیبایدیاد بگیرید که چگونه از کتاب و مخصوصا اینترنت جواب سوالهاتون رو پیدا کنید. در مورد ++C هم سایت فتوفراوونه که اینجا دوتا از خوباش رو میگم(البته به نظر من خوبن):
سایتwww.cppreference.com: یکی از سایتهای خوبه که توش در مورد کتابخونهها و چیزای دیگهی ++C خیلی خوب و مختصر توضیح داده.
سایتhttp://www.cplusplus.com: توش هم یه بخش داره برایآموزشهم یهمرجع برای کتابخانههای ++Cداره، هم یهforumداره که توش میتونید سوال بپرسید.
معمولا تو امتحانها یه مرجع ++C در اختیار مسابقهدهندهها هست. مثلا تو جهانی پارسال و توی امتحان انتخاب تیم امسال همین سایتwww.cppreference.comبه عنوان مرجع در طول امتحان در اختیار مسابقهدهندهها بود. (البته این به معنی دسترسی به اینترنت نیست. بلکه صفحههای این سایت روی کامپیوتر ذخیره شده و ملت میتونن ازش استفاده کنن). تو این امتحانها یه PDF هم بود که برای آموزش ++C بود واینجابراتون آپلودش کردم (به نظرم این PDF همونقسمت آموزشی http://www.cplusplus.comهستش که به صورت PDF در آوردنش).
یه نکته مهم در مورد ++C، کتابخانه STL هست. این کتابخونه توش هم یه سری تابعبسیاربه درد بخور داره و هم یه سری ظرف (ترجمه container!) . این توابع و ظروف! اینقدر زیادن که من بعد عمری! کار کردن با این کتابخونه هنوز توش چیزای جدید پیدا میکنم. البته اگه این اسمها براتون جدیده اصلا نگران نشید. چون به نظرم خیلی بعیده تو این امتحان سوالی بدن که نیاز به استفاده از این ها مخصوصا container ها داشته باشین. اما به نظر من درمورد تابعمرتبسازیاین کتابخونه اگه استفاده ازش رو بلد باشین خیلی خوبه. از اسمش معلومه که چیکار میکنه و احتمالا خودتون هم میتونید بدون استفاده از STL این تابع رو بنویسید، ولی به هرحال یاد گرفتنش خیلی کارو راحت تر میکنه. اسم این تابعsortهستش و نحوه استفادهاش اینطوریه:
فرض کنید شما یه آرایه از اعداد (مثلا از نوع int) به اسم num دارید که توش n تا عدد ذخیره کردید و حالا میخواید اعدادش رو مرتب کنید. کافیه از تابعsortبه شکل زیر استفاده کنید:
sort(num, num + n); // num esme arayatoone va n tedad adade tooshe.
شاید تو پستهای دیگه در مورد سایر توابع پرکاربرد STL هم نوشتیم. خب این هم درمورد برنامهنویسی و STL. وقتی معلوم شد که امتحانتون چیجوریه و در چه سطحی باید الگوریتم بلد باشید، احتمالا در مورد الگوریتمها هم پست بذاریم. اما فعلا یه سوال برنامه نویسی میگم(از کتاب مسئله های الگوریتمی) که روش فکر کنید.
------------------------------------------------------------------------------------------------------
کتاب مسئلههای الگوریتمی، مسئله ۸۰. متوسط زمان پاسخ یک ماشین:
n کار را میخواهیم روی یک ماشین اجرا کنیم. اجرای کار شماره i به اندازهی tiزمان میگیرد. ماشین در هر لحظه حداکثر میتواند یکی از کارها رو انجام دهد. برنامهای بنویسید که ترتیبی برای اجرای این کارها پیدا کند، به طوری که متوسط زمان پایان یافتن کارها مینیمم شود.
ورودی: در سطر اول ورودی n و در سطر بعدی tiها نوشته شدهاند. فرض کنید n iها صحیح و مثبت اند.
خروجی: در سطر اول فایل خروجی متوسط زمان پایان یافتن کارها و در سطر دوم ترتیب انجام کارها رو بنویسید.
مثال:
ورودی نمونه:
5
34 23 52 13 42
خروجی نمونه:
79
4 2 1 5 3
------------------------------------------------------------------------------------------------------
اگه حلش کردید کدش رو هم بزنید. خب دیگه من باید برم فیزیک بخونم!
موفق باشید
فعلا خداحافظ!
۱۳۸۹/۰۲/۳۱ · ۰۸:۴۲
تیم ملی المپیاد کامپیوتر ایران
بعد از چند دوره امتحانات طاقت فرسا و تنگاتنگ! و خداحافظی با بقیه شرکت کنندگان در مراحل مختلف ، بالاخره تیم ملی المپیاد کامپیوتر برای شرکت درالمپیاد جهانی که توی واترلوی کانادابرگزار می شه ، انتخاب شد!
اعضای تیم ، به ترتیب الفبا اینا هستن:
1- علی بابایی چشمه احمد رضایی - علامه حلی تهران!
2- سید مهران خلدی - علامه حلی تهران!
3- بهروز ربیعی - علامه حلی تهران!
4- مهرداد طهماسبی - علامه حلی تهران!
به همه شون تبریک می گم و امیدوارم موفق باشن. (واسه من هم تی شرت یادشون نره بیارن!)
به کسایی هم که توی مراحل مختلف بودن و باهاشون خداحافظی شد خسته نباشید میگم!
به دوستانی هم که جایی غیر از علامه حلی هستن ، می گم که نا امید نشین! امسال استثنائی بود.
۱۳۸۹/۰۲/۲۱ · ۲۴:۳۹
کلید جدید
اینم کلیدی که قول داده بودم... (با کمک بهروز)
سوال ۱:
حقوق هر فرد را در وضعیتی که iنفر در شرکت اول بروند Pi و در وضعیتی که به شرکت دوم بروند Fi می نامیم... برهان خلف می زنیم... فرض کنیم وضعیت جواب نداریم
اگر nنفر به شرکت اول بروند، F1 > Pn است، (وگرنه وضعیت جواب بود)، حالا اگر n-1 نفر به شرکت اول بروند Pn-1
تناقض است. پس این بین یکی از نامساوی ها غلط بوده و حالت جواب بوده.
//=================================================
سوال ۲:
گراف جایگشت را می کشیم،طوری که از i به πi یالی جهت دار می کشیم. گراف افرازی از چند دور است. در هر عمل طول هر دور نصف می شود، (چرا ؟) پس از k مرحله همه دور ها طولشان یک می شود.
ب) جایگشت 2, 3, 4, ..., n-1, n, 1را در نظر بگیرید و پس از هر مرحله جای یک را بررسی کنید...
//==================================================
سوال ۳:
الف) درخت را از یک راس آویزان می کنیم،حالا پایین ترین یال خراب (یالی که عوارض دو سرش یکسان شده اند) را در نظر بگیرید (و آن را uv بنامید، طوری که u پدر v باشد.) یکی از بچههای v مانند w را انتخاب میکنیم. عوارض یال vw را عوض میکنیم. با این حساب uv دیگر خراب نیست. از طرفی ممکن است چند یال مانند vx یا wy خراب شده باشند. (که همگی پایینتر از uv هستند.) ، و ... استقرا
پایهی استقرا: برگ. چون عوارض صفر نداریم، ...
ب) *ها شهرها هستند. عوارض جادهها درون پرانتز نوشته شده است.
*-(a,b)-*-(0,1)-*-(a,b)-*-(0,1)-*-(a,b)-*
بررسی کنید.
//==================================================
سوال ۴:
یک «وضعیت» را برای مسئله اینگونه تعریف میکنیم:
«جادهی خروجی هر میدان کدام است؟ و ما کجا هستیم؟»
واضح است که تعداد حالات متناهی است. پس اگر از وضعیت ابتدایی شروع کنیم، بعد از طی چند مرحله به یک وضعیت تکراری برمیگردیم. دور حاصل از وضعیتها (در گراف وضعیت) را در نظر میگیریم. ادعا میکنیم با پیمودن این دور، از همهی شهرها گذشتهایم.
برهان خلف: شهری را در نظر بگیرید که در گراف وضعیت بازدید شده باشد و دارای حداقل یک همسایهی بازدیدنشده باشد. (آن را v بنامید) این دور را d_v (تعداد همسایههای v) بار طی میکنیم. حتما یک بار پلیس جادهی منتهی به شهر بازدید نشده را باز میکند. تناقض...
//==================================================
سوال ۵:
توضیح بیشتر در مورد الگوریتم داده شده:
در ابتدا n دستهی ۱ عضوی داریم. هر بار، دو دستهی دلخواه را انتخاب میکنیم، و همهی اعضای دستهی کوچکتر را در دسته بزرگ میریزیم و به اندازهی تعداد اعضای دستهی کوچک پول خرج میکنیم (به b اضافه میکنیم)
الف) در هر مرحله، اگر x دسته داشته باشیم، به x/2 تا دسته ۲تایی تقسیم میکنیم. و دو به دو با هم تلفیق میکنیم.
ب) هر عدد حداکثر در k عملیات جابهجایی شرکت داشته. (چرا؟) پس در کل k * 2^k تا عمل انجام شده.
(برای اطلاعات بیشتر در مورد کاربرد این الگوریتم، در مورد دادهساختار DisjointSet تحقیق کنید. منابع: ویکیپدیا، CLRS، Creative و JBL)
[پس از بررسی حل خود برای تخمین بهتر کف حتما در نظرسنجی شرکت کنید.]
۱۳۸۹/۰۲/۰۸ · ۲۴:۰۰
کلید مرحله ۲
مرحله دوم خوب بود ؟ من که به شخصه خیلی خوشم نیومد .
من یه کلید به سرعت در اوردم امیدوارم درست باشه.
سوال مربع و ۱۳۸۹ پارهخط میشه ۴۱۶۸
سوال ۲۰۱۰ عدد کمتر از ۲ به توان ۱۳۸۹ میشه ۱۳۹۹
سوال ۲۰ سکه ی طلا میشه ۱۰
سوال مکعب ۳*۳*۳ میشه ۶
سوال اشباع شده میشه 42
سوال سکه ها و پرتاب میشه ۱/۸
سوال مربع ۳*۳ میشه ۹ تا
سوال پست خونه میشه ۳۶ تا .
سوال n سکه میشه ۱۳۹۱
سوال مرتب کردن سکه میشه ۵ تا
سوال دزد و تابلو ها میشه p(i)=max(vi+p(i-2),p(i-1)) in
سوال دانشجو و استاد میشه ۶
سوال راننده و جا ی پارک میشه ۱،۳،۲۹۹
سوال الگریتم s و b میشه ۷
سوال لیگ فوتبال میشه ۹
سوال طرح سوال میشه ۱۶۸
سوال الگوریتم رو a1 a2 a3 a4 میشه ۲۶
سوال مقدار کمینه s میشه ۳۵
سوال ۶ لامپ میشه ۲۹
۱۳۸۹/۰۲/۰۷ · ۱۶:۴۵