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

زنگ حل مساله

جمعه, ۲۱ تیر ۱۳۹۲، ۰۳:۰۸ ب.ظ

سلام بچه‌ها

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

توضیح: هر هفته یک فایل به شکل زیر فرستاده می‌شود که شامل سه سوال است که به ترتیب آسون، متوسط و سخت خواهد بود (البته امکان دارد که سطح سوالات در هفته‌های مختلف کمی متفاوت باشد) و شما یک هفته فرصت دارید که روی این سوالها فکر کنید.

مساله‌های این هفته

موفق باشید.

۰ ۹۲/۰۴/۲۱

جواد عابدی گزل آباد

المپیاد کامپیوتر

هفته اول

زنگ حل مساله

سوال تئوری

۲۱ تیر ۹۲ ، ۲۰:۲۰

امیر

سلام . اگه می شه سطح سوالات رو بالا ببرید

این سوالات در حد چه مرحله ای هستن؟

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

اگه میشه همه ی مباحث رو پوشش دهید(گراف و الگریتم و ترکیبیات و نظریه زبان ها و...)

با تشکر

۲۲ تیر ۹۲ ، ۰۲:۴۰

RezaSi

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

من ایده هام رو می گم ، اگه میشه چک کنید درسته یا نه :

1) از یه طرف صف شروع می کنیم ، یکی یکی می ریم جلو و ...

2) n=3k و n=3k+2 ، استقرا می زنیم ...

3) استقرای قوی می زنیم ... تقریبا راهم اینجوریه که تا 6 رو می شه ساخت .. حالا 6 خودش مقسوم علیه 24 هستش ، پس 6+6 رو میشه ساخت ( همونطوری که تا 6 رو ساختیم حالا 6 + تا6 رو می سازسم !!) و حالا 12 + 12 و ... (فکر کنم خیلی بد گفتم !! :) البته من دیگه المپیادی نیستم که بگین با اینجوری نوشتن مرحله 2 قبول نمی شی ... چون از همین لحاظ قبلا ضربه خوردم ... :))

ایشاالله این کارا ادامه پیدا کنه !!

راستی سوالای قبلیتون توی http://contest.irprogramming.ir/ هست ؟؟ اگه آره من یوزر و پس از کجا باید بگیرم ؟؟

۲۴ تیر ۹۲ ، ۱۲:۵۰

Slm kheili mamnun az soala faghat chand ta chiz : 1- soale aval baraye man sakht tar az solaye dg hal shod ba vojude in ke asun tar gharar bude bashe , khob in moshkele mane aya (ake yeki bem gof momkene ke natunam soalaye sade ro hal konam va sakh fek konam )age moshkele mane baraye in moshkel ch kar konam?? 2- soale 2 tekrarii buud !! Ltfan age mishe soale tekrarii nazariin

Kheili mamnun

۲۴ تیر ۹۲ ، ۱۵:۴۶

RezaSi به Me

سوال 1 چون ایده اش خیلی تکراری نبود فکر کنم باهاش مشکل داشتی ... فکر کنم شبیهش توی المپیاد ریاضی اسپانیا(برزیل؟) اومده بود ... اونجا با مهره های سیاه و سفید بود و گفته بود ثابت کنید یه جایی هست که تعداد مهره های سیاه و سفید یکی می شن ! :D

۲۴ تیر ۹۲ ، ۱۹:۳۴

Mr.ink

سوال یک رو اینطوری حل می کنیم که می گیم اولین 100 عضو رو انتخاب می کنیم حالا فرض کنید تعداد افراد سیاه (مثلا روستای b)بیش تر از افراد روستای a(سفید) هست در این 100 نفر(اگر 50-50 باشد که مسیله حل است)

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

ببخشید توضیحم خیلی بد شد!

۲۴ تیر ۹۲ ، ۲۰:۱۴

Mr ink va rezasi mersiii :) !! Hala be nazaretin mesal naghzam baraye 120 ta a va 120 ta b dorostee ???

Saf be shekle zir bashe :

49 ta a , 51 ta b , 49 ta a , 51 ta b , 22 ta a , 18 ta b

Tedade a ha hamishe kuchek tar mosavie 49 e !!!

