صفحه ۶

فرض کنید جایگشت <a₁ , a₂ , ... , a_n> جایگشتی از اعداد 1 تا n باشد. به جایگشتی علامت دار میگوییم اگر هر عدد مثبت بین 1 تا n دقیقن یکبار به صورت منفی یا مثبت آمده باشد. مثلن <1 , 3 , -2> جایگشتی علامتدار است اما <2,-1,1> نیست.

حاصل دوران (i,j) که i<=j روی یک جایگشت علامتدار <a₁ , a₂ , ... ,a_i, a_i+1,...,a_j, ... , a_n> برابر با جایگشت علامتدار زیر است

<a₁ , a₂ , ... ,-a_j,-a_j-1,...,-a_i, ... , a_n>

ثابت کنید برای تبدیل جایگشت علامتدار <a₁ , a₂ , ... , a_n> به <a_n , a_n-1 , ... , a₁> به حداقل n-1 دوران نیاز داریم.

مهدی جعفری

(همچنین یک گراف G داریم و در آن شایان پردیس به راس F میرود و سلام کرده و آب میخورد.)

طلاهای دوره ۲۸ ۱۳۹۷/۱۱/۱۵ · ۲۲:۱۸

سوال شب سیزدهم

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

بدون مقدمه بریم سراغ سوال امشب:

عدد ۱۳ به توان ۲۰۱۹ رو در نظر بگیرید. هر دفعه رقم یکم این عدد را حذف کرده و سپس آن را با بقیه عدد جمع می کنیم. این کار را تا زمانی انجام می دهیم که به یک عدد ده رقمی برسیم. ثابت کنید این عدد دو رقم برابر دارد.

امیرمحمد ایمانی

طلاهای دوره ۲۸ ۱۳۹۷/۱۱/۱۳ · ۰۱:۲۰

cf extension

سلام ملت.

حال می کنین امسال چقد فعالیم؟

در همین راستا امروز بعد جدیدی از شاز رو افتتاح می کنیم. ما استارت یه سایت رو زدیم که هدفش اینه که مطالبی که بهمون کمک می کنه رو جمع کنیم و از زبون های دیگه ترجمه کنیم به فارسی که بتونیم راحت تر ازشون استفاده کنیم. فعلا هم بنا به اینه که سوال های CF رو که می زنیم ترجمه کنیم تا کسایی که بعد از ما می زنن بتونن راحت تر باشن. ( در همین راستا یه اکستنشن زدیم که اگه نصبش کنین و برین تو CF ، سوالایی که ترجمه شدن به فارسی میان براتون ) از این لینکه می تونین اکستنشن رو نصب کنین.

نکته : این یه کار همگانیه و اگه مشارکت شما کم باشه سریع شکست می خوره ( و ما هم دیگه از این همه شکست خسته می شیم و شاز رها میشه ). ولی اگه این ۳۰۰ دنبال کننده شاز هر کدوم ۵ تا سوال ترجمه کنن کسر خوبی از CF ترجمه می شه ! برای ترجمه سوال هم بعد نصب اکستنشن بالای سوال یه دکمه ترجمه داره که هدایتتون می کنه به گیت هاب . اگه سوالی حین ترجمه پیش اومد تو دیسکورد بپرسین جواب میدیم . بازم می گم که اگه هر سوالی که میزنید رو ترجمه کنید سال پایینی هاتون CF فارسی خواهند داشت!

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

حرف دیگه ای نیست. خدافظ

آپدیت ۱:

SGU هم هندل شد!

نویسنده: حمیدرضا کلباسی (با کاپی میکائیل)

طلاهای دوره ۲۸ ۱۳۹۷/۱۱/۱۰ · ۲۰:۰۴

سوال شب سیزدهم

سلامی دوباره

فرض کنید دور یک میز گرد ‎50‎ دختر و ‎50‎ پسر نشسته اند . ثابت کنید یک دختر و پسر وجود دارند که بین انها دقیقا یک دختر و یک پسر نشسته باشد

ارشیا سلطانی

شب خوش :)

طلاهای دوره ۲۸ ۱۳۹۷/۱۱/۰۸ · ۲۲:۲۳

سوال شب دوازدهم

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

خوبین؟

خب مثل قبل. جواب سوال قبلی رو تو دیسکورد میگیم!

و حالا سوال امشب!

درخت T با n راس داریم. به جایگشت p میگیم خوب اگه به ازای هر یال درخت که بین u,v هستش، بین P_v,P_u هم یک یال باشه.

ثابت کنید توی هر جایگشت خوب یا x ای وجود داره که P_x=x و یا x,y وجود دارن که P_y=x,P_x=y.

نویسنده: میکائیل

طلاهای دوره ۲۸ ۱۳۹۷/۱۱/۰۷ · ۲۳:۳۴

سوال شب یازدهم

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

آقا تیزی یه جمله داره میگه:‌ هه! آقا رو باش :)

ضمن یاداوری این نکته که جواب سوالات شب های قبل توی دیسکورد موجود هستش میریم سراغ سوال امشب:

یک عدد اول به نام p داریم.

ثابت کنید یال های گراف K p^2‌ (گراف کامل پی دو راسی) رو می تونیم به تعدادی K p (گراف کامل p راسی) افراز کنیم. دقت کنید که در افراز هر یال دقیقا یک بار می آید.

موفق باشید. خدانگهدار همتون.

امیرمحمد ایمانی

طلاهای دوره ۲۸ ۱۳۹۷/۱۱/۰۶ · ۲۲:۵۳

الگوریتم هفتگی-برنامه نویسی پویا

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

سوالا به ترتیب آسون به سخت سورت شدن!! تقریبن تضمین میشه که هر پستیو اگه تا آخرین سوال حل کنید کامل اون مبحث براتون بسته میشه!

تگ این هفته برنامه نویسی پویا یا همون dynamic programming(dp) هستش.

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

سوال نهم