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

زنگ حل مساله

پنجشنبه, ۲۷ تیر ۱۳۹۲، ۱۱:۰۱ ب.ظ

سلام به همگی

خوبین؟ خوشین؟

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

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

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

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

موفق باشید.

۰ ۹۲/۰۴/۲۷

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

سوال تشریحی

سوال تئوری

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

زنگ حل مساله

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

doost

az ideaye soale 1 khosham omad. hala raham ro migam har ki khas bekhone. man ke kheyli hal kardam:

اول از همه ی وزنه ها یکی می زاریم. مثلا ترازو وزن رو بهمون میگه x. خب حالا ایندفعه از وزنه ی ۱ فقط یکی بعد از وزنه ۲ xتا بعد از وزنه ۳ x^2تا و ... می زاریم. خب حالا عددی که بهمون میده رو در مبنای x می نویسیم. عدد iام از راست در مبنای x میشه وزن وزنه iام :دی

khosh bashin

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

mamolan to hale soalaE mese soale 3 moshkel daram vali khoda ro shokr in soal rahat hal shod.
hale soale 3:

برهان خلف می زنم. فرض می کنم تو این گراف هیچ دو راسی نیستند که دارای زوج همسایه مشترک باشند. خب حالا یه راس مثل v رو در نظر می گیرم. چون هر دو راس حداقل ۱ همسایه مشترک دارن پس قطر گراف حداکثر ۲ هست. از طرفی درجه هر راس زوج هست پس هیچ کس نمی تونه با همه دوست باشه پس قطر گراف دقیقا ۲ هست. حالا تمام همسایه های راس v رو تو مجموعه ی A و بقیه راس ها به جز v رو تو مجموعه B میذارم. حالا چون |A| زوج هست و کلا 2n تا آدم داریم پس |B| فرد هست. حالا x رو می گیرم مجموع درجات رئوس داخل A(البته یال های خارج A هم حساب می شن) بنابر فرض مسئله داریم x زوج است. حالا یه طور دیگه زوجیت x رو حساب می کنیم. برای هر راس تو B بنا بر فرض برهان خلف تعداد فرد یال به مجموعه A وارد می شه. پس تا این جا که x فرده. حالا از v هم زوج یال به A میاد(به اندازه تعداد اعزای A که زوج است) به ازای هر یال داخل A هم که x دقیقا ۲ تا اضافه می شه. پس در کل x میشه فرد که بنابر چیزی که قبلا گفتم نمیشه. پس فرض برهان خلف غلطه و حکم سوال ثابت شد :دی

khosh bashin

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

hale soale 2 ro kheyli hal nadaram benevisam va alan ham khastam va hale fek kardan ro baghie soala ro nadaram. dar kol mamnon be khatere soala.

P.N. : hala ke daram negaeh mikonam mibinam bazi chiza ro to hale soale 3 lazem nabod asan begam. dige az dastam dar raft dige. khodeton bebakhshid :D

khosh bashin

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

