آرشیو - گفت و گو ها پیرمون مراحل مختلف ، دوران مختلف

[volta22]

پاسخ : بیست و چهارمین دوره المپیاد کامپیوتر [مرحله اول]

دوستان کف امسال چنده حدودا ؟
من حدودا 16 تا زم 8 تا مطمئنم درسته . بقیه رو هم شک دارم ! قبولم ؟ برم برا مرحله 2 ؟

 

[rezaezio]

پاسخ : بیست و چهارمین دوره المپیاد کامپیوتر [مرحله اول]

دوستان کف امسال چنده حدودا ؟
من حدودا 16 تا زم 8 تا مطمئنم درسته . بقیه رو هم شک دارم ! قبولم ؟ برم برا مرحله 2 ؟

باو باشگاه پاسخنامه داده ! برو صحیح کن، نمره دقیقت رو بفهم ! کف حدود 7 عه !

 

[volta22]

پاسخ : بیست و چهارمین دوره المپیاد کامپیوتر [مرحله اول]

باو باشگاه پاسخنامه داده ! برو صحیح کن، نمره دقیقت رو بفهم ! کف حدود 7 عه !

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

 

[ali 56]

پاسخ : بیست و چهارمین دوره المپیاد کامپیوتر [مرحله اول]

من از 29 سوال (باتوجه به اینکه سوال 30 حذف شده ) 9 درست و 6 غلط زدم یعنی حدود نمره 7.5
به نظرتون می تونم قبول شم؟

 

[rezaezio]

پاسخ : بیست و چهارمین دوره المپیاد کامپیوتر [مرحله اول]

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

عجب !‌

من از 29 سوال (باتوجه به اینکه سوال 30 حذف شده ) 9 درست و 6 غلط زدم یعنی حدود نمره 7.5
به نظرتون می تونم قبول شم؟

شانس قبولی داری، ولی حتمی نیست !

 

[sajjad--senator]

پاسخ : بیست و چهارمین دوره المپیاد کامپیوتر [مرحله اول]

من از 29 سوال (باتوجه به اینکه سوال 30 حذف شده ) 9 درست و 6 غلط زدم یعنی حدود نمره 7.5
به نظرتون می تونم قبول شم؟

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

 

[مهدی]

پاسخ : سوالات مرحله 2 - تشریحی

بی زحمت این سوال ۱ روز دوم دوره ۴ رو یه مرحمتی کنید.

 

[rezaezio]

پاسخ : سوالات مرحله 2 - تشریحی

بی زحمت این سوال ۱ روز دوم دوره ۴ رو یه مرحمتی کنید.

وقتی دو نفر وارد رستوران میشن، به جز خودشون حداکثر چهارده نفر داخل رستوران هستند!
حالا فرض کن ایکس جفت داخل رستوران باشن، پس هفت منهای ایکس تا از خونه هایی که مشخص کرده خالی هستن ! به ازای هر خونه خالی (فکر بد نکن)، اگه یکی از دو سمتش خالی باشه حکم برقرار هست ! پس هر دو طرفش پره !
یه محاسبه بکنی، میبینی که حداقل چهارده نفر لازم داریم که خونه های مشخص شده و مجاور هاش رو پر کنیم ! پس خانه 22 و 23 خالی هستن !

پ.ن :‌ خلاصه نوشتم دیگه ... تو مرحله دو اینجوری ننویسید که نمره نمیدن

 

[rezaezio]

پاسخ : سوالات مرحله 2 - تشریحی

با استقرا راحت تر نبودی ؟

استقرا ابهت داره !

 

[مهدی]

پاسخ : سوالات مرحله 2 - تشریحی

خب استارتش با من بود .
حالا شما شوال بذارید.
از ته بریم سر
+رضا خیلی ذهنت ...

 

[rezaezio]

پاسخ : سوالات مرحله 2 - تشریحی

دِ استارتر
دوره بیست ؛ سوال سوم ! کلا اون دوره سوالای زیبایی داشته !

 

[miladaghajohari]

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

بازم سلام، اینها جوابهای من برای 4 سوال روز دوم است، امیدورام درست باشند، من فکر می کنم در مجموع 2 روز 170 نمره از 200 نمره بگیرم.
اکثر افراد میگن کف حدود 100 است، شماها نظری ندارید؟

جوابهای من:
به دلیل طولانی بودن جواب ها و کمبود حوصله برای تایپ ، آنها را آنقدر خلاصه کردم، که فقط کسانی که سوال ها را خوانده اند و روی آنها فکر کرده اند متوجه جواب می شوند، باید ببخشید.

