شاززز

شاززز

اینجا وبسایت آزاد المپیاد کامپیوتره! ;)
واسه ی همه ی سطوح از تازه کارها تا طلای جهانی!

طبقه بندی موضوعی
بایگانی
۱۴
آبان

سلام!

خب بدون مقدمه می‌ریم سراغ جواب سوال ها:

 

سوال ۱ :‌

 

بلاک های ماکسیمال صندلی ها را در نظر بگیرید که همزمان شامل معلم و دانش آموز نباشند. در بلاک های اول و آخر همه می‌توانند پاپ کرن بخورند ولی در بلاک های وسطی دقیقا یک نفر نمی‌تواند. پس اگر تعداد بلاک های وسطی را 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|) حل کرد!

 


 

سوال ۶ ؛

 

حل کامل سوال در اینجا گفته نمی‌شود. بعد از فهمیدن هینت زیر انقدر به سوال فکر کنید تا حل بشه! laugh

 

اول از همه اینکه دایسترا بزنید و بعد از داخل درخت دایسترا از گوشه بالا چپ جدول به گوشه بالا چپ همه روستا هایی که باید دورشون دیوار بکشیم یک مسیر بکشید. ( با رنگ سبز در شکل زیر مشخص شده. )

حالا مسئله معادل پیدا کردن یک دور شامل گوشه بالا سمت چپ جدول هست به طوریکه مسیر سبز که کشیدیم را قطع نکند. ( دور با رنگ نارنجی مشخص شده )

 

 


 

خب امیدوارم که از سوال ها خوشتون اومده باشه.

اگه چیزی رو نفهمیدید یا اشتباه گفتم توی کامنت ها بگید.  به زودی هم با یه سری سورپرایز بر می‌گردیم. :))

 

نویسنده : شایان پردیس

  • طلاهای دوره ۲۹
۱۰
آبان

سلام سلام!!

 

اولین کانتست شاززز فردا برگذار میشه! شما میتونید در هر بازه ی 5 ساعته ای که می خواید در آزمون شرکت کنید!

 

کانتست از 9 صبح فردا تا 12 شب یکشنبه بازه. امیدواریم که خوشتون بیاد!

 

قابل ذکره که به نفر دوم مسابقه جوایزی تعلق میگیرد! D:

 

لینک ثبت نام

 

کسری مظاهری

  • طلاهای دوره ۲۹
۰۳
آبان

سلام سلام :))

آگاه باشید و بدانید و بعدش به دوستاتون هم بگید که جمعه دهم آبان اولین آزمون عملی شاززز برگزار خواهد شد. 


نویسنده: ابوالفضل سلطانی

  • طلاهای دوره ۲۹
۳۰
مهر

سلام سلام :)

ما یعنی طلاهای دوره ۲۹ اومدیم و تلاشمونو میکنیم که امسال شاززز برای همه مفید باشه و داخل یه فضای صمیمی و باحال کلی چیز یاد بگیریم.

اگه نظری پیشنهادی چیزی دارید، حتما بگید که استفاده کنیم :)

منتظر خبرای خوب باشید، زودِ زووود برمیگردیم

  • طلاهای دوره ۲۹
۲۹
مهر

خب سال طلای ما هم گذشت. شدیدن تو این سال اتفاق افتاد برای ما ۸تا. از "فردا با آقای میرجلالی کلاس دارید" گرفته تا "سیستم در خطره".

شاززز هم تو این سال بد نبود. به نظرم منطقیه به عملکردمون خوب نگیم قطعن بد هم نمیتونیم بگیم. ولی خب حالا گذشته اون و مهم اینه که ۸تای بعدی چیکار میکنن. (میدونیم کسری قرار نیست کاری کنه پس ۸تان)

 

توی زندگی من، بجز ۳ سال اول، به نظرم ۳ سال المپیاد بیشتر از بقیش خوش گذشته. و صرفن منظورم تو مرحله های آخرش مث دوره تابستون و اینا نیست. خود روند اینکه هر روز سوال حل کنی و هر روز مسلط تر شی لذت بخشه.