۲۴ تیر ۹۲ ، ۲۳:۲۴

doost

salam

didam hich ki hal-e soale 1(bakhshe aval) ro kamel nagof goftam khodam begam:
har 100 nafare motevali ro ye goroh migam.
lemma 1: hade aghal ye goroh vojod dare ke to on hade aghal 50 nafar az A hastan
esbat: 100 nafare aval(goroh 1) va 100 nafare akhar(goroh101) ro dar nazar migirim. chon dar mojmo dar in 2 goroh 100 nafar az A hastan pas to yeki az in 2 goroh hade aghal 50 nafar az A hastan
lemma 2: hade aghal ye goroh vojod dare ke to on kamtar az 50 nafar az A hastan.
esbat: mese ghabli. gorohe 1 va 101 ro ham 100 nafar az A daran pas to yeki az in 2 goroh kamtar az 50 nafar az A hastan
lemma 3: agar tedad afrade A dar gorohe i ro x va tedad afrade A dar gorohe i+1 ro y begim darim |x-y|<2
esbat: ba hazfe nafare aval az gorohe i va ezafe kardane nafare akhar az gorohe i+1 hade aksar 1 nafar az A be in goroh ezafe va hade aksar 1 nafar az A az in goroh hazf mishe. pas dar kol darim |x-y|<2
natije lemma 3: ba harekat az gorohe i ta gorohe j tedad azaye A dar har marhale hade aksar yeki ezafe ya yeki kam mishe.
hala age az on gorohi ke hade aghal 50 ta az A ro dare be on gorohi ke kamtar az 50 ta az A dare harekat konim(yani hey nafare aval(ya akhar) ro hazf konim va nafare badi ro ezafe konim) hatman az adade 50 migzarim :D

khosh bashin

(az soal ham khosham omad :D)

۲۴ تیر ۹۲ ، ۲۳:۴۶

مثال نقض برای 120 تا من یه دونه راحتشو زدم.

40 تا سفید

60 تا سیاه

حالا اگر قرار باشه 50 تا سفید برداریم حتما باید 60 از دو تا سفید آدم برداریم که یعنی 60 تا سیاه وسط رو هم برمیداریم پس هیچ راهی وجود نداره که بین 100 نفر 50 تا سفید با 50 تا سیاه داشته باشیم.

۲۴ تیر ۹۲ ، ۲۳:۴۷

ببخشید متن بالا اون به صورت زیر اصلاح میشه:

حالا اگر قرار باشه 50 تا سفید برداریم حتما باید از دو تا گروه سفید آدم سفید برداریم که یعنی 60 تا سیاه وسط رو هم برمیداریم پس هیچ راهی وجود نداره که بین 100 نفر 50 تا سفید با 50 تا سیاه داشته باشیم.

۲۵ تیر ۹۲ ، ۱۴:۴۳

اسماعیل نادری

سلام

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

الان تابستونه و سرتون احتمال زیاد خیلی خیلی شلوغ نیست

دوستان هم فارسی تایپ کنن بهتره!

(چون در اون صورت اکثر وقتا آدم حالشو نداره انگلیسیو بخونه)

۲۶ تیر ۹۲ ، ۰۱:۵۱

سید علیرضا رضایی اصل

سوال 1:بخش اول:

200 نفر رو به دو دسته 100 تایی تقسیم میکنیم حالا یکی از این دو صف یا دقیقا 50 نفر از شهره اوله(از این به بعد بهشون میگم کوتوله) هست که خوب مسئله به خیر و برکت حله یا یکی بیش از 50 کوتوله توشه که میتونیم این کار را انجام دهیم:

از طرفه اتصال دو صف هی یکی میدیم به دسته مورد نظرمون و هی از اون یکی طرفش کم میکنیم حال چون سه حالت برای اینکار وجود داره-که یکیش اینه که یکی به تعداد کوتوله ها اضافه بشه یا یکی کم بشه یا تغییر نکنه-تعداد کوتوله ها در صف ابتدایی ما که بیش از 50 بود چون فقط یکی یکی ای تغییر میکنه و به یک عدد کمتر از 50 هم رسیده پس قطعا یک جا به 50 رسیده.

