المپیاد کامپیوتر مرحله 2 (بخش تشریحی)

[saadatfar]

سلام دوستان،
تشریحی را چه کرید!
من که نمرم بین 40 (بد بینانه) تا 60 (خوش بینانه) و احتمالا 50 (عاقلانه) میشه! اگه گند زدم یعنی بچه های پسر قم همه گند زدند!
شما چه کردید؟

 

[Electron]

منم همین حدود

خب بچه ها منو که دیگه در صحنه ی المپیاد نخواهید دید

به همه اونا که خوب دادن تبریک

منم که با 50 عمرا قبول شم

خیلی ایم مدت خوش گذشت

همیشه موفق باشید

 

[mamadosein]

سلام
جواب سوالا رو کسی نیست بده که ببینیم چیکار کردیم ؟
منم همون حدودای 50 تا 70 میشم،البته جوابا رو بفهمیم چیه دقیقتر میشه گفت
کف قبولی چند امتیازه ؟!
شما اون سوال شهر عجیب رو چطوری حل کردید ؟

 

[Olympiad]

وايسيد آقاي گوهرشادي بياد..... جواب سوال رو ميگه..... (من كه اول هستم نميذاشتن امتحان بديم

)
اگه كسي براش زحمت نيست سوالا رو اسكن كنه تا بهره ببريم..
با تشكر

 

[mamadosein]

بابا دم شما گرم
اول هستیو این همه اطلاعات داری کارت درسته ها !!!

ما که تا دوم اصلا تو کف المپیاد نبودیم :

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

 

[abdi]

من به طرز اسف‌باري گند زدم. فقط يه سوالو حل كردم

 

[Olympiad]

بابا دم شما گرم
اول هستیو این همه اطلاعات داری کارت درسته ها !!!

ما که تا دوم اصلا تو کف المپیاد نبودیم :

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

واقعا دستت درد نكنه!!

 

[spara]

من امروز 70 رو میگیرم اما دیروز 6 تا حل کردم(دیروز سر جلسه یه اتفاقی برام افتاد)
بگذریم
امید به قبولی داشته باشم؟

 

[mamadosein]

اینم از سوالای مرحله 2 المپیاد کامپیوتر بخش تشریحی
دانلود
ببخشید دیگه ، آخه سرعت اینترنتم پایینه مجبور شدم زیپش کنم

 

[shoki]

سوال 1
برهان خلف
سوال 2
الف ) در هر مرحله تعداد نابجایی ها ( یعنی حالتی که \pi(i) به غیر از i باشه ) نصف می شه
ب) با ساختار استقرایی
سوال 3
ریشه یابی درخت ، برای ب مثال با اعداد پیشنهادی (0،k )
سوال 4
خیییییییییلللللللییییییی تابلوه ( چون گراف همبند داریم)
سوال 5
این طوریه
1,2
3,4
5,6
7,8
9,10
11,12
13,14
15,16
2,4
6,8
10,12
14,16
4,8
12,16
8,16
قست ب رو نمی دونم

 

[saadatfar]

به نظر من امسال سوالاش سخت تر از پارسال بود. در حقیقت پارسال سوالاش آبکیبود اما امسال بد نبود.
از طرفی تعداد قبولی ها دوبل شده.
من که سوال 1 و 2 رو کامل حل کردم. 3 و 5 هم قسمت اولشون را حل کردم.
سوال 4 هم فکر نکنم اینطور که شما می گید به این راحتی بشه گفت.

 

[saadatfar]

من امروز 70 رو میگیرم اما دیروز 6 تا حل کردم(دیروز سر جلسه یه اتفاقی برام افتاد)
بگذریم
امید به قبولی داشته باشم؟

شما هم امیدوارم قبول بشید! به نظر من اگه بتونید 200 نفر را رد کنید و واقعا 70 رو بگیرید قبولید.

 

[shoki]

با این حال من فقط تونستم سوالای 1،2،4 رو کامل حل کنم . سوال 5 قسمت الف رو حل کردم . سوال 4 ...

.... اول فکر کردم درسته راه حلم بعدش فهمیدم چه سوتیی دادم ... ولی چون ایده ی اصلی رو زدم فکر کنم در کل 70 شم ... از اونجایی که تعداد افرادی که با ایده ی ریشه یابی آشنا هستند کم اند تعداد افرادی که سوال 3 رو کامل حل کردند کم خواهد بود ( البته به نظر می یاد این طوری باشه ) ... در مورد قسمت ب سوال 5 چون اکثر بچه هامون روش نتونستند اصلا فکر کنند نظری ندارم ...
راستی قسمت ب سوال 2 هم من اینطوری حلش کردم البته مثل این که راه حله دیگری هم داره )
ابتدا تعریف می کنیم < a[SUB]1[/SUB]=<2,1
بدیهیست که در شرط صدق می کند ... حالا

رو دنباله ی برعکس

تعریف کنید . حالا تعریف کنید :

[center:ff44ec9de6]

با یک بار انجام دادن این الگوریتم به دست می یاد :

مثلا به دست می یاد :< a[SUB]2[/SUB]=<4,3,1,2

​

[/center:ff44ec9de6]​

​

 

[shoki]

سوال 4 کجاش تابلو نیست ؟؟

 

[saadatfar]

سوال 4 کجاش تابلو نیست ؟؟

شما باید بگید کجاش تابلو هست! یعنی کامل بگید راه حلتون چی بود تا من بگم دیدی تبلو نبود!

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

 

[mathematician]

من سوال یک رو از برهان خلف حل نکردم! اومدم حالتی که وجود داره رو پیدا کردم. پس شاید اشتباه باشه!
سوال 3 الف رو هم با استقرا حل کردم!
فقط همین دوتا متفاوت بودن.
ایرادی نداره! فردا تلاش می کنم!!! :-"

 

[shoki]

در مورد کف نظر خاصی ندارم (بعضی ها می گن 60 هستش) ...
راه حل من هم اینه :
اگه v_1 راسی باشه که ازش شروع می کنه اتومبیل مسیر یکتایی رو طی می کنه ... حالا فرض کنید در طول این مسیر نتونسته باشه یک سری از رئوس رو بازدید کنه.
مثلا v_k,...,v_n رو نتونسته بازدید کنه. در اون صورت همواره باید یک مسیر رو هی بره و هی بیاد و رئوس{v_1,...,v_{k-1 رو تونسته بازدید کنه. اما چون یالی بین مجموعه رئوس
v_k,...,v_n و {v_1,...,v_{k-1 وجود داره مثلا v_iv_m در اون صورت زمانی می رسه که اتومبیل از v_i می گذره و در اون لحظه یال v_iv_m بازه .
پس مسئله حله

 

[shoki]

این هم از راه حلم برای سوال 1 : فرض کنید که اعدادمون

و

باشند در اون صورت باید داشته باشیم :

و

و اگر نه مسئله حله . پس اگر داشته باشیم

اون وقت چون y_1>x_n پس باز هم مسئله حله . پس باید داشته باشیم :

و به همین ترتیب

تا به این که برسیم به

و تناقض حاصل می شود .

 

[shoki]

به هر حال من که امیدی ندارم چون که تستی ها رو (همون طور که همه می دونن) گند زدم ...

... حالا ببنینیم فردا چی میشه ...

 

[shoki]

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

به خاطر همین

...