هرچقدرم المپیاد براتون بی‌ثمر باشه یا از چیزی که توش به دست آوردید خوشحال نیستید، حداقل وقتی ۵۰ سالتون شده و یاد دوران دبیرستان میفتید، یادتون میاد که داشتید المپیاد میخوندید. بقیه وقتی به دبیرستان فکر میکنن میگن که شت من هیچ کاری نکردم تو دبیرستان!

 

خلاصه که ما کم‌کم داریم از این شکل المپیاد خارج میشیم. خوش گذشت دیگه! بابای :)))

 

جعفر مهدی جعفری

  • طلاهای دوره ۲۸
۲۸
ارديبهشت

پس از سال ها پست الگوریتم هفتگی ر میذاریم :)) این پست قراره خیلی طولانی باشه چون سگمنت‌تری سوالاش متفاوت و زیاده.

پیشنهاد میشه که اگه سوالیو نمیتونید حل کنید توتوریالش ر بخونید.

  • طلاهای دوره ۲۸
۱۰
ارديبهشت

خب سلاام! خوبین؟


حس میکنم که این دو روز باید تایم مهمی برای المپیادیا باشه و خب روحیه خوب داشتن، یه چیزیه که حداقل من فک میکنم خیلی مهمه تو المپیاد کامپیوتر و اساتید دوره هم همین رو میگفتن بهمون! روحیه هم بحثش فک نمیکنم خیلی مخصوص به یه گروه خاص باشه! هم کسایی که مثلا تهرانین و معلم و دوست المپیادی زیاد دارن درگیرش ممکنه باشن چون آدمای قوی تر از خودشون رو احتمالا زیاد دیدن، هم آدمایی که معلم کم داشتن یا نداشتن و دوست المپیادی هم همینطور، چون سطح خودشونو سخته بسنجن.


خب من تقریبا آدم موفقی نبودم تو مرحله دو، واقعا لب مرز قبول شدم، ولی خب شاید بتونم یه چیزایی بگم که بدرد بخوره!


اول از اینکه پست های قدیمی شاززز واقعا پست های خفنی هستن بابت روحیه دادن و این حرفا! مثلا این پست خیلی خوبه. یکی از چیزایی که برای من خیلی جالب بود این لینک هستش. الان متاسفانه پست مربوط بهشو پیدا نکردم شما وقت داشتین میتونین یه سرچی بزنین.


دوم اینکه زمان درس خوندن و تلاش برای قوی شدنتون تموم شده الان برای مرحله 2، الان به نظر من نباید دیگه درسی چیزی بخونین، صرفا چیزایی که الان میتونین یا ممکنه بتونین تغییر بدین تو خودتون یکی اعتماد به نفس هستش، یکی روحیه و انگیزه ی خوب داشتن و حال خوب، و یکی هم استراتژی خوب داشتن.


که دو مورد اول رو خودتون میتونین تلاش کنین براش یا بخواین از دوستاتون و استاداتون یا افراد رندم حتی که کمک کنن بهتون، اگه کمکی از من هم بر میومد بهم بگین حتما! اینکه حالتون خوب باشه به نظرم خیلی مهمه، چه قبول بشین چه نشین چند ماه یا سال دیگه که به قضیه نگاه کنین خیلی دید خوشگل تری دارین نسبت به مرحله دو اگه الان حالتون خوب باشه!


مورد سوم که استراتژی خوب داشتن هست برای افراد مختلف فرق میکنه و اگه تا حالا تو آزمونای آزمایشی یه سری چیز رو تست کردین خیلی خوبه میتونین بهترینشو انتخاب کنین، کسایی هم که اینکارو نکردن میتونن از افرادی که با تجربه ترن نظر بخوان تا کمک کنن بهشون.


چیزایی که من حس میکنم باید رعایت کنین ایناست:


تایم خوااب خیلی مهمه فک میکنم، اگه شب دارین این پستو میخونین که واقعا . بگیرین بخوابین، من اینجور موقع ها یکم بیخوابی و اینا میزد به سرم و میتونستم نیم ساعت یه ساعت اینا بیشتر از حد معمول برنامه ریزی کنم برای خواب که کم نخوابم مثلا.


