صفحه ۲۱
راهنماییهای تعدادی از سوالهای سری ۱ و ۲
برای چندتا از سوالهای سری ۱ و ۲ تمرینها یه خرده راهنماییای آماده کردیم. تا اگه با حل کردن سوالا مشکل داشتید کمکتون کنه.
راه حلهایی که سبحان آماده کرده
راه حلهایی که دانیال آماده کرده
و این هم من آماده کردم D:
تعداد مثبتی از سوالها هم بدون راهنمایی موندن که اگه فرصت شد اونا رو هم اضافه میکنیم.
تو این فرصتی که واسه مرحله ۱ مونده، بدون توجه به این که چه پایهای هستید و چه سطحی دارید حتمن چند دوره مرحله ۱ یا چند تا آزمون مرحله یکی رو از خودتون آزمون بگیرید و وقت بذارید روش و کامل حلش کنید.
خوب دیگه، من برم بخوابم D:
شاد باشید :)
۱۳۹۱/۱۰/۰۹ · ۲۱:۳۲
تئوری سوم
سلام! خوبین؟ دیدین دنیا نابود نشد؟ :-| ! ببخشین که یکم دیر شد. خب این دفه هم 3 تا سوال قراره بهتون بدیم که به ترتیب سختی اند. سوال دو و سه هم الگوریتمی هستش. سوال 3 هم از یک سوال codeforces طرح شده و عملا همون سوال هست :دی !!! سوالا رو لطفا کامل بخونین.
________________________________________________________________________________________________________________________________________________________________
سوال اول : تطابق
افشینیک گراف 2n راسی و n2+1 یالی رابه علی می دهد. پس از یک ماه بررسی علی به افشین می گوید که این گراف دقیقا یک تطابق (مچینگ) کامل دارد . ثابت کنیدعلیدروغ گفته است.
(یک تطابق کامل از گراف یک زیرگراف از گراف اصلی با تمام راس ها است که در آن درجه همه رئوس 1 باشد . )________________________________________________________________________________________________________________________________________________________________
سوال دوم : فرار رویایی
شما قرار است در این سوال به یک دزد کمک کنید که از دست پلیس ها بگریزد . درشهر n تقاطع وجود دارد که بعضی از آن ها با خیابان به هم متصلند. خیابانها طول های مختلفی دارند. سرعت ماشین پلیس های این شهر 1 واحد طول بر ثانیه است.
دزد پس از سرقت بانک متوجه می شود که k پلیس درتعدادی تقاطع قرار گرفتهاندو قصد دستگیری او را دارند (دزد از موقعیت پلیس ها مطلع است). h تقاطع از n تقاطع شهر به اتوبان راه دارد که دزد پس از رسیدن به آن جا می تواند از دستپلیس ها بگریزد . دزد می خواهد کمترین سرعت (سرعت ماشین عددی صحیح مثبت است و کمتر یا مساوی 2k) را برای ماشین خود تعیین کند که بتواند از دست پلیس ها بگریزد . (اگر در یک لحظه دزد با یکی از پلیس ها در یک تقاطع یا در یک نقطه از خیابان قرار بگیرد دستگیر می شود)
الگوریتمیازاردرn2kبدهید که کمترین سرعت ممکن را بدست آورد یا اعلام کنید که فرار ممکن نیست.
________________________________________________________________________________________________________________________________________________________________
سوال سوم: آقای ایکسو گراف خود خواه
آقای ایکس یک گرافباnراس دارد.آقایزد دوست آقای ایکس است. او برای گراف آقای ایکس n یالبا خود آوردهاست و این یال ها را به ترتیب به آقای ایکس میدهد.میدانیم اگر آقای ایکس یال شمارهی i ام را نخواهدبایدBiریالهزینه بدهدو همچنین اگر یال شماره ی i را خواست بایدAi ریال هزینه متقبل شود.همچنین میدانیم که k تا از یال ها وضعیتشان معلوم شده استو آقای ایکس حق انتخاب در خریدن یا نخریدن آن یال ها راندارد.
گراف آقای ایکس ویژگی دارد و آنویژگی این است که اگردر هر زمانی تعداد یال هایش از تعدادیال های گرافمتناظرش کمتر شودخود را نابود میکند. همچنین اگرپس از دریافت آخرین یال تعداد یال های گراف آقای ایکس برابر تعداد یال های گراف متناظرش نباشدگراف آقای ایکس خود را نابود میسازد.
هدف آقای ایکس این است که با کمترین هزینه کاری کند که گرافش نابود نشودو اگر راهی برای نابود نشدن گراف وجود ندارد آقای ایکس اظهار ناتوانی کند.
الگوریتمی از اردر n lg nبدهید که هدف آقای ایکس را برآوردهکند.
گراف متناظر :گراف متشکل از یال هایانتخاب نشده را گراف متناظر مینامیم.
________________________________________________________________________________________________________________________________________________________________
سینه خواهم شرحه شرحه از فراق تا بگویمشرحدرد اشتیاق
خوش باشید!
۱۳۹۱/۱۰/۰۲ · ۱۱:۱۹
تئوری دوم
شاززز :)
امیدوارم حال و روز خوبی داشته باشید. سری جدید سوالا آمادست و احتمالن ایدههای حل سوالای سری قبل رو هم به انتهای این پست اضافه کنم.
سوال اول رو خیلیها احتمالن دیده باشن ولی چون سوال خوبی بود تصمیم گرفتیم کسایی که ندیدنش هم ببیننش. سوال میگه ۹۹ تا جعبه داریم. توی هر جعبه یه تعدادی سیب هست و یه تعدادی پرتقال. ثابت کنید میشه ۵۰ تا از جعبهها رو انتخاب کرد طوری که حداقل نصف سیبها و حداقل نصف پرتقالها انتخاب شده باشن.
سوال دوم هم از یکی از سوالای سایت SGU درومده و راه حل جالبی داره. سوال میگه که زورو و اسبش دارن با هم بازی میکنن. اول کار یه رشتهی خالی داریم. توی هر دور از بازی اسب زورو یه حرف Z یا H به انتهای رشته اضافه میکنه. بعدش زورو میتونه دو تا از حرفهای رشته رو انتخاب کنه و جاشون رو با هم عوض کنه، میتونه هم تصمیم بگیره که هیچ کار نکنه. حالا زورو میخواد طوری بازی کنه که در پایان دورهای فرد (دور یکم، سوم، پنجم...) رشتهای که به وجود اومده قرینه باشه. رشتهی قرینه هم رشتهای هست که خودش و وارونش با هم برابر هستن. ثابت کنید زورو میتونه!
سوال سوم یکی از سوالای مورد علاقهی منه. ایدهش مال یه سوال از Codeforces هست. امیدوارم دوستش داشته باشید. سوال میگه که یه آقای پستچی توی گوشه بالا سمت چپ یه جدول بزرگ هست که مختصاتاش از (۱, ۱) تا (n, n) هست. این آقا میخواد به n تا خونه نامه برسونه. مختصات خونه i ام (ai, bi) هست. ترتیب رسوندن نامهها مهم نیست. هر مرحله میتونه یک واحد به یکی از چهار جهت اصلی بره. یه الگوریتم بدید که بتونه با تعداد O(n√n) حرکت یه مسیری رو طی کنه که از همهی خونهها رد بشه و به خونهی اصلیش برگرده.
خوش باشید! D:
Op op op op oppa Gangnam Style!
۱۳۹۱/۰۹/۰۲ · ۱۳:۵۳
تئوری اول
با سلام خدمت دوستان
امیدوارم این 1 ماه و نیم مدرسه خوش گذشته باشه .(قدر مدرسه رو بدونین :دی)
این سری تمرینا آماده شده
امیدوارم خوشتون بیاد
۱۳۹۱/۰۸/۰۸ · ۲۰:۳۱
برنامه!
ای مرغ سحر عشق ز پروانه بیاموز
کان سوخته را جان شد و آواز نیامد
این مدعیان در طلبش بی خبرانند
کان را که خبر شد خبری باز نیامد
سلام! خوبین؟ خوشین؟ خوش میگذره؟ منم خوبم.
چند شب پیش بود که اولین جلسه ی رسمی شاززز دوره 22 انجام شد :-r
خب تو هر جلسه ای یک سری آدم هستن و یک سری صحبت انجام میشه.
خب قاعدتا هدف جلسه این بود که الان که شاززز دست ما 3 نفر هست باید چه کاری تو این چند وقتی که دست ماست انجام بدیم. :-؟
خب در نهایت هم به این نتیجه رسیدیم که روند مثل سال های پیش باشه و یک آزمون آزمایشی مرحله 1 بگیریم و یک سری برای مرحله 3 و مرحله 2 و زدن پاسخ نامه و ...
خب هیچ ایده ی جدیدی در واقع نزدیم. ( البته فعلا :-؟ شایدم کلا )
اما بعد این که به این نتیجه رسیدیم که شاززز این طوری باشه ( با 100% آرا ) رفتیم سراغ این که خب الان چه طوری این کارا باید انجام بشه و همه گفتیم که خیلی سخت هست این طراحی آزمون :))
و این هم با 100% آرا موافقت شد. خب الان موقش بود که یک تصمیم اساسی گرفته میشد که یهو یکی گفت که : " خب بچه ها سوال بدن !!!"
این لحظه بود که 2 تا از بچه ها پریدن هوا و گفتن "قبووووووووووووووول"!
بعد اون یکی گفت که نه خیلی کار ضایعی هست و اینا ...
بعد خب اون بنده خدا پیش نهاد داد که : " بیاین به بچه ها بگیم که سوال بفرستن به میل شاززز ( در حد و اندازه های مرحله 2 ) و بعد ما بشینیم دور هم دیگه سوالا رو بررسی کنیم و سوالای خوب رو انتخاب کنیم. بعد که انتخاب کردیم اگه سوالا برای این مجموعه سوالات این دفعه کافی بودن که هیچی وگرنه خودمون هم سوال اضافه میکنیم "
خب اون 2 نفر هم که دیدن خیلی حرفه خوشگلی زده شد از هوا اومدن رو زمین و گفتن قبول !!!
اما جلسه به اینجا ختم نمیشد. تو همین لحظه بود که یک نادونی پرسید که خب کی این پست رو بنویسه؟ :|
همه ساکت شدن!!
در نهایت پس از جنگ و دعوا های فراوان زور بقیه به من رسید و مجبور شدین که من رو تو این پست تحمل کنین.
حتی در زمانی از اون حدود 30 دقیقه دعوا سر این موضوع ( کل جلسه 45 دقیقه هم نشد =)) ) ما از تابع رندوم ++C هم استفاده کردیم که مورد قبول دوستان واقع نشد.
خلاصه از همه ی این ها بگذریم جلسه ی خوبی بود و کلی هم خندیدیم :))
راستی موضوع اصلی یادم رفت. :-سوت
لطفا سوالاتون رو یک میل بزنین به sh44zzz@gmail.com ( همون میل شاززز ) ( اصلا شاید اینم نیست ) با سابجکت "سوال" و توی اون میل اسم و فامیل و سوال و ایده ی حل رو فارسی و تاکید می کنم فارسی بنویسین.
خوش باشن! :)
۱۳۹۱/۰۷/۲۰ · ۱۹:۱۳
تا آخر IOI ۲۰۱۲
سلام سهباره!
خوب IOI 2012 هم به سلامتی تموم شد. من هم امروز تصمیم گرفتم باقیموندهی خاطرات رو هم بنویسم. یه بخشی هم مربوط میشه به تجربیاتی که از آزمون کسب کردیم که اونها رو سعی میکنم توی پستهای بعدی لابهلای بحثهای بعدی حتماً بگم. :)
تا آخر روز اول مسابقه رو تعریف کردم. بین روز اول و روز دوم مسابقه یک روز فاصله بود. برنامهی این روز هم رفتن به Gardaland بود. Gardaland یک شهر بازی خیلی بزرگ هست با کلی وسیلهی جالب و هیجان انگیز که به نقل از ویکیپدیا سومین شهربازی معروف اروپاست! اولش فکر میکردیم که باید مواظب باشیم و زیاد به خودمون هیجان ندیم تا قبل روز دوم برامون مشکلی پیش نیاد. صبح اون روز به شدت هوا بارونی شد کلی توی ذوقمون خورد ولی خوشبختانه بارونیهای پلاستیکی همه رو نجات دادن و بدون مشکل همه از همهی وسایل استفاده کردن. من خودم که به شدت از این شهربازی لذت بردم و یکی از بهترین تجربههای شهربازیای عمرم بوده! (^.^) ولی خوب باید بگم که ترسناک ترین تجربه از شهربازی تابهحال رو توی پارک ارم تهران داشتم، چون وسیلههای Gardaland اونقدر امنیت داشتن و به آدم حس آرامش میدادن که اطمینان داشتم که از هر وسیلهای که سوار بشم زنده پیاده میشم. D:
فردای اون روز هم روز دوم IOI بود که سرنوشت مدالهای همهمون میتونست از برنز تا طلا تعیین بشه. با این حال خیلی بیحال و بیخیال مثل روز اول رفتیم سر جلسهی آزمون. از نکات بد سوالها این بود که مسئولین برگذاری مسابقه سعی کرده بودن هر سوالی رو به لئوناردو داوینچی ربط بدن و باعث شده بود مسئلهها اکثرشون صورت سوالهای خیلی نامربوط و مسخرهای داشته باشن. ولی ترجمهی سوالها خوب بود و باعث شد که مشکلی برامون پیش نیاد. من خودم سر آزمون ترجیح دادم صورت سوال فارسی رو بخونم و فقط با صورت سوال انگلیسی چکش کنم. بههرحال دیدم با خوندن صورت سوال فارسی آرامش بیشتری دارم. سوالهای این روز تقریباً خیلی سخت بودن. آزمون از دو تا سوال سخت و یک سوال متوسط رو به بالا تشکیل شده بود. تقریباً از ابتدای آزمون میدونستم قراره کدوم سوالها رو حل کنم و از هر کدوم چهقدر نمره بگیرم. تقریباً به مشکل خاصی بر نخوردم موقع آزمون، تا وقتی که دیدم ۱۵ دقیقه به آخر آزمون مونده و من نتونستم هنوز مشکل یکی از کدهام رو پیدا کنم. دیگه تصمیم گرفتم این یک بار رو تنبلی نکنم و تا دقیقه آخر با آرامش دنبال حل مشکل این کد بندهخدا باشم! ۱۲ دقیقه مونده بود به آخر مسابقه تا این که تونستم یک بخش از امتیاز سوال رو بگیرم. آخرش هم موفق شدم تو ۵ دقیقه آخر ۹ امتیاز دیگه هم از سوال بگیرم. ترسناک ترین بخش قضیه هم این بود که من تا ۵ دقیقهی آخر مسابقه طلا نبودم. حتی بعد مسابقه هم خیالم راحت نبود. چون ممکن بود به دلیل تغییرهای احتمالی رتبهام دو سه تا جابجا بشه و طلا نشم!
بههرحال مسابقهی IOI هم تموم شد و سعید مدال طلا گرفت، علیرضا و محمدرضا هم نقره گرفتن و من هم طلا. تجربهی قشنگی بود. من هم تصمیم گرفتم اگه سال دیگه رفتم IOI یه مقدار سوغاتی ببرم با خودم از ایران و با بچههای کشورهای دیگه بیشتر آشنا شم. توی مراسم افتتاحیه هم مسئول IOI میگفت که رمز این مسابقات رابطههایی هست که بین بچههای کشورهای مختلف ایجاد میشه و باعث میشه سود این مسابقات تو آینده هم به بچهها برسه. این هم از این! چند تا هدف داشتم از نوشتن این سه تا پست. یکی این که خودم قدیما دوست داشتم و هنوز هم خیلی دوست دارم در مورد مسابقههای برنامه نویسی و اتفاقاتشون گزارش بخونم. یکی دیگه از دلیلها هم این بود که دوست دارم باعث انگیزه بشه واسه بعضیها و بعضیهایی که قراره بعداً تو این مسابقات شرکت کنن با روند مسابقه آشنا بشن. در ضمن! آقای شریفی هم عضو کمیته علمی IOI شدن امسال، تبریک میگم بهشون. همچنین ایران برای سال ۲۰۱۷ پیشنهاد میزبانی داده، هورا!
طلاهای کشوری هم خیلی وقته که اعلام شدن. تبریک میگم بهشون. به زودی منتظر نویسندههای جدید شاززز باشید!
روزبه بصیریان جهرمی |
مهدی بهروزی خواه |
محمد امین عابدی |
فرزاد عبدالحسینی |
کیوان علیزاده وحید |
دانیال مهرجردی |
سید سبحان میریوسفی |
هومن هاشمی هندوکشی |
________________________________________________________________________________________________________________________________________________________________________________________________________________________________
پی نوشت: راستی اون بقل رو یک نگاه بندازین. بالاخره نویسنده های جدید اضافه شدن! /D:\
۱۳۹۱/۰۷/۱۲ · ۲۰:۳۱
تا آخر روز اول کانتست IOI ۲۰۱۲
سلام دوباره!
پست قبلی تا شب ۵شنبه بود. ما همون شب رسیدیم میلان، رفتیم یه هتل نزدیک ایستگاه مرکزی شهر اسمش Michelangelo بود. روز بعد رفتیم کمی بخشهای قدیمی شهر رو دیدیم. یعنی یه جایی بود که یه بازار خیلی بامزه و فکر کنم قدیمی داشت به کلیسای قدیمی هم کنارش بود. اون رو دیدیم. میلان زیاد چیز جدیدی واسه ما نداره. به جز معماری خونههای قدیمیش و بخشهای قدیمیش که فکر کنم توی بخشهای دیگهی اروپا هم مشابهش زیاد پیدا شه. در کل هم بیشتر فعالیتهای این شهر در زمینهی لباس و فعالیتهای تجاریه. واسه همین شاید چیزی جز یه عالمه مغازه لباس و رستوران سرگرمتون نکنه. با این نرخ یورو هم هروقت میخواستیم چیزی بخریم تا تبدیلش میکردیم به تومن اشکمون در میاومد. اشکامون رو پاک میکردیم، کظم غیظ میکردیم و به راهمون ادامه میدادیم. شنبه یه خیابون طولانی رو زیر پا گذاشتیم پر مغازه لباس فروشی و کافه-بار-رستوران و هیچی جز این پیدا نمیشد! عصر شنبه هم رفتیم Play Center نزدیک میلان. یه چیزی شبیه تیراژهی خودمون بود. سینما، شهربازی سرپوشیده، فروشگاه و رستوران بود. بیشتر بچهگونه بود ولی ما هم همچین بزرگ نبودیم انگار! خوش گذشت. =)
یکشنبه صبح وسایل رو جمع کردیم و رفتیم فرودگاه میلان. اونجا اتوبوسهای Garda Village، محل اقامت شرکت کنندهها، آماده بودن. سوار شدیم. من دیگه از اینجا تا Garda Village رو نمیدونم چی شد. خواب بودم. اونجا هم با راهنما مون رفتیم کیف و تیشرت گرفتیم. اتاقهامونم گرفتیم. محیط اینجا شبیه این مجموعه ویلاییهای لب ساحل هست که تو گیلان هم پیدا میشه. آب و هواش هم دقیقا همون طوریه. تقریبا انواع ورزشها هم اینجا قابل انجام هست.
دیروز، دوشنبه، مراسم افتتاحیه بود که چیز خاصی نداشت. من کلش رو خوابیدم. عصرش هم کانتست تمرینی بود که سوالاش رو از قبل داده بودن و برای تست کردن محیط مسابقه بود. اون رو دادیم. من هم احساس کردم این دو هفته قبل IOI که کد نزدم همهچی یادم رفته! خوشبختانه کم کم یادم اومد!
امروز هم روز اول مسابقات بود. یکی از چیزهای جالب این بود که به هیچ وجه استرس نداشتیم. شب ساعت ۱۰ – ۱۱ افتادیم خوابیدیم و صبح ۶:۳۰ بیدار شدیم. توی اتوبوس هم تا محل برگذاری مسابقات خوابیدم من. کلن هیچ حسی نداشتیم نسبت به مسابقه. علیرضا میگفت شب مرحله ۱ آدم خوابش نمیبرد بعد الان اصن یادمون نیست IOI داریم! آزمون با نیم ساعت تاخیر شروع شد ساعت ۹:۳۰ و ساعت و ۴۵ دقیقه زمانش بود. سه تا سوال داشت که ترجمه فارسیشون روی سایت هست الان. سوالا اونقدرها سخت نبودن. تقریبا مثل سال پیش بود سطحش. من که سوال اول رو زدم ۸۵ نمره و سوال دوم رو کامل و سوال سوم رو ۱۲ نمره. انگار که سوال سوم آسون ترین سوال بوده که خیلیها گرفته بودنش. زیاد از این نمره تخیلیم راضی نیستم! آخه سوال سه رو تقریبا نفهمیدم هیچی ازش. سعید هم آزمون رو خیلی خوب داد! نتایج امروز رو اینجا زدهhttp://carp.di.unipi.it. در حین آزمون هم این صفحه همزمان با ارسال ما آپدیت میشه.
آزمون بعدی پسفردا هست. به نتیجهی یه روز به هیچ وجه نمیشه نگاه کرد و همه چی به روز دوم بستگی داره. بههرحال امیدوارم نتیجه قابل قبولی بگیریم! منم همینطوری ادامه بدم نقره ۱ میشم کلی حال میده (۲۷ تا طلا میدن)! =)
خداحافظ، شبتون خوش! هرچی دوست داشتید بخورید. D:
۱۳۹۱/۰۷/۰۳ · ۲۰:۳۱
روز اول سفر IOI ۲۰۱۲
سلام به شما! :)
قرار شد اولین پستم تو شاززز در مورد IOI 2012 باشه. تیم امسال که از من و سعید و محمد رضا و علیرضا تشکیل شده و همراهامون دکتر آبام، آقای صدیقین، آقای شریفی (که از فرانسه میان به ما ملحق میشن) و یه آقا از وزارت آموزش پرورش هستن. این طوری شد که ما ساعت ۷ صبح توی باشگاه جمع شدیم و بعد از خوردن کمی صبحانه از زیر قرآن رد شدیم و آقای شیری بوسمون کرد و سوار ون شدیم و رفتیم فرودگاه. توی فرودگاهم یکی دو سه ساعتی پشت گیتها منتظر بودیم. عکسی هم که این زیر ضمیمه شده تو همون یک ساعت گرفته شده! بالاخره سوار هواپیما شدیم. همهچیز طبق انتظار پیش رفته بود و همه خوشحال بودیم. توی هواپیما توی مونیتور جلوی صندلی مقدار زیادی فیلم و آهنگ و سریال و بازی بود. ولی خوب لذت بخش ترین بخشش برای من زیر و رو کردن آلبومهای آهنگش بود. هیچوقت همچین فرصتی گیر نمیاد، درک کنید! یه آهنگ خوشگل هم پیدا کردم گوش بدید ببینید چطوره. آهنگ Don’t Leave Me از Regina Spektor از آلبوم What We Saw from the Cheap Seats. خلاصه پرواز هم تموم شد. دو ساعتی توی فرودگاه دبی چرخیدیم و استراحت کردیم و کمی هم خرید تا سوار هواپیمای دومی شدیم به مقصد میلان. الآن هم که دارم اینو مینویسم تو همون هواپیما هستیم و حدود دو ساعت دیگه میرسیم میلان. تو این هواپیما هم سعی کردم بخوابم نشد، فیلم ببینم نشد، کارتون ببینم نشد. جاش یکم با هم بازی کردیم. الان هم محمدرضا و سعید و علیرضا دارن بازی میکنن و دکتر آبام و آقای صدیقین هم این پشتن و گویی خوابن. آقای کمکی هم داره یه فیلمی میبینه. خوب جو این پرواز دومیه خیلی خارجیه بعد من غریبیم گرفته... الآن هم داریم از یک جبهه هوای داغون رد میشیم خیلی باحاله! و کلی سر و صدا البته. رعد و برق هم میاد از پنجره.
برنامه سفرمون هم اینطوریه که تا یکشنبه ظهر میلان هستیم، بعد هم میریم محل برگزاری مسابقه. سایت مسابقه هم www.ioi2012.org هست که ریز برنامهی مسابقه رو نوشته. من هم هر موقع وقت کنم از اتفاقات اخیر مینویسم. جاتون خالیه. این بچههام هنوز دارن بازی میکنن. :)) این پست رو نت به دست آوردم میذارم رو بلاگ.
شب خوبی داشته باشید. شام هم ترد نمکی بزنید توی سس تند با tomato juice میل کنید!
۱۳۹۱/۰۶/۳۰ · ۲۳:۳۳