شاززز

شاززز

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

طبقه بندی موضوعی
بایگانی
۰۱
ارديبهشت
جواب 1) کافیه ثابت کنید که از هر ستون لازم و کافیه که تنها آخرین دستور sort اون ستون اجرا بشه. لازمش که بدیهیه چون کافیه سطرها همه‌ی اعدادشون مساوی باشند و فقط در همین یه ستون با هم فرق کنند. کافیش هم تقریبا واضحه چون کلا دستوراتی که قبل از دستور sort_i میان، بود و نبودشون فقط در جابجایی افرادی مهم هست که عضو iامشون با هم یکسانه که خوب یه دستور sort_i دیگه، تغییری در اونها ایجاد نمیکنه.

جواب 2) داریم استقرا میزنیم روی n. اگه یکی از بازه‌ها کاملا در یکی دیگه قرار داشته باشه، کافیه اون بزرگه رو حذف کنیم و سپس بنابر استقرا اون k-1 نقطه‌ی مناسب رو انتخاب کنیم. حالا چون یکی از نقاط داخل کوچیکه هست، پس از بزرگه هم یکی انتخاب شده و تموم. حالا فرض کنیم حالتی هست که هیچ بازه‌ای کاملا داخل دیگری نیست. میایم همه نقاط شروع بازه‌ها رو مرتب میکنیم. حالا زودترین شروع رو در نظر بگیرید. بیاید نقطه‌ی انتهای این بازه رو بعنوان یکی از نقاط انتخابیمون در نظر بگیرید. چون همه‌ی بازه‌هایی که بین شروع و پایان این بازه، باز شدن، بعد از پایان این بازه، بسته شده‌اند(وگرنه کاملا داخله بازه‌ی انتخابیه ما میومده)؛ لذا با انتخاب این نقطه‌ی خاص، از همه‌ی بازه‌هایی که قبل از بسته شدن اولین بازه، باز شده‌اند، یک نقطه انتخاب شده. پس حالا همین کار را ادامه میدهیم. یعنی باز اولین بازه‌ای رو در نظر میگیریم که بعد از تمام شدن اولی، شروع شده. و نقطه‌ی انتهایش را بعنوان یکی دیگر از نقاط انتخابی در نظر میگریم. و همینطور ادامه می‌دهیم. واضحه که همه‌ی بازه‌ها حداقل یک نقطه‌یشان انتخاب شده. حالا میمونه ثابت کنم تعداد نقاط حداکثر k-1 هست. این هم واضحه‌ چون بازه‌هایی که ما نقاط انتهایشان رو انتخاب کرده بودیم، کاملا جدا از هم هستند، لذا اگر تعداد این بازه‌ها بیشتر از k-1 باشد، اونوقت توانسته بودیم که k تا بازه در نظر بگیریم که با هم هیچ اشتراکی ندارند و این با فرض مسئله در تناقضه.

جواب 3) یه گراف جهت‌دار وزندار می‌سازیم. اینطوری که به ازای هر حالت از چینش کتاب‌ها(حداکثر میشه دو به توان n در n فاکتوریل) یک راس میذاریم. و از راس a یک یال جهت‌دار به b با وزن i میذاریم اگر بوسیله‌ی swap_to_i بشه از حالت a به b رسید. توجه کنید که این گراف به ازای هر یال از a به b یک یال با همون وزن از b به a داره.(در حقیقت یه جورایی این رو میشه بصورت گراف بدون جهت دیدش ولی برای اثبات راحت‌تر اینجوری در نظر میگیریمش). حالا اعمال ما مثل طی کردن یک گشت توی این گراف میمونه. چون تعداد یال‌ها متناهیه زمانی ما از یک یال مجددا عبور خواهیم کرد(همینجا جهت‌دار بودنش کار رو راحت میکنه). پس یال e اولین یالی هست -مثلا با وزن i- که پس از طی چند عمل دوباره به خودش میرسه. بدیهیه که نه تنها e بلکه همه‌ی یالهای توی گذر بسته‌ی از e به e همینجوری هستن و چون یه یال توی این گذر هست که وزنش یکه(کافیه اینقدر طبق الگوریتم حرکت کنیم تا برسیم به 1 دیگه). فرض کنیم این یال 1 که بوسیله‌ی حرکات الگوریتممون توی یک گذر بستن، از a به b باشه. پس ما از a با شروع از یال 1 و طی چند حرکت میرسیم به خودش. این دقیقن مثل وقتی هست که ما از حالت اولیمون شروع کردیم به حرکت. نکته اینجان که ما اگه از راس فلان طی چند حرکت به خودش برسیم، از هر راس دیگه‌ای هم اون حرکات خاص رو انجام بدیم باز به خوده اون راسه میرسیم. بعبارت واضح‌تر حرکات ما مستقل از وضعیت کتابا هستن. لذا اگه یه راس بتونه با شروع از 1 برسه به خودش(که راس a الآن اینجوریه) راس شروع ما هم باید براش همین اتفاق بیفته.

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

  • شااززز منگولیا