خوراکی و شوکولات خیلیییی مهمه، اینجوریه که ملت ممکنه ازین شوکولات خفنا بیارن و شما دلتون بخواد بعد ناراحت شین که شوکولات ندارین یا خفن نیست شوکولاتتون که این خیلی بده، سعی کنین شما اون آدم شوکولات خفن آورنده هه باشین. آب هم ببرین و هر از چندگاهی مقداری بنوشید چون استرستون را کاهش میده. البته زیادیشم خوب نیست :)


این مورده یکم شخصیه ولی پیشنهاد میکنم چک نکنین  برگتونو بعد آزمون تستی، من خودم هر دو سال فک کنم چک کردم ولی اگه چک نمیکردم حس میکنم ممکن بود نتیجم بهتر شه. چون شما دارین دو تا آزمون مستقل میدین که توش باید مستقل از اون یکی آزمون بهترین خودتون باشین.


برای اینکه رو هر سوال تستی چقد فک کنید و چجوری مطمعن شین از جوابتون و چقد تایم بزارین و چجوری ددلاین بزارین برای تست ها فک کنین قبل آزمون خوبه. حواستون باشه که زمان کم نیارید و روی همه سوالا به اندازه کافی وقت بذارید.


برای آزمون های تشریحی هم خیلی مدیریت وقتتون مهمه، سعی کنین براش برنامه ریزی کنین!


سومین و مهم ترین نکته ای که میشه در مورد این دو روز بهتون گفت اینه که استرس نداشته باشید. آروم آروم آروم. دلیلی برای نگرانی و استرس وجود ندارد. شما تمام تلاشتون را کردید و اگر برگردید به عقب هم دوباره همین مسیر را میایید. وقتی بهترین کاری که می تونستید را انجام دادید چرا می خواهید با اضطرابب، بیخودی خرابش کنید. مطمئن باشید اگر یه دلیل وجود داشته باشه که شما نتونید نتیجه زحماتتون را بگیرید همین استرسه. اصلا به آزمون فکر نکنید و بیخودی برای خودتون بزرگش نکنید. یه آزمون معمولیه مثل بقیه آزمونا. شما درس خواندید و تلاش کردید و الان می خواهید خودتون را یه محکی بزنید. همین و فقط همین. زندگیتونو بکنید و از این دو روزتون لذت ببرید. وسطش یه ازمونی هم بدید.

باز با تموم این حرفا می دونم که هم قبل از آزمون استرس دارید و هم وقتی آزمون شروع میشه و هم وقتی تموم میشه. بالاخره کاریش نمیشه کرد. این استرس را هر چه قدر هم کنترل کنید تا یه حدیش واقعا اجتناب ناپذیره. در این مواقع فقط یک توصیه میشه کرد و اونم اینه که به خدا توکل کنید. مطمئن باشید که هیچ کس جز خدا نمی تونه ارامتون کنه و بهتون ارامش بده و واقعا هم اگر کمک بخواهید ازش و به یادش باشید حتما اروم تر میشید و ازمون بهتری میدید. اگر دوست داشتید گوش دادن به قران هم ادمو اروم می کنه :)))


وقتی رفتید سر آزمون اگر سوالا سخت بود هول نشید. بدونید وقتی یه سوال سخته برای همه سخته و نه فقط برای شما. البته جا داره بگم که اگر سوالا براتون راحت بود هم مغرور نشید. شما برای گرفتن نتیجه زحماتتون موظفید که برید سر آزمون و بدون توجه به هیچ عامل خارجی، بهترین خودتون را سر آزمون بذارید و مطمئنم که اگر روی همین کار تمرکز کنید، به خوبی انجامش می دید و حسابی می ترکونید. برید و بترکونید. بهترین ها منتظرتونه :))))


نویسنده ها: میکائیل قربانی و امیرمحمد ایمانی

  • طلاهای دوره ۲۸