سوال پنجم:تعداد رنگ آمیزی های مجاز برای یک سطر(بدون در نظر گرفتن بقیه ستون ها) 144 است.( با رابطه ی بازگشتی و فیبوناچی می توانید 144 را به دست آورید.). پس ما چون 10 سطر داریم حداکثر 144 به توان 10 حالت داریم، که اثبات می شود از 10 به توان 25 کمتر است.
حال فرض کنید، جدول را به صورت شطرنجی رنگ کرده ایم، 50 خانه سیاه به دست می آید که هیچ کدام ضلع مشترک با دیگری ندارد، حال در رنگ آمیزی جدید تمام سفیدهای صفحه ی شطرنجی را سفید و هر کدام از این 50 تا را به 2 حالت سیاه یا سفید می کنیم، پس حداقل 2 به توان 50 حالت داریم که بیشتر از 10 به توان 15 است.(زیرا 2 به توان 50 برابر است با 1024 به توان 5 و بشتر است از 1000 به توان 5، پس بیشتر است از 10 به توان 15)(البته من این قسمت را که باید اثبات می کردیم بیش از 10 به توان 15 است را هم با رابطه بازگشتی رفتم، ولی بعد از امتحان فهمیدم این راه کوتاه تر است)


سوال ششم:به جای 20 حرکت، حکم را برای 10 حرکت اثبات می کنیم( برای 8 حرکت هم اثبات می شود).
فرض خلف می کنیم که در 10 حرکت متوالی به سراغ 10 سطل با بیش از 10 توپ رفته ایم، اثبات می شود که این سطل ها متمایز اند، همچنین سطل اول 10، سطل دوم 9 و... سطل نهم 2 و سطل دهم باید 1 توپ داشته باشد، پس در مجموع حداقل 55 توپ متمایز داشتیم، و تناقض ایجاد می شود.

سوال هفتم:استقرا روی تعداد کلید ها می زنیم، به ازای یک کلید که درست است،( چون همه به همان یک کلید وصل اند)فرض کنید به ازای n کلید درست باشد، به ازای n+1 اثبات می کنیم، یک کلید را مزنیم، تعدادی روشن میشود، بقیه که خاموش اند به این کلید وصل نیستند، پس حداقل به یکی از n کلید دیگر وصل اند، طبق فرض می توان با استفاده از آن n کلید، بیش از نیمی از بقیه را روشن کرد، از بین چراغ هایی که به وسیله کلید اول روشن کردیم، اگر کمتر مساوی نصف تا خاموش شود که مسئله حل است، و اگر نه دوباره کلید اول را می زنیم، مسئله حل می شود.

سوال هشتم: استقرا روی n می زنیم، برای 1 که درست است،اگربرای n-1درست باشد، برای n حکم را اثبات می کنیم، به این صورت که اگر بین کارتهای مرتضی دو تا اختلاف کمتر مساوی از d داشت، با dپرسش می فهمیم اختلاف یکی از این دوتا با کیان بیشتر مساوی دیگری است، پس n-1 کارت پیدا می شود که طبق فرض حل می شود، ولی اگر هیچ دوتایی اختلاف کمتر مساوی d نداشتند، حکم استقرا را قوی کرده و تبدیل به حکم زیر می کنیم، و مسئله حل خواهد شد:
اگر در بین n کارت اگر بدانیم یکی از آنها x<d-1 اختلاف با کیان دارد، می توانیم کارت دارای کمتر از d اختلاف را با کمتر از nd-x پرسش بیابیم.

اثباتتون رو برای سوال 2 برای 8 تا میگین؟

 

[مهدی]

پاسخ : سوالات مرحله 2 - تشریحی

این جواب بهینه (تر) هستش

درخت را از یک راس آویزان می کنیم،‌حالا پایین ترین یال خراب (یالی که عوارض دو سرش یکسان شده ن ) رو در نظر بگیرید (و اون را uv بنامید، طوری که u پدر v باشه.) یکی از بچه‌های v مانند w رو انتخاب می‌کنیم. عوارض یال vw رو عوض می‌کنیم. با این حساب uv دیگر خراب نیستش. از طرفی ممکنه که چند یال مانند vx یا wy خراب شده باشن. (که همگی پایین‌تر از uv هستن.) ، و ... استقرا
پایه‌ی استقرا: برگ. چون عوارض صفر نداریم، ...
دقت کنید که روی ارتفاع درخت استقرا زدیم و در هر مرحله در دو زیردرخت که ارتفاعشون کمتر از درخت اصلی از فرض استقرا استفاده میکنیم

 

