صفحه ۲۱
تئوری چهارم
______________________________________________________________________________________________________
سوال اول: شکلات سمی
یک جدول n*m داریم که در یکی از خونه های این جدول یک شکلات قرار داره. آقای ایکس و دشمنش روی این جدول دارن با هم بازی میکنن. نکته ی جالب این جدول اینه که هر کی به شکلات برسه باید اون شکلات رو بخوره و احتمالا خیلی سریع میمیره. ( احتمالا!!! )
توی هر حرکت یک نفر میتونه یا یک برش افقی توی جدول بزنه یا یک برش عمودی و حتما برش رو باید از روی خطوط جدول بزنه. بعد از اینکه برش زده شد جدولی که باقی میمونه اون جدولی هست که شکلات داره. حالا آقای ایکس میخواد زنده بمونه. بهش بگین نفر اول باشه یا نفر دوم :دی
مثال: فرض کنین یک جدول 1 * 3 داریم که توی خونه ی وسط این جدول شکلات قرار داره. حالا اگه آقای ایکس نفر دوم باشه زنده میمونه. دشمنش یک جدول 1 * 2 ایجاد میکنه که توی گوشش یک شکلات هست. بعد آقای ایکس جدول 1 * 1 ایجاد میکنه که شکلات توشه. بعد دشمن آقای ایکس باید شکلات رو بخوره :دی.
_____________________________________________________________________________________________________
سوال دوم: ایکس او مدل جدید با آقای ایکس
یک جدول n * m داریم. آقای ایکس که دشمن قبلیش رو کشته بود به دشمن جدیدش رسیده به اسم آقای او.اگه نوبت آقای ایکس باشه, آقای ایکس, یک ایکس توی یکی از خونه های خالی جدول میذاره.اگه نوبت آقای او باشه, آقای او, یک او توی یکی از خونه های خالی جدول میذاره. حالا اگه 9 تا خونه ی پشت سر هم از یک قطر یا یک ستون یا یک سطر همشون او بشن, آقای او میبره, در غیر این صورت آقای ایکس میبره.
بگین آقای ایکس چندم باشه که ببره؟ :دی
_____________________________________________________________________________________________________
سوال سوم: دنباله ی جالب
یک دنباله داریم به اسم d که اولین عنصرش 2 هست و دومین عنصرش هم 13 هست. ما در هر مرحله میتونیم َعنصر i ام رو برابر یکی از حالت های زیر کنیم.
di = 12di - 2
di = 13di - 1 - 12di - 2
حالا فرض کنین که ما همیشه فقط 2 تا عنصر آخر دنباله رو نگه داریم. حالا ثابت کنین در مرحله ی i ام میتونیم دقیقا به i تا دنباله ی مختلف برسیم.
مرحله ی اول: 2 13
مرحله ی دوم: 13 24 , 13 145
مرحله سوم: 24 156 , 145 156 , 145 1729
______________________________________________________________________________________________________
چهار شنبه آخر سال خوش بگذره. عید نیز هم. شاد و پیروز و موفق باشید. :دی
۱۳۹۱/۱۲/۲۹ · ۱۶:۵۱
عیدتون مبارک !
اگر چند مدت شاززز سوت و کور بود به خاطر امتحان انتخاب تیم امسال بود . تیم امسال :
سید حامد ولیزاده - کیوان علیزاده وحید - دانیال مهرجردی - فرزاد عبدالحسینی
برای همشون آرزوی موفقیت می کنیم انشالله امسال 4 تا طلا می گیریم . (امسال امتحان تو استرالیاست هیچی بعید نیست :دی )
نتایج مرحله 1هم که خیلی وقته اومده . به همه ی کسایی که قبول شدن تبریک می گم و کسایی هم که نشدن بدونن که چیزی از بقیه کمتر ندارن فقط یک امتحان رو نتونستن خوب بدن و مطمئنا در مقاطع بعدی بهتر عمل می کنن .
نوروز خوش بگذره ! تفریح تو نوروز فراموش نشه !!! توصیه اکید می شه که تفریح رو از برنامه کنار نگذارید !
شاد و خرم باشید
۱۳۹۱/۱۲/۲۲ · ۱۷:۵۹
مرحله ۱
اما هدف اصلی از این که این پستو گذاشتم اصلا بحث پاسخ نامه و این طور چیزا نیست. اومدم در مورد مرحله 1 صحبت کنم. اول از همه این که نظرای شاززز رو اصلا تحویل نگیرین. هر کسی هر نمره ای دوس داره رو میاد میذاره این جا و به هیچ عنوان جدی نگیرین این چیزیایی که اینجا بچه ها میگن. ضمن اینکه اگه حتی کسی نمره ی واقعی خودشو بذاره هم اکثرا اونایی اند که خوب دادن آزمون رو. همین پارسال مثلا. کف پارسال خیلی پایین بوده تقریبا همه این موضوع رو میدونید. اما چیزایی که من تو شاززز میدیدم کف پایین رو نشون نمیداد! خب پس نکته ی خیلی مهم اینه که بیخیال نظرای شاززز شین و فقط اونا رو بخونید و بخندید و جدی نگیریدشون.
حالا از نظرا و اینا بگذریم. الان بعضیا از جلسه اومدن بیرون و خیلی نا امیدن و میخوان دیگه بیخیال المپیاد شن. اگه اولی هستن که واقعا اشتباهه. خیلی ها هستن که مرحله اول تو سال اول و دوم ( حتی ) قبول نمیشن ولی سال سوم میان دوره. اگه اونایی که فکر میکنن بد دادن امتحانو دومی هستن هم این چیزی که گفتم در موردشون صدق میکنه و نا امیدی هیچ مفهومی نداره. اما اگه سومی هستن من خودم بهشون یک پیشنهادی میدم. اونم این که الان المپیاد رو ول نکنن. صبر کنن نتایج بیاد. چون که اگه قبول شن خیلی ناراحت کنندس براشون. ضمن این که تا اومدن نتایج کار خاصی ندارن و میتونن المپیاد رو ادامه بدن.
یک چیزه دیگه هم اینکه خودتون رو با بچه های مدرسه ی خودتون مقایسه نکنید. چون ممکنه خیلی مدرسه ی قوی داشته باشید و بچه هاش خفن باشند. بعد نمره ی اونا رو میفهمین کلی نا امید میشینو اینا. کلن الان که مرحله 1 دادین حس راحتی کنین. ( با این که چیزه خیلی مهمی نبوده )
احتمالا تا آخر شب ادامه ی این پست یک سری حرف میزنیم دوباره که در مورد کلید مرحله اول هستش.
خوش باشید!
_____________________________________________________________________________________________________________________________
پی نوشت 1: فکر میکنم که بعضیا دارین خیلی حرص میخورید و استرس دارید. به نظرم این حرص خوردن بی خودیه. یک آزمون تا وقتی ارزش فکر کردن داره که تموم نشده باشه. وقتی که تموم شد دیگه کاری از دستتون بر نمیاد. بی خودی این قدر فکرو خیال نکنین. پشت کامپیوتر هم نشینین بیخود و هی رفرش بزنین که پاسخ نامه بیاد. اگه کمیته تا 12 شب نزنه این جا میذاریم پاسخ نامه رو. اگه که از تلاشی که کردین برای این آزمون که مثل یک مسابقه میمونده راضی بودین که به جایگاهه خیلی بزرگی رسیدین و رضایت از خود خیلی چیزه مهمیه. ولی اگه که فکر میکنین کم کاری کردین دیگه غصه خوردن فایده نداره. باید بیخیال شینو برای بعدی بیشتر تلاش کنین. کلن هم برای این که آروم شین من پیشنهاد میکنم چند تا نفس خیلی عمیق بکشین و آروم دم و بازدم کنین. اثیر گذاره. بازم میگم یک آزمون تا وقتی ارزش داره که تموم نشده باشه. وقتی تموم شد فکر کردن بهش خیلی اشتباس!
تا بعد...
____________________________________________________________________________________________
پی نوشت 2:http://paste.ubuntu.com/1639844
خب بچه ها. اینم لینک پاسخ نامه ی بچه های شاززز هستش.
دیدم خیلی عجله دارید این پاسخ نامه رو گذاشتم. امیدوارم که اشتباه نباشه. شاد باشید.
تا بعد!
_______________________________________________________________________________________________
پی نوشت 3: راستی اگه که دوست داشتین توی نظر سنجی هم شرکت کنین.
ضمنا اگه میشه نمره ی واقعی رو بزنین. مرسی.
فعلا!
۱۳۹۱/۱۱/۲۴ · ۱۱:۰۳
اطلاعرسانی inoi.ir
اومدم بگم که یه سری بهسایت کمیته کامپیوتر (inoi.ir)بزنید و مطالب جدیدشو بخونید! مخصوصن بخشپرسشهای متداولکه تازه اضافه شده. توش به یه سری سوالهایی که در طول ۵ سال گذشته از طریق ایمیل کمیته پرسیده شده بود جواب داده شده.
خوب باشید :)
۱۳۹۱/۱۱/۰۱ · ۲۰:۲۱
راهنماییهای تعدادی از سوالهای سری ۱ و ۲
برای چندتا از سوالهای سری ۱ و ۲ تمرینها یه خرده راهنماییای آماده کردیم. تا اگه با حل کردن سوالا مشکل داشتید کمکتون کنه.
راه حلهایی که سبحان آماده کرده
راه حلهایی که دانیال آماده کرده
و این هم من آماده کردم 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 ماه و نیم مدرسه خوش گذشته باشه .(قدر مدرسه رو بدونین :دی)
این سری تمرینا آماده شده
امیدوارم خوشتون بیاد
۱۳۹۱/۰۸/۰۸ · ۲۰:۳۱