قسمت دوش هم دوستان گفتن و مثال هم زدن و کلا امکان نداره

سوال ذو:

جواب:

اعداد بخش پذیر بر 3 و یه دونه مونه به اعداد بخش پذیر بر سه به جز (2و3) -علت علمی نونشتن فرموله جواب خراب شدن اون در کامنت ها بوده ها حالا نگید بی سواد بوده-

اثبات:

برای 5و6و8و9 یک راحه دسته بندی می پیداییم(!!)

5:-1و4-2و3-5

6:-6و1-2و5-3و4

8:-8و4-7و5-1و2و3و6

9:-9و1و2و3-7و8-4و5و6

جال استقرا میزنیم و میگیم فرض میکنیم باری عدد الف(فارسی را پاس بدارید:))قضیه ی ما درسته حالا باید برای الف +6 ثابت کنیم و این هم کاری نداره چون 6 عدد بعدی را میتوان به 3 دسته تقسیم کرد-اولی با شیشمی ...دومی با پنچمی...سومی با چهارمی-سپس این سه دسته را به سه دسته الف اضافه میکنیم وو به این ترتیب ثابت میشه باری اعداد یکی بزرگ تر از اعداد بخش پذیر بر 3 هم کلا نمی شه چون مجموعشون بر 3 بخش پذیر نیست.

سوال 3:

از ان ضایس که استفرا میتونه مشکل گشا باشه پس استقرا میزنیم.

پایه : 3!=6

1=1

2=2

3=3

4=1+3

5=2+3

6=6

فرض برای عدد الف فاکتوریل قضیه درسته حال باید برای الف به اضافه یک اثبات کنیم.

ما فرضیدیم که میشه ار 1 تا الف فاکتوریل را ساخت و جالب تاک است که بدانیم تمام مقسوم علیه های الف فاکتوریل از عامل های اول الف ساخته شدن(اصلا هم جالب ناک نیست گفتم اونو بگم عمیق تر بخونید)حال اگر تمام اعدادی را که باهاشون اعداد یک تا الف رو میساختیم رو ضرب الف به اضافه یک بکنیم دقیقا از اعداد 0 تا الف +1 فاکتوریل رو الف تا در میان با الف بار استفاده از مقسوم های الف+1 فاکنوریل ساخته ایم حال چون اعداد 1تا الف هم جز مقسوم علیه های الف+1 فاکتوریل هستن و هم ازشون استفاده نشده(چون کوچک ترین عددی رو که ساختیم الف+1 بوده)میتونیم باقی اعداد را با اضافه کردن اعداد 1 تا الف به اعدادی که الف تا در میون ساختیم تمام اعداد 1 تا الف +1 فاکتوریل رو بسازیم.

مثال:

همون 3! رو در نظر بگیرید حالا هر عدد 1 تا 6 رو که ساختیم رو هم خودشون رو و هم اعدادی که با هم جمع شدن تا اون ها ساخته بشن رو ضرب 4 کنید

میشه مثله زیر:

(1*4)=(1*4)

(2*4)=(2*4)

(3*4)=(3*4)

(4*4)=(1*4)+(3*4)

(5*4)=(2*4)+(3*4)

(6*4)=(6*4)

می بینیم که اعداد 4 و 8و12و16و20و24 ساخته شدن (با حداکثر سه بار جمع -البته دو باره ولی به خاطر نشکوندن دل مسئله سه بار-)و اعداد 1تا 3 هم استفاده تشدن پس به این ترتیب میتونیم به اضافه کردن این اعداد به اعداد 4و8و... اعداد 1تا 24 رو بسازیم

و تمامممممم .

۲۶ تیر ۹۲ ، ۰۱:۵۴

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

المپیاد کامپیوتر و برنامه‌نویسی

المپیاد کامپیوتر و برنامه‌نویسی

سوال های برنامه نویسی

جزوه های آموزشی

متفرقه

راه حل مرحله 3

امتحان آزمایشی

زنگ حل مساله

زنگ تفریح

زنگ امتحان

روش

راه حل های سوالات برنامه نویسی

زنگ حل مساله

المپیاد کامپیوتر

هفته اول

زنگ حل مساله

سوال تئوری

نظرات (۲۱)

ارسال نظر