پرش به محتویات

صفحه ۱۷

راه حل سوالات آزمون عملی سوم شاززز

سوال 1:
تو این سوال می دونیم که عدد نهایی تو int جا میشه ولی ممکنه وسطش overflow بشه برای این که بتونیم این عدد گنده رو ذخیره کنیم استفاده از bignum مناسب نیست چون اگر برای هر رقم یک بایت هم فضا اشغال بشه حدود 4 ترابایت فضا نیازه!!!
راه حلی که می خواستیم شما بهش برسید این بود که تجزیه این عدد به عوامل اولش رو نگه دارید که خب خیلی هاتون هم بهش رسیدید.ولی نکته اصلیش این بود که پیدا کردن عوامل عدد رو با رادیکال گرفتن از عدد و ... پیاده سازی نکنید.به جای این کار می تونید از الگوریتماستفاده کنید که زمان خیلی کمتری مصرف می کنه.خیلی از افراد همینطوری پیاده سازی کردن واسه همین دیگه کد غربال رو نمی ذاریم می تونید از تو scoreboard کد های مختلف رو نگاه کنید.
راه حل دوم:اگر x رو جواب نهایی فرض کنیم می دونیمx>0 و x
 x%(1000000009)=x
خب حالا می تونیم همه عملیات هامون رو mod این عدد انجام بدیم.از اونجایی که این عدد اول هستش و همه اعداد ورودی ازش کوچیکترن موقع تقسیم می تونیم ازقضیه کوچک فرمااستفاده کنیم که تو پست های قبلی توضیح داده بودیم در موردش.این راه حل از غربال خیلی سریعتر بود!
در مورد تست ها:
تست 1:اگر با همون ترتیب ورودی ضرب و تقسیم عادی انجام میدادید کار می کرد!
تست 2:مثل تست 1 فقط باید تو long long جواب رو ضرب و تقسیم می کردید
تست 3:اگر رادیکالی تجزیه می کردید نمره اش رو می گرفتید
تست 4:یه خورده باید همون رادیکالتون رو بهینه سازی می کردید
تست 5:می تونستید یه جوری ضرب و تقسیم کنید که overflow نشه.مثلاً اگه ضرب جواب فعلی در هر عددی باعث overflow بشه حتماً یه عددی وجود داره که می شه بهش تقسیم بشه و دوباره جوابمون کوچیکتر بشه.
تست 6-10:از اینجا دیگه تست ها سخت می شد و کد هایی رادیکالی به سختی accept می شدن.