سوال ۱ : بار اول وزن کردن جمع وزنه ها را (sum( را به دس میاریم ، بعد

دفهی بعد n ی رو در نظر میگیریم که بزرگتر مساوی sum باشه بعد از وزنه ی اول ۱ دونه از وزنهی دوم m تا ... وزنهی n ام m^n-1 تا رو قرار میدیم ، بعد عدد حاصل رو میبریم توی مبنای m حالا هر رقم این عدد متانظر با وزن یکی از انواع وزنه هاس (سوال توی تورنومنت شهر ها نبود (ضرایب چند جمله ای رو میخواس ) ؟؟؟؟ O.o (

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

2: فرض کنین غور باغه ها a و خرچنگا (یا هرچی که بودن ) b هستن ، واضحه مه بیشتر از ۲ تا a نباید کنار هم بشینن (چون در اون صورت حد اقل یکی هس که وسط ۲ تا a قرار میگیره )پس حد اقل ۱۳ تا دسه هستن که کنار هم میشینن (۱۲ تا نمیشه چون طبق لانه ۱ دسه هس که بیشتر از ۳ تا داره )

چون دور ۱ دایره هستن => ۱۳ تا دسه از b هم باید وجود داشته باشه که بین این ها بشینن که یکی از این ها در ان فقط ۱ b وجود داره (چون اگر در هر کدوم حداقل ۲ تا b باشه تعداد کل میشه حد اقل ۲۶ تا b که از ۲۵ بیشتره) در نتیجه اون دستهی یکی دو ترفش ۲ تا a هس => پس حتما موجودی وجود داره که ۲ طرفش غورباغه باشه .

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

3: با برهان خلف ثابت میکنیم :

یعنی هر ۲ نفر فرد دوست مشترک دارن ،

لم۱ : اینجا کسی نمیتونه باشه که هیچ دوستی مداشته باشه ( راس تنها نداریم ) چون در ان صورت با بقیه ۰ دوست مشترک داره => با فرز متناقض هست .

حالا یک راس را به دلخواه در نظر میگیریم ، (راس v ) این راس زوج تا همیایه داره که هر کدام غیر از v فرد همسایه ی دیگر داره ،یعنی راس v از طریق هر کدام از همسایه هاش ، با فرد راس دیگر همسایه ی مشترک داره ، چون v زوج تا دوست یا راس مجاور داره => در مجموع زوج راس دیگر هستند که v با ان ها همسایه ی مشترک داره ، ممکن است بعضی راس ها تکراری شمرده شده باشند ولی چون طبق فرض خلف هر دو راس فرد همسایه ی مشترک دارن => هر راس زوج بار اضافه شمرده شده پس مقدار راس هایی که v با ان ها همسایه ی مشترک داره زوج باقی میمونه .

از ان جایی که ۲n نفر وجود دارن => غیر از v تعداد ۲n-1 نفر دیگر وجود دارن که v با زوج تاشون دوست مشترک داره => یکی هس که باش دوس مشترک نداره که یعنی ۰ تا دوست مشترک => فرض خلف غلط است

۲۸ تیر ۹۲ ، ۱۵:۰۳

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

سلام
ازینکه تعداد سوال هارو زیاد کردین واقعا ممنون خیلییییی کار خوبیه و واقعا دستون درد نکنه ، اجرتون با خدا
منتظر سوال های برنامه نویسی هم هستیم با تشکر

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

kimia

سوال 2 )

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

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

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

++ واقعا مرسی !

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

سوال 3 )

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

یک راس با درجه دلتا رو در نظر میگیریم ، اگر مجموعه دوستاشو A بگیم و مجموعه اونایی رو که دوستش نیستن B بنامیم .

تعداد اعضای مجموعه B عددی فرد است ، زیرا در کل 2*N راس داریم و راس با درجه دلتا + همسایه هایش تعداد فردی راس هستند و بنابراین رئوس باقی مانده ، تعداد فردی هستند .

حالا تعداد یال های بین مجموعه A , B را به دو صورت میشماریم .

از یک طرف هر کدوم از مجموعه B تعداد فردی همسایه مشترک با راس درجه دلتا دارند ، و چون خودشون هم فرد هستند ، تعداد فرد تا یال به مجموعه A دارند .

از طرفی دیگه : هر کدوم از راس های مجموعه A با فرد تا از مجموعه A دوست است و با راس درجه دلتا هم که دوسته ، بنابراین با تعداد زوجی از مجموعه B دوست هست که یعنی تعداد یال هایی که به B میره ، زوج هست که به تناقض میرسیم .

۲۸ تیر ۹۲ ، ۱۷:۵۴

من با ۱۰۰ تا میتونم برای سوال ۴ ، اول یکی در میان ستون های ۲،۴...۱۰۰ را تغییر میدیم بعد سطر های ۱،۳...۹۹ را تغییر میدیم ، ول اثبات کمینگی را بلد میسم

من خنگم :'(

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

با تشکر از سوال ها ، من یه پیشنهاد دارم از سوال هایی مانند سوال ۴ که باید کمینه بودن یه چیز را ثابت کرد بیشتر بدین ، و ایده های اثبات کمینگی رو هم لطفا بگین ، من بقیه را نمیدونم ولی خودم توی سوالایی مثل ۴ خیلی مشکل دارم ، با تشکر :)

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

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

ببخشید میشه یه سیستم بزارید که هر پستی که میزارید به صورت ایمبل به کاربرا برسه من تازه الان فهمیدم که سوال گذاشتین

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

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

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

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

متفرقه

راه حل مرحله 3

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

زنگ حل مساله

زنگ تفریح

زنگ امتحان

روش

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

زنگ حل مساله

سوال تشریحی

سوال تئوری

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

زنگ حل مساله

نظرات (۱۶)

ارسال نظر