صفحه ۲۹
چند تا سؤال
(راهنمایی: استقرا خیلی خوبه)
۲- ثابت کنید بین هر ۳۹ عدد متوالی، میتوان عددی را پیدا کرد که مجموع رقمهای آن بر ۱۱ بخشپذیر باشد.
(راهنمایی: لانهی کبوتری هم خیلی خوبه)
۳- n فوتبالیست با شمارههای ۱ تا n، و n صندلی با شمارههای ۱ تا n وجود دارد. با هر سوت مربی،
n نفر به صورت کاملا تصادفی روی صندلیها مینشینند و مربی تعداد افرادی
که روی صندلی با شمارهی خودشان نشستهاند را یادداشت میکند. این آزمایش
را به دفعات زیاد تکرار میکند. میانگین تمام اعداد نوشته شده چه عددی
خواهد بود؟
(راهنمایی: عدد مورد نظر، برابر میانگین تمام اعداد یادداشت شده به ازای جایگشتهای مختلف افراد است.)
۴- n جعبه داریم. در جعبهی i-ام aiکیلو سیب، biکیلو گلابی وجود دارد. ثابت کنید میتوانیم با برداشتن[n/۲]+۱تا از جعبهها را برداریم، که حداقل نیمی
از [کل] گلابیها و حداقل نیمی از [کل] سیبها را برداشته باشیم.
(راهنمایی: استقرا همیشه آسونترین راه نیست)
۵- قرار شد تیم المپیاد کامپیوتر جهانی امسال ۳-نفره
باشد و
مسئولین کمیته برای موفقیت هر چه بیشتر تیم، به فکر افتادهاند. آنها بعد
از بررسیهای بسیار، و مشاوره با نویسندگان شاززز، توانستند شرط لازم و
کافی برای موفقیت تیم را کشف کنند: «تعداد دوستان هر فرد (از ۳ نفر تیم، و
در بین تمامی شرکتکنندگان) باید با تعداد دوستان ۲ نفر دیگر برابر باشد.»
بعد از تلاشهای بسیار، و با اجرای الگوریتمهای پیچیده، کمیته به این
نتیجه رسید که امسال به هیچ وجه تیم جهانی المپیاد کامپیوتر نتیجهی خوبی
نخواهد گرفت و به همین دلیل تصمیم گرفته المپیاد کامپیوتر را منحل کند. با
دانستن تعداد شرکتکنندگان، یک نحوهی دوستی ممکن بین افراد را بیابید.
(دوستی رابطهی دوطرفه است.)
(راهنمایی: فهمیدن سؤال نصف سؤاله!)
۱۳۸۹/۰۸/۰۵ · ۰۸:۵۴
سفرنامهی IOI ۲۰۱۰ (المپیاد جهانی کامپیوتر سال ۲۰۱۰)
به نام خدا
سلام بچهها! خوبین؟
اگه منو نمیشناسید من علی بابایی یکی از «نویسندگان سابق» این وبلاگم (چقدر زود پیر شدیم!). معمولا وقتی یه نویسنده «سابق» میشه دیگه چیزی نمینویسه. من هم قصد سنتشکنی نداشتم، ولی چون قبلا قول داده بودم سفرنامهی IOI رو بنویسم، این پست رو زدم.
این سفرنامه، در مورد سفر تیم المپیاد کامپیوتر ایران به IOI 2010 است. ایدهی نوشتن سفرنامه قبل از رفتن به IOI تو ذهنم بود. بعدش که برگشتیم تا یه مدت وقت نکردم درستش کنم. الان یه چند وقتیه شروع کردم و قسمت اولش آماده شده.
قبل از شروع سفرنامه چندتا نکته:
-تو این مدتی که داشتم سفرنامه رو آماده میکردم، این سوال که «این سفرنامه به درد شما میخوره یا نه» مدام میاومد سراغم و جواب قانع کنندهای براش پیدا نکردم. کلا برای خود من نوشتن همچین چیزی به درد بخوره اما نمیدونم خوندنش به درد شما میخوره یا نه!
-اولش فکر میکردم که کل سفرنامه رو میشه تو ۵-۶ صفحه و تو یه پست نوشت. ولی وقتی شروع به نوشتن کردم، دیدم همین تیکهی اولش خودش کلی شد. برای همین تصمیم گرفتم که به صورت چند قسمت بنویسمش و اینجا بذارم. از همین اول هم بگم که ممکنه زمان بین گذاشتن قسمتها طولانی بشه! ولی سعیم رو میکنم که زود تمومش کنم.
-احتمالا از قسمتهای بعدی عکس هم میذارم و چون کار کردن با editor وبلاگ برای گذاشتن عکس و ... سخته، ممکنه که بقیهی قسمتها رو تو یه صفحهی دیگه درست کنم و اینجا فقط لیکش رو بذارم.
قسمت اول سفرنامه در مورد وقایعیه که قبل از سفر برامون اتفاق افتاد. برای خوندن این قسمت روی «قسمت اول» کلیک کنید. برای نوشتن این قسمت، یه سری ایده هم بهروز داد که ازش تشکر میکنم.
۱۳۸۹/۰۷/۲۷ · ۰۸:۳۰
نویسندههای جدید
۳ نویسندهی جدید به جمع نویسندههای شاززز اضافه شدن، برای اینکه تعداد پستها زیاد نشه همه رو یه جا معرفی میکنم:
حسین شایسته، علامهحلی تهران، طلای دورهی ۲۰ کامپیوتر
نازنین علیپور، فرزانگان تهران، طلای دورهی ۱۹ کامپیوتر
محمد زابلیان، شهید اژهای اصفهان، طلای دورهی ۱۹ کامپیوتر
۱۳۸۹/۰۷/۱۵ · ۱۶:۳۶
Hello World
من سید مهران خلدی هستم، از بچههای دورهی ۱۹ کامپیوتر، و قرار شده به عنوان نویسندهی جدید شاززز در خدمتتون باشم.
امیدوارم بتونم کمک کنم
بهروزرسانی:احتمالا چند تا صفحهی جداگانه قراره برای وبلاگ آماده بشه، احتمالا اولیش «ویکیشازززیا» هستش که قراره در مورد منابع المپیاد و یه سری توصیه و اینجور چیزها باشه. اما قبلش لازم بود یه تغییراتی روی قالب اجرا بشه (نترسید، قالب تغییر محسوسی نمیکنه، صرفا یه مقدار با سرویسهای جدید بلاگفا سازگار میشه) برای همین ممکنه یه کم وقت بگیره.
بهروزرسانی:خب، بازنویسی قالب هم تموم شد. الآن قالب از صفحات جداگانه هم پشتیبانی میکنه. سمت راست وبلاگ، توی بخش پیوندها، یه لینک به نام «لیست صفحات جداگانه» وجود داره. روی اون کلیک کنید تا لیست این صفحات رو ببینید. این صفحات، صفحاتی هستن که چون احتمالا در آینده هم قراره زیاد تغییر بکنند، از بقیه جدا شدن. اولین صفحهی جدا هم با اسم «ویکیشازززیا» قرار داده شده. توضیحات بیشتر رو همونجا بخونید. خب دیگه، من خسته شدم، یه مدت کمتر فعالیت میکنم.
بهروزرسانی:صفحهی تغییرات اضافه شد. میل جدید شاززز راهاندازی شد. (توضیحات بیشتر در صفحهی تغییرات)
۱۳۸۹/۰۷/۰۹ · ۱۴:۲۹
سالی دیگر.. طلاهایی دیگر
| نام | نام خانوادگی | توضیحات |
| سجاد | جلالی | شام بچههای شاززز فراموش نشود |
| محمد حسین | سخاوت | |
| پارسا | سعادت پناه | |
| حسین | شایسته | شام بچههای شاززز فراموش نشود |
| حامد | صالح | دوم دبیرستان |
| کسری | عدالت نژاد | شام بچههای شاززز فراموش نشود |
| محمدرضا | کسنوی | شام بچههای شاززز فراموش نشود |
| محمدرضا | ملکی | دوم دبیرستان |
۱۳۸۹/۰۶/۲۵ · ۱۹:۳۵
جواب پست قبلی
یا حق
سلام به همه رفقا.
شرمنده به خاطر تاخیر تو پست زدن. این جواب سوالهای پست قبلیه:
۱- برای اینکه ببینیم چندتا جایگشت رو میشه مرتب کرد، تعداد جایگشتهایی که از جایگشت مرتب شده میشه به اونها رفت رو میشماریم. اگه جایگاههای 1 تا n رو به عنوان راس و هر کارت رو به عنوان یک یال در نظر بگیریم، به یک گراف میرسیم. حالا تو این گراف هر دو راسی که تو یک مولفه باشند رو میشه جابجا کرد، بدون اینکه بقیه رئوس رو به هم بریزیم. پس در واقع هر مولفه از این گراف رو میتونیم به هر شکلی جایگشت بدیم. پس اگه این گراف k تا مولفه با اندازههای a1تا akداشته باشه، جواب مسئله میشه:
a1! * a2! * ... * ak!) % 1000007)
بنابراین کافیه با یهDFSاندازه مولفهها رو در بیاریم و عبارت بالا رو محاسبه کنیم.
۲- فرض کنید با تعدادی حرکت دنباله رو مرتب کردیم. عناصری رو در نظر بگیرید که در هیچ مرحلهای حرکت داده نشدهاند. این عناصر باید تشکیل یک زیردنبالهی صعودی بدهند. از طرفی اگر یک زیر دنبالهی صعودی را در نظر بگیریم، با جابجا کردن بقیه عناصر میشه دنباله رو مرتب کرد. پس مساله تبدیل میشه به پیدا کردن طولانیترین زیردنبالهی صعودی که اختصارا بهش میگنLIS. برای این مساله یه راهحل داینمایک از (O(n^2 وجود داره که با یه ایدهی جالب میشه به (O(n * log n کاهشش داد.
میخواستم برای این دوتا سوال تستدیتا درست کنم ولی وقت نشد. اما توصیه میکنم که کدهاشون رو بزنید. راهحل ها رو خیلی مختصر توضیح دادم، اگه چیزی رو نفهمیدید تو نظرات بپرسید. (بلاخره باید یه جوری آمار نظرها بالا بره!).
----------------------------------------------------------------------------------
چند وقت پیش تصمیم گرفته بودم که از المپیاد جهانی امسال یه چیزی تو مایههای سفرنامه بنویسم و تو شاززز بذارم. الان دو-سه روزه که برگشتیم و وقت نشده کاری بکنم. از طرفی ما باید به زودی این وبلاگ رو بدیم به دست سال پایینیها. برای همین نمیدونم وقت بشه که پست دیگهای بزنم یا نه. حالا اگه وقت شد سفرنامه رو بنویسم و اینجا بذارم که خب هیجی(یعنی فعلا در خدمتیم) وگرنه اگه خوبی-بدی دیدید حلال کنید.
فعلا خداحافظ!
(پی نوشت: دمه افطاره. از همه دوستان التماس دعا)
۱۳۸۹/۰۶/۰۶ · ۱۵:۰۹
سوال
با یاد خدا،
سلام بچهها؟ خوبین؟
یه چند وقتی بود اینجا سوت و کور شده بود. برای همین تصمیم گرفتم دوتا سوال برنامه نویسی بذارم. سطح سوالها متفاوته. ولی در مجموع در حد امتحانهای عملی دوره تابستون هستند. زمان ما (یادش بخیر) امتحانهای عملی دوره تابستون ۲ تا سوال بود با ۵ ساعت وقت. فکر کنم دوره تابستون امسال هم همینجوری بود. برا همین میتونید این دوتا سوال رو مثل یه امتحان تو ۵ ساعت حل کنید.
اگه نتونستید سوالها رو حل کنید ناامید نشید. این سوالها نسبت به سوالهای مرحله ۳ (امتحان برنامه نویسی قبل دوره تابستون)، الگوریتمیتر و بالطبع سختتر اند. اگه از الان شروع به تمرین کردید که سال دیگه وارد دوره بشید توصیه میکنم که کنار مباحثی مثل ترکیبیات و گراف، حتما الگوریتم و برنامه نویسی رو هم کار کنید. خصوصا اینکه امتحان مرحله ۳ هم اضافه شده و علاوه بر اون تکلیف مدالها تو تابستون معلوم میشه و برای همین بار عملی دوره تابستون هم بیشتر شده. خب دیگه پند و اندرز بسه. اینم سوالها:
-------------------------------------------------------------------------------
سوال ۱: مرتب سازی۱.
خیکوله قرار است یک جایگشت از اعداد ۱ تا n را مرتب کند. برای این کار او از یک ماشین مرتبسازی کمک میگیرد. این ماشین به این شکل کار میکند که در ورودیاش یک کارت که روی آن دو عدد a و b نوشته شده است قرار داده میشود. سپس ماشین جای عنصر aام و عنصر bام جایگشت را عوض میکند. مثلا اگر جایگشت کنونی باشد و در ورودی کارت (4, 5) را قرار دهیم، جایگشت به این شکل در میآید: .
به خیکوله m تا کارت داده شده است. او میخواهد بداند با کارتهایی که دارد چندتا جایگشت از اعداد ۱ تا n را میتواند مرتب کند؟ او میتواند از هر کارت به تعداد دلخاوه استفاده کند.
ورودی: در خط اول n و m آمده. در m خط بعدی اعداد روی کارتها آمده است.
خروجی: در تنها سطر خروجی یاقیماندهی جواب مساله را بر ۱۰۰۰۰۰۷ چاپ کنید.
محدودیتها: (n , m
-------------------------------------------------------------------------------
سوال ۲: مرتبسازی۲.
این بار خیکوله با یک مسالهی مرتبسازی دیگر مواجه شده است. به او یک دنبالهی n تایی از اعداد صحیح دادهاند و از او خواستهاند که این دنباله را مرتب کند. برای این کار او میتواند در هر مرحله یک عدد از دنباله را برداشته و به هر جای دیگر از دنباله منتقل کند. مثلا برای مرتب کردن دنبالهی او میتواند در یک حرکت عدد ۵ را از ابتدای دنباله به انتهای آن ببرد.
خیکوله میخواهد بداند برای مرتب کردن دنبالهی داده شده حداقل چند حرکت نیاز دارد؟
ورودی: در خط اول n و در n خط بعدی اعداد دنباله به ترتیب آمدهاند.
خروجی: در تنها سطر خروجی حداقل تعداد حرکت مورد نیاز برای مرتب کردن دنبالهی داده شده را بنویسید.
محدودیتها: در ۷۰ درصد تستها n
-------------------------------------------------------------------------------
محدودیت زمان برای هردوتا سوال ۱ ثانیه هست. یعنی برنامهتون باید کمتر از یک ثانیه تموم بشه. حافظهای هم که میتونید بگیرید حداکثر ۱۶ مگابایته.
-------------------------------------------------------------------------------
سوال اول رو خودم طرح کردم. سوال دوم رو هم یه جایی دیده بودم. به نظر خودم سوالهای خوبیاند. اگه حلشون کردید توصیه میکنم کدش رو هم بزنید. ورودی، خروجی و محدودیتها رو دقیق گفتم که اگه وقت شد تستدیتا براشون درست کنم تا بتونید کدهاتون رو جاج کنید (یعنی برنامهتون رو تست کنید و بهش نمره بدید). خب دیگه! نصف شب شد! من برم بخوابم.
شب خوش!
۱۳۸۹/۰۵/۱۶ · ۲۱:۱۸
دل نوشته ها!
سلام ، خوبین؟ چه خبرا؟ زندگانی خوب پیش میره؟
چند وقت بود که می خواستم دیدگاهام رو در مورد المپیاد بهتون بگم.گفتم شاید واستون جالب باشه که بعد از دو سه سال که درگیر المپیاد بودم ، بدونین نظرم در این مورد چیه.( اگه واستون جالب نیست ، ادامه ی مطلب رو نخونین! )
اول ، به زبان ساده اگه بخوام المپیاد رو ترسیم کنم، این شکلیه:یه سری مسابقات جهانی به اسم المپیاد برگزار می شه.خب ما ایرانیا هم باید تیم بفرستیم به این مسابقات دیگه.خب الان می خوایم یه تیم انتخاب کنیم که برن واسه مسابقات.سبک مسابقات ببینیم چه شکلیه.خب به هوش و خلاقیت و بلد بودن یه مباحثی نیاز داره.پس بیایم یه امتحان برگزار کنیم و از بین دانش آموزا یه سری رو انتخاب کنیم برای تیم.اونا که این مطالبو بلد نیستن ، پس یه امتحان می ذاریم که کسایی که یه چیزایی بلدن و خلاقیت هم دارن انتخاب شن بیان براشون کلاس بذاریم و بعد بفرستیم جهانی.یه امتحان خیلی درصد خطاش زیاده و ممکنه افراد شایسته تری باشن و انتخاب نشن.واسه این همه داوطلب هم که نمی شه یه عالمه امتحان گذاشت.پس بیایم یه تعداد بیشتری (30 الی 40 تا ) انتخاب کنیم و کلاس بذاریم و تعداد زیادی امتحان بگیریم تا بهترین ترکیب واسه تیم مشخص شه .(بالاخره دوست داریم تیممون که میره جهانی بهترین نتیجه ممکن رو بگیره دیگه)برای انتخاب این 30~40 نفر هم ، چون داوطلبا خیلی زیادن ، نمی شه امتحان تشریحی گرفت ، امتحان تستی هم خیلی مناسب نیست ، پس اول یه امتحان تستی می ذاریم و بعد از منتخب ها یه امتحان تشریحی می گیریم.
خب الان فرض کنید با یه سری امتحان از این 30~40 نفرتیم مشخص شد. این بچه ها باید کلاس داشته باشن تا قوی بشن واسه مسابقات.بعد هم باید اعزام بشن و برن جهانی.خب پس کی اینا کنکور بخونن؟!درسته که بچه های خیلی با استعدادی هستن ، ولی خب وقتی کنکور نخونن ، چیزی نمی شن تو کنکور دیگه!(و تنها مجرای رفتن به دانشگاه کنکوره) پس بیاین معافشون کنیم از کنکور.یعنی می گیم آقا جون ، تو بیا وقتت رو بذار واسه تیم ، کنکورت با ما!(واسه اینکه باز هم درصد خطای انتخاب تیم کمتر شه ، دو برابر تعدادی که واسه تیم می خوایم رو انتخاب می کنیم و اسمشون رو می ذاریم طلا و از کنکور معافشون می کنیم و به بقیه هم چون تابستونشون رو گذاشتن واسه این کار و از کنکوریا عقب افتادن یه سهمیه می دیم که جبران بشه)
به همین سادگی! این بود نحوه ی به وجود اومدن المپیاد از نظر من.
اما ببینیم از بیرون چه شکلیه! :
اول کار بچه ها بیشتر واسه ی علاقه وارد المپیاد می شدن. مثلا یادمه راهنمایی که بودیم ، یه سری کلاسهایی توی تابستون می ذاشتن به اسم کارسوق ریاضی. حدود سه شبانه روز یه سری از بچه های اصفهان و یزد و قزوین و کرج و…که با آزمون ورودی انتخاب شده بودیم ، دور هم جمع می شدیم و یه سری کلاس و کارگاه داشتیم. توی کلاسا مباحثی مطرح می شد که عموما مربوط به المپیاد ریاضی و کامپیوتر بود ، بدون اینکه اسمی از المپیاد برده بشه. خب من و خیلیای دیگه از این چیزا خیلی خوشمون میومد و دنبال می کردیم ( حتی در حد همون 3 روز ) بدون اینکه هدفی برای شرکت تو المپیاد داشته باشیم. اصلا اون موقع فکر می کردیم این المپیادی های مدال آور که تو تلویزیون نشون می ده ، یه سری آدم عجیب و خفن و خارق العاده و خرخون که هیچ چیز غیر درس خوندن بلد نیستن و…هستن! ( ولی الان فهمیدم یه سری آدم معمولی هستن مثه خودم‼)
البته منظورم این نیست که الان بچه ها بی علاقه یا زوری وارد المپیاد می شن. (البته چنین مواردی هم وجود داره)
اما این رو می بینیم که برای خیلی ها مهم ترین هدف شده طلا شدن و معافی از کنکور. نتیجه اش می شه چی؟ اینکه کسایی که به این هدفشون نمی رسن ، احساس شکست می کنن و ناراحت و شاید حتی افسرده می شن.
به نظر شما آیا این هدف برگزاری المپیاد بوده؟! هدف ایجاد نشاط علمی بوده یا ناراحتی طولانی مدت یه عده ی زیادی از دانش آموزا؟
بله ، این رو قبول دارم که بالاخره ذات انسان کمال طلبه و دوست داره همه جا موفق باشه. و طبیعتا اگه کسی توی هر یک از مراحل موفق نشه ، ناراحت می شه. اما این ناراحتی باید زود گذر باشه ، باید همراه با عزمی بیشتر برای کسب موفقیت توی زمینه دیگه باشه. به نظر شما فرق این دو نفر ، بعد از این که مرحله 2 قبول نشدن چیه ، قضاوت با خودتون! :
نفر اول از وقتی فهمیده اگه طلا بشه کنکور معاف می شه ، شروع کرده المپیاد می خونه ، سر بعضی کلاسها هم نمی ره ، چون می خواد حتما طلا بشه. همه فکر و ذکرش شده المپیاد و خیلی هم زحمت می کشه. شبا خواب طلا می بینه! اما توی مرحله 2 به هر دلیلی موفق نمی شه…
نفر دوم ، المپیاد کامپیوتر رو دوست داره. کنار درسای مدرسه اش المپیاد می خونه . بعد از مدتی می بینه استعدادش رو هم داره و کم کم اگه درسی هست که خیلی نیاز به کلاس نداشته باشه ، نمیره سر کلاسش و عزمش رو برای شرکت توی مرحله 1 و 2 جزم می کنه! سر همه امتحانا هم با خودش می گه ، من که تلاش خودم رو کردم ، ایشالله هر چی صلاحمه اتفاق بیفته. چون دوست نداره اتفاقی براش بیفته که حتی اگه در ظاهر خوبه ، در آینده به ضررش باشه. این هم توی مرحله 2 به هر دلیلی قبول نمی شه…
این همه حرف زدم که بگم ، عزیزان من! این مباحث المپیادی رو اگه دوست دارین ، واسه خودش بخونین. هدف اصلیتون المپیاد و معافی و…نباشه! شما حتی اگه مدال هم نگیرین ، هیچ ضرری نکردین. المپیاد کامپیوتر و کلا سوال حل کردن ذهنتون رو باز می کنه. دید خوبی بهتون می ده که بعدها خیلی بهتون کمک می کنه. (حتی مباحث شمارشی که یاد می گیرین توی درس جبر سوم و گسسته ی پیش کمکتون می کنه)
این رو هم بدونین ، که چون معمولا کسایی که طلا می شن ، درس مدرسه رو بی خیال می شن (به خاطر دوره تیم) خیلی توی ریاضی و فیزیک ضعیفن (مخصوصا کامپیوتری ها) و توی دانشگاه از کنکوری ها کم میارن! مسلما موفقیت توی دانشگاه مهم تر از دبیرستان یا پیچوندن یه کنکوره! اینم که می گن برای طلاها دعوتنامه میاد و رو هوا می زننشون! و…همش کشکه! از طلا جهانیا هم که پرسیدم ، گفتن واسشون دعوتنامه نیومده و توی پذیرش گرفتن از دانشگاههای خارجی هم عملکردشون توی دانشگاه خیلی مهم تر از مدال جهانیشون بوده. ( در واقع مدال جهانی هم حتی خیلی تاثیری در پذیرش گرفتن از دانشگاههای خارجی نداره ) این رو گفتم که بدونید طلا گرفتن ، صرفا می تونه توی دور زدن کنکور کمک کنه و ممکنه مشکلاتی هم ایجاد کنه!
در پایان! اگه هدف اصلیتون پیچوندن کنکوره ، اشتباه اومدین! بهتره برگردین از اول شروع کنید.
پی نوشت 1: من این پست رو یه هفته پیش نوشته بودم ، ولی بکاپ نگرفته بودم و مشکل پیش اومد و پرید! (البته چیزی که اون موقع نوشته بودم یه کم فرق داشت ، شاید قسمت بود که یه چیزایی رو نگم و یه چیزای دیگه بگم! ) الان ساعت 1:30 نصفه شبه دارم اینو می نویسم فردا هم 6 صبح قراره با بچه ها بریم کوه! چه طوری بیدار شم حالا؟‼
پی نوشت 2: اگه غلط املائی یا انشائی دیدین تو متن ، بگین تا درستش کنم!
۱۳۸۹/۰۴/۱۳ · ۱۹:۳۰