سوال 2:
ایده مشترک دو قسمت سوال این بود که پاره خط ها رو بر حسب ارتفاع یه سمت ثابت مرتب کنید.پس از این بعد فرض می کنیم پاره خط i ام ارتفاع سمت چپش از پاره خط j ام بیشتره اگر و تنها اگر i>j. همچین [h[i رو ارتفاع سمت راست پاره خط i ام فرض می کنیم.
قسمت اول:شرط لازم و کافی برای این که پاره خط iوj با هم تقاطع داشته باشن با فرض این که j>i هستش اینه که [h[j کوچکتر از [h[i باشه.
قسمت دوم:یه مجموعه که خاصیت گفته شده رو داره در نظر بگیرید.پاره خطی که سمت چپش از همه پایین تره سمت راستش باید از همه بالاتر باشه در غیر اینصورت با همه پاره خط های دیگه تقاطع نداره.با استفاده از همین ایده می تونید ثابت کنید که جواب بزرگترین زیردنباله نزولی تو آرایه h هستش.بزرگترین زیر دنباله نزولی یا صعودی یه مسئله خیلی معروف هستش که راه حلش رو می تونید ازاینجاببینید.
سوال 3:

در این سوال یک گراف به ما داده شده است و می خواهیم کمترین تعداد یال را حذف کنیم تا راس های 1 تا k در هیچ دوری نباشند.

ابتدا همه ی یال های گراف مثل v-u که u>k , v>k را در نظر می گیریم (می شه به راحتی اثبات کرد که این یال ها در یکی از جواب های مسئله وجود دارند). هر مولفه ی گراف درست شده را یک راس بگیریم یال های باقی مانده (یال هایی که حداقل یکسرشان از این k راس است) باید یک جنگل تشکیل دهند در غیر این صورت یکی از این k راس در یک دور می افتد. به هر صورتی که این یال ها را انتخاب کنیم تا گراف جنگل بماند به یک جواب بهینه می رسیم. برای این کار هم می توان از الگوریتمdsuاستفاده کرد.
پیاده سازی ای سوال رو هم می تونید ازاینجادانلود کنید.


نوشته شده توسط محمدامین خشخاشی‌مقدم(سابق) در سه شنبه ۲۲ بهمن۱۳۹۲ و ساعت 22:17 |

شااززز منگولیا ۱۳۹۲/۱۱/۲۱ · ۲۰:۳۱

آزمون عملی سوم

سلااااااام :)

خب بالاخره بعد از 2 ماه غیر فعال بودن شااززز (به دلیل امتحانای ترم و دوره طلا و ...) می خوایم یک آزمون دیگه بگیریم.

این آزمون هم مثل آزمون های قبلی قراره 3 سواله و 2 ساعت باشه. آزمون حمعهساعت 7شروع می شه.

کسانی که قبلا ثبت نام نکردن می تونن ازاینجاثبت نام کنن.

اگر همچنان تعداد شرکت کننده ها کم باشه این آزمون ها رو متوقف می کنیم :|

 موفق باشید.

-----------------------------------------

زمان آزمون به دلیل تداخل داشتن با کانتست Topcoder به ساعت 5 تغییر کرد.

-----------------------------------------

ثبت نام ساعت ۳ متوقف می شه.اکانت های زیر حذف شدند:

fhshemi,fshashemi,MaRaGo,Wrong

آزمون با 15 دقیقه تاخیر شروع میشه یعنی از ساعت 5:15 تا 7:15

آزمون شروع شد!

سوالات رو ازاینجادریافت کنید.

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

خب سرورو رسماً ترکوندید :)

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

اگر اعصابتون خورد شد ، وقتتون تلف شد یا هر چیز دیگه به بزرگواری خودتون ببخشید :)

موفق باشید.

-----------------------------------------

جاجدرست شده وتا یک هفته باز می مونه. می تونید کدهاتون رو سابمیت کنید.scoreboardهم فعال شده.

از الان می تونید سورس کد بقیه رو هم تو scoreboard ببینید:اول روی اسم کاربر کلیک کنید و بعدش جلوی اسم سوال دکمه Show رو بزنید.اگر مشکلی مشاهده می کنید Ctrl+F5 بزنید.راه حل های اصلی رو هم به زودی اضافه می کنیم.

شااززز منگولیا ۱۳۹۲/۱۱/۱۷ · ۱۸:۰۷

مرحله اول نزدیک است

سلام به همگی

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

1-سال دومی ها و سال سومی هایی که سال پیش مرحله اول قبول شدند باز هم از خودشون مرحله اول امتحان بگیرن.این کار هم باعث می شه دستتون(مغزتون) گرم شه و هم این که روز اول مرحله دوم(به احتمال زیاد) تستی هستش و خب اونجا هم می تونه کمکتون کنه.

2-تست زدن با تشریحی امتحان دادن از زمین تا آسمون فرق داره.سعی نکنید که اثبات کنید جوابتون درسته.منظورم این نیست که شانسی بزنید ولی می تونید از تکنیک هایی مثل حذف گزینه و یا در اوردن مثال های کوچیک و الگو یابی استفاده کنید.راهی که 5 دقه طول می کشه تا به جواب برسه ولی مطمئن هستید که به جواب درست می رسه خیلی بهتر از راهی هستش که کمتر طول می کشه ولی ممکنه اشتباه باشه.به طور کلی از این که امتحان تستی هستش نهایت استفاده رو ببرید.خوب تست زدن خیلی می تونه تو مرحله دو کمکتون کنه.خیلی!!!

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

4-اگر وقت اضافی داشتید می تونید تمرین های کتاب های مختلف رو حل کنید از جمله:ترکیبیات علیپور(جلد زرد)،آنالیز ترکیبی،جلوه هایی از ترکیبیات و الفبای المپیاد ریاضی

------

5-  اگه بین دو گزینه شک داشتین رندوم بزنین حتما.(طبق امیدریاضی. امیدریاضی میگه اگه کلا هم رندوم بزنید صفر میشید پس خیلی جای نگرانی نیست!)  البته تو این موضوع بحث داشتیم و رای 2 به 2 بود. برای این که حق اون دو نفری که گفتن رندوم بزنید ضایع نشه این بند هم اضافه شد :)

آرشیو سوالات گذشته رو می تونید ازاینجادریافت کنید.

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

شااززز منگولیا ۱۳۹۲/۱۱/۱۶ · ۱۷:۴۴

لغو موقتی آزمون

سلام بچه ها :)

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

موفق باشید

------------------------

آقای اسدی زحمت کشیدن و یه نسخه ی خیلی خوب از سوالات المپیاد روسیه ( 1994 - 2013) درست کردن. میتونید ازاینجااین فایل رو دریافت کنید. این فایل از وب‌سایتجی‌پکهم قابل دریافت است.

شااززز منگولیا ۱۳۹۲/۱۱/۰۹ · ۱۹:۴۷

آزمون پنجم شاززز

سوال اول :

ازون جا که سوال اشتباه از آب دراومد (با صورت سوال اصلی ای که مد نظر داشتم فرق داشت) یک نکته خیلی مهم راجع به سوال های اشتباه میگم. سوالی که تو یک آزمون اشتباهه نه حذف میشه و نه نمره ش پخش میشه بلکه شما موظف هستین که مثال نقض اون سوال رو در بیارید.  (برای همه ی n ها باید مثال نقض بیارید یا اثبات کنید).

سوال دوم‌:
یک گراف شونزده راسی بسازید. اگه آقای آ‌ آقای ب رو نگاه میکرد از آ‌ به ب یک یال بذارین. حالا درجه ورودی و خروجی هر کس تو این گراف ۷ ه (چرا؟). حالا یازده نفر رو در نظر بگیرید یکی از این یازده نفر هست که به هر ده نفر دیگه یال داره (ورودی یا خروجی). حالا اون ده نفر یک دور دارن . با استفاده از این دور و این که اون یک نفر که کنار گذاشتین به همه یال داره ثابت کنید دور به اندازه یازده هم داریم.
سوال سوم:
این سوال که سوال خیلی خیلی سختی بود ما پیشنهاد نمیکنیم که راه حلشو بخونید. ولی راه حلشو کامل میگیم.
اول این سوال رو برای ده ربات حل میکنیم. بعد از راه حل این برای ۳ کمک میگیریم. (اگه میخواین بیشتر رو این سوال فکر کنید دیگه ازینجاش نخونین)
از استقرا قوی استفاده میکنیم. حکم استقرا میگه اگر ما log n مامور داشته باشیم میتونیم درخت رو بگردیم.
همون طور که میدونید فرض استقرا همون حکمشه برای حالت های کوچیکتر پس ما لازم نیست فرض استقرا رو بنویسیم :)
حال هر ده مامور در یک راس جمع میشوند(اسم این راس را مقر میگذاریم). اگر این راس را از گراف حذف کنیم‌ ، تعدادی درخت به وجود می‌آید که از این تعداد حد اکثر یکی از آن ها تعداد راس هایش بیش از نصف است. طبق فرض استقرا باقی درخت ها با ۹ مامور گشته میشوند. پس ما باقی درخت ها را با ۹ مامور میگردیم. یک مامور هم در مقر نگهبانی میدهد که سوسک از درختی به درخت دیگری نرود. حال اگر ۹ مامور سوسک را پیدا نکنند به مقر برمیگردند. و قسمت بعدی کار آغاز میشود (گشتن در درختی که بیش از نصف راس ها را دارد). هر ده مامور روی یالی که به این درخت میرود حرکت میکنند و داخل راسی جدید میشوند. این راس را مقر جدید میگذارند و یکی در این راس نگهبانی میدهد. قطعن سوسک به بخش هایی از گراف که قبلن گشته شده نمیره.
پس میتونیم فرض کنیم اون درختا وجود ندارن و داریم تو یه درخت کوچیککتر با ده مامور میگردیم. دوباره همین کارو با راس مقر میکنیم تا کل درخت گشته بشه. :)
خب اگه این قسمت رو نفهمیدین از این جا به بعد رو هم نمیفهمین :) پس سعی کنین این قسمت رو بفهمین
اگر توجه کنین مقر های ما تشکیل یک مسیر رو میدن توی درخت که اگه ما اون مسیر رو حذف کنیم تمام درخت های باقی مونده کمتر از نصف تعداد راس های ما رو دارن.
حالا ما اگه بتونیم مسیری پیدا کنیم که با حذف کردنش تمام درخت های باقی مونده کمتر از ۱/۳ راس ها رو داشته باشن. میتونیم این کارو با ۶ رباتم بکنیم.
(یه مامور میذاریم میشه ۳۳۳ راسی. باز تو مقر جدید یه مامور میذاریم نگهبانی بده چند تا ۱۱۱ راسی میمونه. یا مامور جدید میذاریم چند تا ۳۶ راسی میمونه. یکی دیگه میذاریم چند تا ۱۱ راسی میمونه. یکی دیگه بذاریم چند تا سه راسی میمونه. که درخت سه راسی یک مسیره با یک مامورم میشه گشتش)
حالا میخوایم ثابت کنیم چنین مسیری وجود داره. دوباره استقرا میزنیم. اولین نکته اینه که راس درجه ۲ اگه وجود داشته باشه میتونیم حذفش کنیم و به جاش دو تا همسایه شو به هم وصل کنیم و استقرا بزنیم. پس راس درجه دو نداریم.
 اگه راسی وجود نداشته باشه که با حذفش بیشتر از یک درخت با کمتر از یک سوم راس ها به وجود بیاد مانند مثله قبل عمل میکنیم. یعنی ۶ نفر رو میذاریم تو یک راس دلخواه. سپس با ۵ نفر درخت هایی که کمتر از یک سوم دارن رو حل میکنیم بعد همگی میریم به درختی که بیشتر از یک سوم داره.