۲۴
فروردين

سلاام،

بالاخره آزمون 4 ام شاززز تموم شد (تمومممم شد)،

خوشبختانه (و بدبختانه برای مصحح) تعداد شرکت کننده های این آزمون به نسبت خوب بود. تقریبا 80 نفر از طریق بات تلگرام آزمون دادن و نزدیک 45 نفر هم از طریق مدرسشون. برگه ها تصحیح شدن و نمره ها اعلام شد به هر فرد!

در کل آزمون روز اول (تستی) طبق نظر اکثریت نسبت به تستی مرحله دو آسون تر بود. و تشریحی هم تقریبا هم سطح یا یکم سخت تر از تشریحی پارسال بود.

فکر میکنم به جز سوال 3 تشریحی که یکم نامفهوم بود، آزمون تقریبا اشکال خاصی نداشت. تلاشمو کردم که این آزمون مشکل خاصی نداشته باشه، از همه ی کسایی هم که بهم تو کارها کمک کردن تشکر میکنم.
تقریبا 40 نفر اول این آزمون نمره ی بالای 70 گرفتن!
این رتبه بندی نفرات برتر آزمون هست! بهشون تبریک میگیم، با برنده ی پیتزا هم هماهنگ میکنیم خودمون!
 
 
فایل ها و پاسخ ها و کلید آزمونم تو بخش امتحانات و سوالات قرار گرفت.
 
آپدیت 1: کد بات هم اینجا گذاشته میشه برای آیندگان (کلباس کبیر کدشو زده:D)
آپدیت 2: نمره ی نفر دوم 10 نمره اضافه شد. نفر 10 ام هم مشترکن یک نفر اضافه شد. با عرض پوزش:D
 
خب دیگه  همین
موفق باشید!
 
میکائیل قربانی
  • طلاهای دوره ۲۸
۰۸
فروردين

سلاااام.

ما میخوایم تو این نوروز (البته با تاخیر:D) یه آزمون مرحله 2 ای بگیریم.(احتمالا تستی هم داشته باشیم)

این آزمون نسبت به سه تای قبلی ای که گرفتیم فرقش اینه که احتمالا جامع تره و اطلاع رسانی بیشتری احتمالا بشه.

امیدوارم بتونیم تهش یه رنکینگ از نمره های نفرات برتر داشته باشیم. پس حتما این آزمونو بدین که بتونین خودتونو بسنجین و مقایسه کنید با دیگران.

اگه از مدرستون بیشتر از یک نفر میخوان این آزمون رو بدن سعی کنید که تو مدرسه آزمون بدین و از طرف مدرستون ثبت نام کنید تا یکم رسمی تر بشه آزمون براتون.

احتمالا تایم این آزمون 17 ام تا 19 ام فروردین 98 باشه.

اگه تغییری پیش اومد اطلاع میدیم. در مورد نحوه ی ثبت نام هم همینطور:))

موفق باشین:D


آپدیت 1: هووراااا بالاخره آزمون شروع شد. حداقل 4 روز برای دادن آزمون فرصت دارید. به نفرات اول تا دهم به صورت تصادفی پیتزا داده میشه:D

آپدیت 2: حتما حتما اسماتونو واقعی بنویسید. اگه از اسم های فیک استفاده کنید خوب نیست:(

آپدیت 3: هیچوقت قبول نکنین که برگه تصحیح کنین:( میمیرین:(

میکائیل قربانی

  • طلاهای دوره ۲۸
۲۶
اسفند

این پست یکم سنگینه. چون نظریه اعداد مبحث کوچیکی نیست. اما سعی کردیم جمعش کنیم. لازمه لینک هایی که گفته شده ر بلد باشید تا بتونید سوال ها ر حل کنید. همچنین تو خود لینک ها هم سعی کنید چندتا از سوالای انتهای صفحه‌شون ر بزنید!

 

مباحثی که خوبه بلد باشید:

لینک یک ترجمه یک

لینک دو ترجمه دو

  • طلاهای دوره ۲۸