صفحه ۴
آزمون عملی دو
سلام!!
دومین کانتست عملی شاززز جمعه این هفته برگذار میشه! مثل کانتست قبلی میتونید در هر بازه ی 5 ساعته ای که می خواید در آزمون شرکت کنید.
کانتست از 8 صبح جمعه تا 12 شب دوشنبه برقرار خواهد بود. امیدواریم که از سوالا خوشتون بیاد! =)
توصیه میکنیم که حتما همه ی سوال ها رو بخونید!
کسری مظاهری
۱۳۹۸/۱۱/۲۹ · ۱۵:۱۵
آزمون شبه مرحله ۱ ای
سلاااااام
توی این روزای دم مرحله ۱ ما براتون یه آزمون شبیه ساز تدارک دیدیم تا از بی آزمونی رنج نبرید !
شما می تونید از اول پنجشنبه تا آخر جمعه این هفته توی یک بازه زمانی 3 ساعته در آزمون شرکت کنید.
پس از پایان وقت آزمون اسامی ده نفر برتر اعلام خواهد شد.
سوالات آزمون هم به شدت جذاب هستن و سعی شده که شبیه به مرحله ۱ باشن پس به دوستانتون هم بگید که شرکت کنند.
آپدیت ۱ :
از طریق بات تلگرام مرحله ۱ شااززز می تونید در آزمون شرکت کنید!
با تشکر از حمیدرضا کلباسی و دبیرستان علامه حلی ۱ .
آپدیت ۲ :
زمان آزمون تا انتهای روز شنبه تمدید شد.
آپدیت ۳:
اسامی ۱۰ نفر برتر به این شکل می باشد :
۱ - سیدمحمدحسین حسینی
۲ - سید آریان وهاب پور
۳ - ماردین نیچی
۴ - هادی علی کرمی
۵ - عماد امام جمعه
۶ - سید محمد مهدی مصطفوی اصفهانی
۷ - علی دوستی
۸ - شایان باب المندبی
۹ - بهراد صمیمی
۱۰ - محمد امین درستی
تعداد افرادی که درصد آنها بالای ۶۰ بود : ۲۰ نفر
تعداد افرادی که درصد آنها بالای ۴۰ بود : ۶۹ نفر
تعداد افرادی که درصد آنها بالای ۲۰ بود: ۱۲۶ نفر
تعداد افرادی که درصد آنها بالای ۰ بود : ۳۲۸ نفر
۱۳۹۸/۱۰/۲۰ · ۲۲:۵۵
سوالات تلگرامی شااززز
آیا از کمبود سوال یا نداشتن سوال تئوری رنج می برید ؟
آیا به دنبال قوی شدن در یک مبحث خاص ( مثلا ناوردایی ) هستید ولی به اندازه کافی سوال برای حل کردن ندارید ؟
ما (طلا های دوره ۲۹ ) برای این مشکل راه حلی پیدا کردیم! از این به بعد می توانید به بات تلگرام شااززز سر بزنید و سوال بگیرید.
نکته قابل توجه این است که می توانید از یک تگ ( مثلا استقرا ) یا حتی چند تگ خاص (مثلا استقرا و اکسترمال و لانه کبوتری) سوال بگیرید. در اینصورت سوالاتی که همه این تگ ها را همزمان دارند برای شما نمایش داده می شود.
شما قابلیت ذخیره کردن سوالاتی که روی آنها فکر کردید و حل نشدند را دارید ! پس نگرانی از بابت به فراموشی سپرده شدن سوالات حل نشده وجود نخواهد داشت.
اگر سوالی حل نشد شما می توانید هینت سوال را بخوانید! در صورت تمایل می توانید راه حل سوال را هم بخوانید ولی در فرهنگ المپیادی این کار ( سوزاندن سوال ) کاری بسیار زشت است :))
در صورت تمایل می توانید به آرشیو سوالات ما سوال اضافه کنید! در اینصورت سوال شما بعد از بررسی ما به لیست سوالات اضافه خواهد شد. همچنین به کسی که بیشترین تعداد سوال را اضافه کند پیتزا تعلق خواهد گرفت! برای فهمیدن اینکه چند تا سوال اضافه کرده اید و نفر چندم هستید می توانید به 'رنکینگ' را ببینید.
https://t.me/ShaazzzProblemBot
با تشکر از دبیرستان علامه حلی ۱ که سرورشان را در اختیار ما قرار دادند.
۱۳۹۸/۰۹/۲۷ · ۲۴:۵۷
راه حل های آزمون عملی یک
سلام!
خب بدون مقدمه می‌ریم سراغ جواب سوال ها:
سوال ۱ :
بلاک های ماکسیمال صندلی ها را در نظر بگیرید که همزمان شامل معلم و دانش آموز نباشند. در بلاک های اول و آخر همه می‌توانند پاپ کرن بخورند ولی در بلاک های وسطی دقیقا یک نفر نمی‌تواند. پس اگر تعداد بلاک های وسطی را x بگیریم جواب سوال n-x میشه.
سوال ۲ :
فرض کنید dp i,rev رو تعریف میکنیم مینیمم تعداد حرکات لازم اگر که بخوایم i تا حرف اول رشته رو تبدیل به A کنیم. و rev هم می تونه 0 یا 1 باشه که بهمون میگه قبل از شروع کار ما i تای اول برعکس شده‌اند یا نه.
حالا توجه کنید که اگر تصمیم بگیریم یک حرکت بزاریم که فقط i رو عوض کنه اونوقت مستقل از اینکه خونه i ام چی هست می تونیم فرض کنیم که در آخر می‌تونیم به A تبدیلش کنیم. اگر هم تصمیم بگیریم که تکی i رو عوض نکنیم دو حالت داریم. یا خونه i ام الان برابر با A هست که در اینصورت نباید کاری انجام بدیم. یا اینکه برابر نیست که باید با یک حرکت i تای اول رو عوض کنیم.
فرض کتید change متغیری بولین باشد که نشان می دهد بعد از اعمال rev باز هم باید خانه i ام را تغییر دهیم یا نه.
dp i,rev = min( 1 + dp i-1,rev , change + dp i-1,rev ^ change )
سوال ۳ :
لم : یک عدد بر ۱۱ بخش پذیر است اگر و فقط اگر یکی در میان رقم هایش را جمع و منها کنیم و حاصل بر ۱۱ بخش پذیر باشد!
اثبات :
a1a2a3...an = a1 * 10 ^ (n-1) + a2 * 10 ^ (n-2) + ... + an = a1 * -1 ^ (n-1) + a2 * -1 ^ (n-2) + ... + an (mod 11)
که حکم را ثابت می‌کند.
حالا واضحه که عدد m همیشه بر ۱۱ بخش پذیر خواهد بود. پس کافیه برای عوامل اول ۲ و ۳ و ۵ و ۷ و ۱۱ چک کنیم که آیا m بر اون ها بخش پذیر هست یا نه.
فرض کنید می‌خواهیم باقی مانده m را بر p پیدا کنیم. برای اینکار هم می توانیم از پرارزش ترین رقم شروع کنیم و در هر مرحله باقی مانده تقسیم i رقم اول بر p را حساب کنیم. اگر این باقی مانده تا الان r باشد و رقم i+1 ام x باشد داریم :
r = ( r * 10 + x ) % p
سوال ۴ :
اول از همه اینکه فاصله منهتنی دو نقطه x1,y1 و x2,y2 برابر با |x1-x2| + |y1-y2| هست. می بینیم که ابعاد x و y با هم هیچ ارتباطی ندارند پس می توان آنها را جدا جدا حل کرد و سپس جواب های به دست آمده را با هم جمع کنیم و خروجی بدیم.
حالا بررسی کنید که اگر x ما یک واحد زیاد شود جواب چه تغییری می کند. فاصله ما از نقاطی که x کمتر مساوی دارند یک واحد زیاد می شود و از نقاطی که x بیشتر دارند یک واحد کم می شود. مشابها حالتی که x یک واحد کم شود هم قابل بررسی است.
پس اگر بتوانیم در هر مرحله تعداد نقاطی که مختصات x کمتر مساوی از x ارشیا دارند را حساب کنیم می توانیم با این اطلاعات تغییرات جواب را حساب کرده و جواب جدید را به دست بیاوریم. برای این کار کافیه کل x ها را در یک آ رایه سورت شده ذخیره کنیم و با باینری سرچ ( یا تابع lower_bound ) این تعداد را پیدا کنیم.
سوال ۵ :
برای حل این سوال راه حل های متفاوتی وجود داشت از جمله راه هایی با استفاده از ایده هایی مثل sqrt یا centroid.
اما در اینجا راه حلی دیگر را بیان میکنیم که احتمالا ایده کلی آن برای شما جدید و جالب و قابل تعمیم است!
سوال معادل این است که یک درخت n راسی وزن دار داریم و q تا کوئری که در هر کدام دو مجموعه نه لزوما مجزا از رئوس به نام های A و B داده می‌شود و هدف پیدا کردن کوتاه ترین مسیری است که یک سر عضو A و سر دیگر عضو B باشد.
ابتدا در نظر بگیرید که می توانیم هر کوئری را O(n) جواب بدهیم. کافیست با یک bfs مینیمم فاصله هر راس از یک راس مجموعه A را به دست بیاوریم و جواب مینیمم این فاصله ها در بین رئوس B خواهد بود.
اجتماع مجموعه های A و B را S بنامید. حالا توجه کنید که برای بسیاری از رئوس به دست آوردن این مقدار لازم نیست! پس هدف ما است که یک درخت کوچکتر بسازیم که در آن به ازای هر راس S راسی معادل وجود داشته باشد و فاصله هر دو راس در S برابر با فواصل معادل های آنها در درخت جایگزین باشد!
لم : اگر مچموعه S از راس های درخت را داشته باشیم که t عضو دارد می توانیم حداکثر t-1 راس به آن اضافه کنیم که مجموعه جدید نسبت به عمل Lca بسته باشد. (به عبارتی Lca هر دو راس مجموعه عضو مجموعه باشد. )
اثبات :
کافیست رئوس را بر حسب استارتینگ تایم صعودی سورت کنید. سپس به ازای هر دو راس متوالی در S مثل a,b ما Lca(a,b) را به مجموعه اضافه میکنیم. ( پس حداکثر t-1 عضو اضافه کردیم )
حالا دوباره راس ها را بر حسب استارتینگ تایم صعودی سورت کنید و اگر a,b دو راس متوالی باشند پدر b همان Lca(a,b) خواهد بود! (باید وزن یال بین a,b باید طول مسیر بین a,b در درخت اصلی باشد)
پس به ازای مجموعه S از راس ها می توان درخت جدیدی با تعداد رئوس حداکثر 2 * |S| ساخت و همانطور که در ابتدا کوئری را O(n) جواب دادیم می توان در درخت جدید کوئری را O(|S|) حل کرد!
سوال ۶ ؛
حل کامل سوال در اینجا گفته نمی‌شود. بعد از فهمیدن هینت زیر انقدر به سوال فکر کنید تا حل بشه! 😃
اول از همه اینکه دایسترا بزنید و بعد از داخل درخت دایسترا از گوشه بالا چپ جدول به گوشه بالا چپ همه روستا هایی که باید دورشون دیوار بکشیم یک مسیر بکشید. ( با رنگ سبز در شکل زیر مشخص شده. )
حالا مسئله معادل پیدا کردن یک دور شامل گوشه بالا سمت چپ جدول هست به طوریکه مسیر سبز که کشیدیم را قطع نکند. ( دور با رنگ نارنجی مشخص شده )
خب امیدوارم که از سوال ها خوشتون اومده باشه.
اگه چیزی رو نفهمیدید یا اشتباه گفتم توی کامنت ها بگید. به زودی هم با یه سری سورپرایز بر می‌گردیم. :))
نویسنده : شایان پردیس
۱۳۹۸/۰۸/۱۴ · ۱۷:۲۳
آزمون عملی یک
سلام سلام!!
اولین کانتست شاززز فردا برگذار میشه! شما میتونید در هر بازه ی 5 ساعته ای که می خواید در آزمون شرکت کنید!
کانتست از 9 صبح فردا تا 12 شب یکشنبه بازه. امیدواریم که خوشتون بیاد!
قابل ذکره که به نفر دوم مسابقه جوایزی تعلق میگیرد! D:
کسری مظاهری
۱۳۹۸/۰۸/۱۰ · ۱۲:۲۲
آزمون عملی اول
سلام سلام :))
آگاه باشید و بدانید و بعدش به دوستاتون هم بگید که جمعه دهم آبان اولین آزمون عملی شاززز برگزار خواهد شد.
نویسنده: ابوالفضل سلطانی
۱۳۹۸/۰۸/۰۳ · ۱۳:۲۰
سلام اول
سلام سلام :)
ما یعنی طلاهای دوره ۲۹ اومدیم و تلاشمونو میکنیم که امسال شاززز برای همه مفید باشه و داخل یه فضای صمیمی و باحال کلی چیز یاد بگیریم.
اگه نظری پیشنهادی چیزی دارید، حتما بگید که استفاده کنیم :)
منتظر خبرای خوب باشید، زودِ زووود برمیگردیم
۱۳۹۸/۰۷/۳۰ · ۱۴:۱۴
خدافظی ۹۸ایا
خب سال طلای ما هم گذشت. شدیدن تو این سال اتفاق افتاد برای ما ۸تا. از "فردا با آقای میرجلالی کلاس دارید" گرفته تا "سیستم در خطره".
شاززز هم تو این سال بد نبود. به نظرم منطقیه به عملکردمون خوب نگیم قطعن بد هم نمیتونیم بگیم. ولی خب حالا گذشته اون و مهم اینه که ۸تای بعدی چیکار میکنن. (میدونیم کسری قرار نیست کاری کنه پس ۸تان)
توی زندگی من، بجز ۳ سال اول، به نظرم ۳ سال المپیاد بیشتر از بقیش خوش گذشته. و صرفن منظورم تو مرحله های آخرش مث دوره تابستون و اینا نیست. خود روند اینکه هر روز سوال حل کنی و هر روز مسلط تر شی لذت بخشه.
هرچقدرم المپیاد براتون بی‌ثمر باشه یا از چیزی که توش به دست آوردید خوشحال نیستید، حداقل وقتی ۵۰ سالتون شده و یاد دوران دبیرستان میفتید، یادتون میاد که داشتید المپیاد میخوندید. بقیه وقتی به دبیرستان فکر میکنن میگن که شت من هیچ کاری نکردم تو دبیرستان!
خلاصه که ما کم‌کم داریم از این شکل المپیاد خارج میشیم. خوش گذشت دیگه! بابای :)))
جعفر مهدی جعفری
۱۳۹۸/۰۷/۲۹ · ۲۱:۲۵