حالا اگه راسی وجود داشت که با حذفش دو تا درخت با بیش از یک سوم به وجود میومد (قطعن سه تا به وجود نمیاد :) ). خب فقط این راس و دو درختی که بیش از یک سوم راس دارد در نظر میگیریم و باقی درخت ها را حذف میکنیم (حد اقل یک درخت حذف میشه چون درجه همه راسا بیشتر از دو بود). حالا طبق فرض استقرا تو این درخت کوچکتر مسیری وجود داره که با حذفش همه درختای باقی مونده کمتر از یک سوم راس هارو دارن. همین مسیر تو گراف اصلی هم این خاصیت رو داره :)

شااززز منگولیا ۱۳۹۲/۱۰/۰۴ · ۲۰:۲۷

آزمون تستی شاززز

درود بر همه :)

امسال مثل پیارسال شاززز قصد داره یک آزمون شبه مرحله 1  برگزار کنه. این آزمون قراره در تاریخ ۳ بهمن (اولین پنج شنبه بهمن) و به دو صورت حضوری (داخل مدرسه خودتون یا سمپاد شهرتون) و غیر حضوری (آنلاین)برگزار بشه. ما نهایت تلاشمون رو می کنیم که به مدارس مختلف خبر رسانی کنیم و سطح آزمون رو به سطح امتحان مرحله یک نزدیک تر کنیم.طراحای سوالات هم طلاهای امسال هستند.