[Dark Eagle]

پاسخ : سوالات مرحله 2 - تشریحی

این طوری بنویسی نمره که نمیده هیچ, ببینتت فُشتم میده ...

از یه راس root کن درخت رو بعد رو ارتفاعش استقرا بزن ... واسه قسمت ب هم یه مسیر به طول 5 رو در نظر بگیرید که یال 2 و 4 اِش (p , 0) باشه

بقیه هر چی می خوان باشن واسش مطرح نیس ...

 

[miladaghajohari]

پاسخ : سوالات مرحله 2 - تشریحی

آقا یکی مردونگی کنه جواب دوره 18 سوال 5 علی کوچولو رو بزاره. مال روز دومه.

 

[mhjh]

پاسخ : سوالات مرحله 2 - تستی

آقا اگر کسی سوالهای 6 و 7 و 12و 15 و 18 دوره ی 21 (تستی ) رو جواب تشریحیش رو بذاره خیلی ممنون میشم.

 

[مهدی]

پاسخ : سوالات مرحله 2 - تستی

برای سوال۶ دوره ۲۱ روز اول:
همه اعداد رو به مد ۳ بنویس
1-1-2-1-0-0-2-1-0-1-0-1-2-1-0
حالا برای هر i
S
رو مجموعه اعداد از اول دنباله تا اونجا بگیر.
مثلا S[1]=1
S[2]=2
S[3]=1
و...
حالا دنباله Sرو بنویس
1-2-1-2-2-2-1-2-2-0-0-1-0-1-1
به ازای هر دو عدد برابر از این دنباله داریم S-S[j]=0
پس A[j+1]+A[j+2]+...+A=3k
حالا باید تعداد اعداد برابر رو پیدا کنی که می‌شه انتخاب 2 از تعداد1 ها
+
انتخاب 2از تعداد 2 ها
+
انتخاب 2 از تعداد 0 ها
اما این کل حل نیستش،یه نکته ای در مورد 0 ها هستش که اون رو باید بهش دقت کنی و اونو خودت روش فکر کن ،اگر نفهمیدی بهم بگو

 

[mhjh]

پاسخ : سوالات مرحله 2 - تستی

فهمیدم .
با این چیزی که شما نوشتی ، میشه :
C(6,2)+C(6,2)+C(3,2)=33
ولی فکر کنم نکتش اینه که هر صفر در این دنباله خودش یه صفر روی کاغذ می سازه .
پس میشه 33+3=36
درست گفتم ؟؟؟

 

[مهدی]

پاسخ : سوالات مرحله 2 - تشریحی

فک کنم جوابش [2*(n-1)/d] باشه
مثالش هم ستاره هست یعنی یه راس رو مشخص می کنیم
بعد d/2 تا راس بر می داریم . یه مسیر d/2-یالی که ابتداش راس مشخص هست می سازیم ببعد اینکارو تا جاییکه ممکنه ادامه میدیم که تعداد پلیس ها همون مقدار بالا میشه
برای اثباتش هم درخت رو از یه برگ (میشه فرض کرد این برگ پلیسه) آویزون می کنیم .
حالا فاصله این راس تا اولین راس غیر برگ رو x فرض می کنیم .
حالا این راس (فرض کن راس v) به یه سری پلیس دیگه مسیر داره که مسیر هاش مجازن یالن.
اگر تو یکی از این مسیرا 2تا پلیسه باشه پس میشه فرض کرد فاصله ی بین 2 تا از اونا dتا یال هست .یکی از اونا که به راسه vدورتره رو حذف و کله مسیرش رو به vوصل می کنیم.
با اینکار تعداد پلیسها تغییر نمی کنه و میشه اون فاصله ی vتا اون راسی که جاشو تغییر دادیم تا کم کنیم
پس با این کار درختمون بهینه میشه
پس بهینه ترین حالت همون حالتی هست که مثال زدیم

 

[The Smith]

پاسخ : سوالات مرحله 2 - تشریحی

بچه ها دوره چهار ، سوال آخر ، روز دوم

سوالیه که ایدش پنج یا شش بار اومده توی مرحله دو. :)

حل بکنید و لذت ببرید و از این سوال.