۲۵
فروردين

سلام بچه ها.خوبین که؟

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

همونتور که میدونین استقرا یکی از ابزار هایه کاربردیه مرحله 2 است! تجربه ثابت کرده هر سال تو مرحله 2 دو سه تا سوال استقرا میدن...!خلاصه ستقرا ممکنه خیلی هال به آدم بده دیگه...

بگزریم بریم سره مساله ها (البتّه ممکنه راه حلّی به جز استقرا هم داشته باشن)

1)یه گرافه کامل با ۱+۲*n راس داریم که یال ها شو با 3 رنگه 1 و 2 و 3 رنگ کردیم. ثابت کنین میتونیم یه رنگ و n+1 راس رو انتخاب کنیم به طوری که اگه بقیه راس هایه گراف رو دور بریزیم بتونیم با استفاده از این رنگ از هر راسه این مجموعه  n+1 تایی به هر راسه دیگه اش رفت

2)یه گراف همبند با زوج تا یال داریم ثابت کنین که میتونیم یال هایه این گرافرو به مسیر هایه به طوله 2 افراز کنیم

3) (این مساله سخته!) ثابت کنین مجموعه رءوس هر گراف رو میتونیم به دو تا مجموعه A۱ و A۲ افراز کرد به توری که درجه هر راس در هر یک از زیر گرافهای القایی A۱ و A۲ زوج باشد

4)مساله یه 4 مرحله دوّم دوره یه 13 ام یه راه هلّه خیلی کوتاه استقرایی داره!

5)هر مریخی 100 روزه متوالی عمر میکنه.اگه مریخ کلّن 9734123871 روز عمر کرده باشه و کلّن تو تاریخه مریختویه مرّیخ 12391230151511 ای آدم زندگی کرده باشه ثابت کنین هدّقل100روز هست که تویه اون روزها "فرد" تا مریخی رویه مریخ زندگی کرده باشه

خوب بستونه دیگه . همینم زیادتون بود!خودتون برین استقرا کار کنینD:

ادیو

  • شااززز منگولیا
۲۲
فروردين
به نام اول آموزگار             که اول درسش عشق بود

سلام ملت چطورین، خوبین؟ ای بابا همچنان که همتون زنده‌اید! خوب چه خبرا؟ چه میکنید؟ خوشید؟ سلامتید؟ منم هی، بد نیستم، همچنان غرق الافی!

- متاسفانه - وبلاگمون داره پیش میره به سمت علمی شدن که البته خدارا شکر هنوز با این نویسندگان شازی که داره جای نگرانی وجود نداره، برای همین واسه اینکه لااقل از این افشین کم نیارم گفتم بیام 2 تا سوال بدم، البته اینا مال بعضی از امتحان‌های ceoi بوده که روشون الگوریتم BTM2 اجرا شده. برای همین یه دفعه ممکنه راه حل‌هایی آسون‌تر از اون چیزی که تو ذهنمه داشته باشن و بعبارتی سوال سوت بشه. اما در هر صورت سوال‌های خوبین و جدا اونقدر قشنگ هستند که کاملا پتانسیلشو دارن شبیهشون توی مرحله دوم بیاد. در مورد اینکه حلشون رو بذاریم یا نه هنوز بحثش نشده، ولی احتمالا حلشون رو خواهم گذاشت. در مورد اینکه بچه‌ها حل کنند و واسمون میل بزنن تا ما تصحیحشون کنیم هم هنوز تصمیمی گرفته نشده. ا راستی یادم رفته بود ممکنه بعضی از افراد کوته‌فکر -که امیدوارم ما از این بازدیدکننده‌ها نداشته باشیم- ندونن BTM2 چیه. محض اطلاعشون بگم BTM2 مخفف "بچپونش تو مرحله 2" هست. که به شخصه معتقدم تعداد(شاید اندکی) از سوال‌های مرحله 2 و بسیاری از سوالهای مرحله 3 توسط همین الگوریتم BTM2 ویا BTM2++ = BTM3 ساخته شدن. در هر صورت این هم سوال‌ها:

1) n عدد طبیعی روی یک خط چیده شده‌اند. با نام‌های a1 تا an. حالا ما یک حرکت مجاز داریم و آن اینست که یک i بین 1 تا کمتر از n در نظر بگیریم و ai و a i+1 را حذف کرده به جاش ai - ai+1 رو میذاریم یعنی میشه n-1 عدد. حالا هی این کار رو تکرار میکنیم تا بشه 1 عدد. مثلا یک نمونه برای n=4 اینگونه عمل میکنه:

1 12 4 9          --2-->         1 8 9         --2-->         1 -1         --1-->       2

حالا فرض کنید در حالت خاصی از سوال داشته باشیم ai=2^i یعنی اعداد اولیمون (الزامی برای رعایت این شرط در ادامه‌ی مراحل وجود ندارد) 2 و 4 و 8 و 16 و ... است. سوال اینه که ما در آخر که فقط یک عدد می ماند، چند حالت مختلف برای آن عدد وجود دارد؟(در حالت کلی سوال اینه که حداکثر چند عدد مختلف وجود دارد به ازای هر اعداد ابتدایی)

2) n پله با شماره‌های 1 تا n جلوی دروازه‌ی شهر الموت قرار دارد.(دروازه در پله‌ی n ام است) تعدادی متناهی سرباز روی این پله‌ها ایستاده‌اند(در پله‌ی iام ai سرباز). این سرباز‌ها که مال چنگیزخان هستند، میخوان بریزن و الموت رو تصرف کنند. شهردار الموت که آدم صلح طلبی(بی بخاری) هست، واسه‌ی اینکه کشتار زیادی نشه میاد پیشنهاد یه بازی میده و چنگیزخان هم که میبینه بازی شازی هست، قبول میکنه. بازی اینجوریه که هر مرحله چنگیزخان همه‌ی سربازهاش رو به دو دسته (نه الزاما مساوی و نه الزاما ناتهی) تقسیم میکنه، شهردار یکی از دسته‌ها رو انتخاب میکنه و اون دسته بر میگردن مغلستان واسه دوره‌ی طلا(که درحقیقت دودر میشن)، اما اون دسته‌ی باقیمونده هرکدوم یک پله میان بالا. و بازی همینجور ادامه پیدا میکنه. حالا اگه حداقل یک سرباز برسه به دروازه‌ی الموت(پله‌ی nام) شهردار، الموت رو تسلیم میکنه، اما اگر همه‌ی سربازها برگشتن... خوب معلومه دیگه چنگیزخان از دنیا سوت میشه...

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

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

بطور مثال اگر توی پله‌ی n-1ام 1 نفر و توی پله‌ی n-2ام 2 نفر ایستاده باشن، اونوقت چنگیزخان افراد پله‌ی n-2ام رو میکنه یه دسته و اون یکی سرباز رو هم میکنه یه دسته. حالا شهردار مجبوره اون دسته‌ی نفر توی پله‌ی n-1ام رو حذف کنه و در مرحله‌ی بعدی چنگیزخان 2 نفر در پله‌ی n-1ام خواهد داشت، که با تقسیم اونها به 2 دسته خواهد برد.

 

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

خوب دیگه زیاد از وقت همچون طلایم گرفته شد، کسی کاری چیزی نداره؟ پس فعلا

یا حق

  • شااززز منگولیا
۲۲
فروردين
سلام! خوبین؟ خوب الاهی شکر! الّافی خوش میگزره؟
ما(بهتره بگم من:D) فرضمون اینه که همه اونایی که این وبلاگ رو میخونن حداقل یکمی رو الّافی میکنن تو زندگی
خوب حالا که نزدیکه مرحله دوّمه (به درک) گفتیم بزار این مدّت رو یه سری مساله بگیم ! بهتره. بد نیست که با چند تا مساله یه نه خیلی اسون شروع کنیم!