روش شرکت حضوری در این آزمون :

به دلیل بسته بودن دست ما در ارتباط با مدارس (مثلپیارسال) خبر رسانی از طریق خود شماست. هر کسی که این پست رو میبینه به مدرسه شون بگه که به این ایمیل اعلام آمادگی کنن ( sh44zzz@gmail.com ).

روش شرکت در آزمون آنلاین :

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

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

شااززز منگولیا ۱۳۹۲/۰۹/۲۵ · ۲۰:۱۴

بررسی آزمون عملی ۲

سلام !

ببخشید یک کم دیر شد سرمون شلوغ بود و وقت نداشتیم.

خب بریم سر آزمون:

سوال 1: اگر همه خونه هایی که عدد های اول با هم تقاطع دارن رو در نظر بگیریم و برای هر کدومشون یه عدد خاص بنویسیم،مسئله خیلی راحت تر می شه.مثلاً اگر تو جدول دوم رقم 4 تا خونه گوشه مربع رو فیکس کنیم.بعدش کافیه حساب کنیم چند تا عدد اول هستند که با یک رقم خاص شروع و با یک رقم خاص دیگه تموم می شن.و این اعداد رو در هم ضرب کنیم.می تونیم با یه پیش پردازش همه این حالت ها رو به دست بیاریم.بعدش کافیه که همه حالت های 4 خونه گوشه مربع رو بررسی کنیم که این تعداد هم زیاد نیست.تو جدول سوم هم دقیقاً با این روش می شه جواب رو به دست اورد.