۱)یه گروه داریم از ۱+ ۲*n نفر. از بین هر n+1 نفر حتماً یه نفر هست که بقیه رو میشناسه. ثابت کنین 1 نفر هست که همه رو میشناسه!

۲)یه جدوله n*n داریم که توش عدد هایه 1 و -1 و 0 رو نوشتیم. به طوری که تویه هر سطری دقیقن یدونه 1 هست و یدونه -1. هر باری میتونی 2 تا سطر یا 2 تا ستون جدول رو بگیری و جایه اون 2 تا رو با هم عوض کنی .ثابت کنین میتونیم به جدولی برسیم که جایه 1 ها و -1 ها نسبت به جدوله قبلی توش عوض شده.

۳)یه ترازوی 2 کفه ای داریم که وزنه اجسامه سمته راستش منهایه وزنه اجسامه سمته چپش رو به ما گزارش میده! 27 تا وزنه به وزنهایه1و 3 و 9 و ... 3 به توانه 26 هم داریم.حداقل بار هایه استفاده از از ترازو برایه اینکه این وزنه ها رو به ترتیبه وزن مرتّب کنیم چند تاست؟

۴)یه جدول 200*200 داریم که خونه هاش با 2 رنگ رنگ شده! سفیدو سیاه! اختلاف خونه هایه سفید با سیاه برابر 404 است!ثابت کنید یه مربع 2*2 هست که تعداده فردی خونه سفید داره!

۵)یه صفحه یه 100*100 داریم که خونه هاش با 4 رنگ رنگ شده .هر سطری و هر ستونی از هر رنگ دقیقن 25 تا داره. ثابت کنین میتونیم 2 تا سطر و 2 تا ستون رو انتخاب کنیم به طوری که 4 تا خونه یه محل برخوردشون از 4 رنگه مختلف باشه!

۶)یه گراف ساده داریم که درجه یه هر راسیش حداقل 3 است ثابت کنین که یه دور تویه گراف وجود داره به توری که طوله دور مضربه 3 نباشه

یه مسله یه باحال( مرحله دوّمی نیست ولی من کلّن حال میکنم با مساله یه با حال چه مرحله دوّمی چه غیره مرحله دوّمی):
ثابت کنین بازه (۱و ۰) با R متناظر است!( به نظره من که اگه حلّشو تا حالا نشنیدین حتماً بشینین حلّش کنین!
خوب دیگه بستونه. دستم درد نکنه!:Dخوش باشین
فعلاً خدا خافظ
  • شااززز منگولیا
۲۱
فروردين

به نام خدا

سلام

خوبین؟ خوب به من چه

آقا ما با برو بچز (n تا از طلا هایه المپیاده کامپیوتره ساله 84 به بعد (n عضوه R)) بیکار بودیم گفتیم

یه وبلاگ بزنیم! ایشالا که مفید باشه!

قرار نیست این وبلاگ فقط مربوت به مرحله اوّل .دوم یا سوّمه المپیاد باشه

حتّا ممکنه زمانی مطالبه کامپیوتری یه غیرالمپیادی هم توش گفته بشه

ولی خوب بنا به فراخور زمان و مکان تغییر میکنه!

البتّه الان که نزدیکه مرحله دوّمه بیشتر سعی میکنیم که مطالب به درده مرحله دوّم بخوره!

و امّا شاززز؟ چرا اصلن شاززز؟ اسن یعنی چی؟اصلن شما چرا میخاین بدونین شاززز یعنی چی!

 مثلن مگه شما میدونین که هرم خؤو پوس چیه؟ میدونین الفاقنطورس اسم کدوم ستاره است؟

(تازه این اسم ها همشون وجوده خارجی دارن!!! )

نسبیته انیشتین فقط همین قدر در مورده شاززز به ما اطلاعات میده که :

شاززز شدیدن با مفاهیمی چون : گراف. وست. گذر. باندی و مخسوسن مورتی رابطه داره ! و کاملن مبرهن شده که نسبیت قدرته توجیهه شاززز رو نداره!یه ایده یه کاملن جدید نیازهاسن بیخیال! درگیر نشین!

اینم از پست اوّلمون

راستی! سال نو مبارک!

فعلا خدا نگهدار

 (راستی شما می دونین تو فنت فارسی چه جوری میشه ویرگول گذاشت؟)

  • شااززز منگولیا