سوال 2: این سوال با استفاده از الگوریتم داینمایک حل می شه. و داینامیکتون رو باید به این شکل تعریف کنید. di,j: کمترین هزینه برای رسیدن به مربع i ام به طوری که با پرش به طول j به آن برسیم.

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

سوال 3: می دانیم گوشه n ام این جدول برابر است با n/2+1) * (n/2 + mod 2) +1) و از این طریق می توان A های خواسته شده را به دست آورد.

حال یک گراف وزن دار می سازیم که راس های آن 1 و n و همه ی A و B ها است و به ازای هر AوB یک یال به وزن یک می گذاریم. حال همه ی راس ها را به صورت مرتب شده در یک آرایه نگه می داریم و راس i ام این آرایه را siمی گیریم و بین siو si+1یال به وزن si+1 - si+1 می گذاریم. حال با استفاده از الگوریتمdijkstra طول کوتاهترین مسیر بین راس 1 و n را به دست می آوریم.


صورت سوالات ، تست کیس ها و کد سوالات رو می تونید از اینجادانلودکنید.

این هفته به دلیل برگزاری مسابقه izocup آزمون شاززز نخواهیم داشت.

در کل تعداد شرکت کنندگان در آزمون های عملی خیلی کمه و اگه همینجوری پیش بره آزمون های کمتری برگزار خواهیم کرد (مثلا 1 یا 2 ماه در میان) پس به دوستاتون بگید که شرکت کنن.

جاج این آرمون هم تا این جمعه باز است.

موفق باشید :)

-----------------------------

پ.ن: لینک ها درویکی شاازززیاآپدیت شد و مسائل داینامیک و سوالات المپیاد روسیه به آن اضافه شد.


شااززز منگولیا ۱۳۹۲/۰۹/۲۴ · ۲۲:۵۸

آزمون عملی دوم

سلام :)

این هفته قراره آزمون عملی دوم رو  مثل آزمون هفته گذشته برگزار کنیم. زمان آزمون 2 ساعته،در روز جمعه از ساعت 7 تا 9 ولی ممکنه کمی زمان آزمون تغییر کنه پس حتما شاززز رو چند ساعت قبل از شروع آزمون چک کنید.

از اینجا هم می تونید ثبت نام کنید.کسانی که هفته پیش ثبت نام کردند لازم نیست دوباره ثبت نام کنن و این هفته هم می تونن با همون اکانت ها وارد بشن.تا پنج شنبه شب هم مهلت ثبت نام هست.

خوش باشید

----------------------------------------

آزمون ساعت 7 شروع میشه.تو این آزمون scoreboard هم داریم.

سوالات رو می تونید ازاینجادریافت کنید.

برای وارد شدن بهاینجامراجعه کنید.

آزمون به پایان رسید. می توانید نتایج را ازاونجادریافت کنید

جاج تا فردا باز است و می نوانید کد هاتون را سابمیت کنید.

شااززز منگولیا ۱۳۹۲/۰۹/۱۱ · ۱۷:۵۷

۱ ۱۶ ۱۷ ۱۸ ۳۸