حل سوالات تشريحي مرحله دوم بيستمين المپياد كامپيوتر
C
پاسخ : حل سوالات تشريحي مرحله دوم بيستمين المپياد كامپيوتر
سوال استخدام (س 1 - دوره 20) رو راهنمایی کنید!
دانلود سوالای مرحله دو بیستمین دوره
سوال استخدام (س 1 - دوره 20) رو راهنمایی کنید!
دانلود سوالای مرحله دو بیستمین دوره
پاسخ : حل سوالات تشريحي مرحله دوم بيستمين المپياد كامپيوتر
سلام !
اگه میشه بیایید تا قبل مرحله 2 جواب سوالات این دوره رو با هم بنویسیم و حل کنیم :
خوب جواب سوال اول :
اول همه ی کارمندها رو میریزیم تو شرکت a ! اگه کسی ناراضی نبود که حله در غیر این صورت هر کسی که ناراضی بود رو میندازیم تو کارخونه ی b . ثابت میکنیم اگه کسی به کارخونه ی b بره دیگه تمایل نداره به کارخونه ی a برگرده و اینم واضحه چون اگه آخرین نفری رو که از کارخونه ی a به b بردیم رو در نظر بگیریم حتما ناراضی بوده بنابراین هیچ کس دیگه تمایل نداره که به کارخونه ی a برگرده زیرا در این صورت وضعیت آخرین نفر منتقل شده رو پیدا میکنه و دوباره به b برمی گرده ...
حالا یکی جواب سوال بعد رو بذاره ( یا هر کدوم از 4 سوال باقیمانده !!!!!!) :3: :35: :1:
سلام !
اگه میشه بیایید تا قبل مرحله 2 جواب سوالات این دوره رو با هم بنویسیم و حل کنیم :
خوب جواب سوال اول :
اول همه ی کارمندها رو میریزیم تو شرکت a ! اگه کسی ناراضی نبود که حله در غیر این صورت هر کسی که ناراضی بود رو میندازیم تو کارخونه ی b . ثابت میکنیم اگه کسی به کارخونه ی b بره دیگه تمایل نداره به کارخونه ی a برگرده و اینم واضحه چون اگه آخرین نفری رو که از کارخونه ی a به b بردیم رو در نظر بگیریم حتما ناراضی بوده بنابراین هیچ کس دیگه تمایل نداره که به کارخونه ی a برگرده زیرا در این صورت وضعیت آخرین نفر منتقل شده رو پیدا میکنه و دوباره به b برمی گرده ...
حالا یکی جواب سوال بعد رو بذاره ( یا هر کدوم از 4 سوال باقیمانده !!!!!!) :3: :35: :1:
C
پاسخ : حل سوالات تشريحي مرحله دوم بيستمين المپياد كامپيوتر
این جوابارو شااززز پارسال گذاشته بود:
تستی (روز اول):
سوال مربع و ۱۳۸۹ پارهخط میشه ۴۱۶۸
سوال ۲۰۱۰ عدد کمتر از ۲ به توان ۱۳۸۹ میشه ۱۳۹۹
سوال ۲۰ سکه ی طلا میشه ۱۰
سوال مکعب ۳*۳*۳ میشه ۶
سوال اشباع شده میشه 42
سوال سکه ها و پرتاب میشه ۱/۸
سوال مربع ۳*۳ میشه ۹ تا
سوال پست خونه میشه ۳۶ تا .
سوال n سکه میشه ۱۳۹۱
سوال ۳ کلید میشه k =3
سوال مرتب کردن سکه میشه ۵ تا
سوال دزد و تابلو ها میشه p(i)=max(vi+p(i-2),p(i-1)) in
سوال دانشجو و استاد میشه ۶
سوال راننده و جا ی پارک میشه ۱،۳،۲۹۹
سوال الگریتم s و b میشه ۷
سوال لیگ فوتبال میشه ۹
سوال طرح سوال میشه ۱۶۸
سوال الگوریتم رو a1 a2 a3 a4 میشه ۲۶
سوال مقدار کمینه s میشه ۳۵
سوال ۶ لامپ میشه ۲۹
تشریحی (روز دوم):
سوال ۱:
حقوق هر فرد را در وضعیتی که iنفر در شرکت اول بروند Pi و در وضعیتی که به شرکت دوم بروند Fi می نامیم... برهان خلف می زنیم... فرض کنیم وضعیت جواب نداریم
اگر nنفر به شرکت اول بروند، F1 > Pn است، (وگرنه وضعیت جواب بود)، *حالا اگر n-1 نفر به شرکت اول بروند Pn-1 < F2،*اگر n-2 نفر بروند Pn-2 < F3 و ... و اگر یک نفر برود P0 < Fn است که نا مساوی آخر
تناقض است. ***پس این بین یکی از نامساوی ها غلط بوده و حالت جواب بوده.
//=================================================
سوال ۲:
گراف جایگشت را می کشیم،*طوری که از i به πi یالی جهت دار می کشیم. گراف افرازی از چند دور است. در هر عمل طول هر دور نصف می شود، (چرا ؟) پس از k مرحله همه دور ها طولشان یک می شود.
ب) جایگشت 2, 3, 4, ..., n-1, n, 1 را در نظر بگیرید و پس از هر مرحله جای یک را بررسی کنید...
//==================================================
سوال ۳:
الف) درخت را از یک راس آویزان می کنیم،*حالا پایین ترین یال خراب (یالی که عوارض دو سرش یکسان شده اند) را در نظر بگیرید (و آن را uv بنامید، طوری که u پدر v باشد.) یکی از بچه*های v مانند w را انتخاب می*کنیم. عوارض یال vw را عوض می*کنیم. با این حساب uv دیگر خراب نیست. از طرفی ممکن است چند یال مانند vx یا wy خراب شده باشند. (که همگی پایین*تر از uv هستند.) ، و ... استقرا
پایه*ی استقرا: برگ. چون عوارض صفر نداریم، ...
ب) *ها شهرها هستند. عوارض جاده*ها درون پرانتز نوشته شده است.
*-(a,b)-*-(0,1)-*-(a,b)-*-(0,1)-*-(a,b)-*
بررسی کنید.
//==================================================
سوال ۴:
یک «وضعیت» را برای مسئله اینگونه تعریف می*کنیم:
«جاده*ی خروجی هر میدان کدام است؟ و ما کجا هستیم؟»
واضح است که تعداد حالات متناهی است. پس اگر از وضعیت ابتدایی شروع کنیم، بعد از طی چند مرحله به یک وضعیت تکراری برمی*گردیم. دور حاصل از وضعیت*ها (در گراف وضعیت) را در نظر می*گیریم. ادعا می*کنیم با پیمودن این دور، از همه*ی شهرها گذشته*ایم.
برهان خلف: شهری را در نظر بگیرید که در گراف وضعیت بازدید شده باشد و دارای حداقل یک همسایه*ی بازدید*نشده باشد. (آن را v بنامید) این دور را d_v (تعداد همسایه*های v) بار طی می*کنیم. حتما یک بار پلیس جاده*ی منتهی به شهر بازدید نشده را باز می*کند. تناقض...
//==================================================
سوال ۵:
توضیح بیشتر در مورد الگوریتم داده شده:
در ابتدا n دسته*ی ۱ عضوی داریم. هر بار، دو دسته*ی دلخواه را انتخاب می*کنیم، و همه*ی اعضای دسته*ی کوچکتر را در دسته بزرگ می*ریزیم و به اندازه*ی تعداد اعضای دسته*ی کوچک پول خرج می*کنیم (به b اضافه می*کنیم)
الف) در هر مرحله، اگر x دسته داشته باشیم، به x/2 تا دسته ۲تایی تقسیم می*کنیم. و دو به دو با هم تلفیق می*کنیم.
ب) هر عدد حداکثر در k عملیات جابه*جایی شرکت داشته. (چرا؟) پس در کل k * 2^k تا عمل انجام شده.
(برای اطلاعات بیشتر در مورد کاربرد این الگوریتم، در مورد داده*ساختار DisjointSet تحقیق کنید. منابع: ویکی*پدیا، CLRS، Creative و JBL)
جوابی که قرمز کردم به نظرت غلط نیست؟ من فکر میکنم 1/4 بشه!
سوالشم اینه:
علی یک سکه را آنقدر پرتاب میکند تا نتیجه ی دو پرتاب متوالی، مثل هم بیاید (هر دو رو یا هر دو پشت). چقدر احتمال دارد که علی بیش از 4 سکه را پرتاب کند؟ 1/4 یا 1/8 یا ...
کلا من با کارای علی مشکل دارم! مثل مرحله یک امسال!
این جوابارو شااززز پارسال گذاشته بود:
تستی (روز اول):
سوال مربع و ۱۳۸۹ پارهخط میشه ۴۱۶۸
سوال ۲۰۱۰ عدد کمتر از ۲ به توان ۱۳۸۹ میشه ۱۳۹۹
سوال ۲۰ سکه ی طلا میشه ۱۰
سوال مکعب ۳*۳*۳ میشه ۶
سوال اشباع شده میشه 42
سوال سکه ها و پرتاب میشه ۱/۸
سوال مربع ۳*۳ میشه ۹ تا
سوال پست خونه میشه ۳۶ تا .
سوال n سکه میشه ۱۳۹۱
سوال ۳ کلید میشه k =3
سوال مرتب کردن سکه میشه ۵ تا
سوال دزد و تابلو ها میشه p(i)=max(vi+p(i-2),p(i-1)) in
سوال دانشجو و استاد میشه ۶
سوال راننده و جا ی پارک میشه ۱،۳،۲۹۹
سوال الگریتم s و b میشه ۷
سوال لیگ فوتبال میشه ۹
سوال طرح سوال میشه ۱۶۸
سوال الگوریتم رو a1 a2 a3 a4 میشه ۲۶
سوال مقدار کمینه s میشه ۳۵
سوال ۶ لامپ میشه ۲۹
تشریحی (روز دوم):
سوال ۱:
حقوق هر فرد را در وضعیتی که iنفر در شرکت اول بروند Pi و در وضعیتی که به شرکت دوم بروند Fi می نامیم... برهان خلف می زنیم... فرض کنیم وضعیت جواب نداریم
اگر nنفر به شرکت اول بروند، F1 > Pn است، (وگرنه وضعیت جواب بود)، *حالا اگر n-1 نفر به شرکت اول بروند Pn-1 < F2،*اگر n-2 نفر بروند Pn-2 < F3 و ... و اگر یک نفر برود P0 < Fn است که نا مساوی آخر
تناقض است. ***پس این بین یکی از نامساوی ها غلط بوده و حالت جواب بوده.
//=================================================
سوال ۲:
گراف جایگشت را می کشیم،*طوری که از i به πi یالی جهت دار می کشیم. گراف افرازی از چند دور است. در هر عمل طول هر دور نصف می شود، (چرا ؟) پس از k مرحله همه دور ها طولشان یک می شود.
ب) جایگشت 2, 3, 4, ..., n-1, n, 1 را در نظر بگیرید و پس از هر مرحله جای یک را بررسی کنید...
//==================================================
سوال ۳:
الف) درخت را از یک راس آویزان می کنیم،*حالا پایین ترین یال خراب (یالی که عوارض دو سرش یکسان شده اند) را در نظر بگیرید (و آن را uv بنامید، طوری که u پدر v باشد.) یکی از بچه*های v مانند w را انتخاب می*کنیم. عوارض یال vw را عوض می*کنیم. با این حساب uv دیگر خراب نیست. از طرفی ممکن است چند یال مانند vx یا wy خراب شده باشند. (که همگی پایین*تر از uv هستند.) ، و ... استقرا
پایه*ی استقرا: برگ. چون عوارض صفر نداریم، ...
ب) *ها شهرها هستند. عوارض جاده*ها درون پرانتز نوشته شده است.
*-(a,b)-*-(0,1)-*-(a,b)-*-(0,1)-*-(a,b)-*
بررسی کنید.
//==================================================
سوال ۴:
یک «وضعیت» را برای مسئله اینگونه تعریف می*کنیم:
«جاده*ی خروجی هر میدان کدام است؟ و ما کجا هستیم؟»
واضح است که تعداد حالات متناهی است. پس اگر از وضعیت ابتدایی شروع کنیم، بعد از طی چند مرحله به یک وضعیت تکراری برمی*گردیم. دور حاصل از وضعیت*ها (در گراف وضعیت) را در نظر می*گیریم. ادعا می*کنیم با پیمودن این دور، از همه*ی شهرها گذشته*ایم.
برهان خلف: شهری را در نظر بگیرید که در گراف وضعیت بازدید شده باشد و دارای حداقل یک همسایه*ی بازدید*نشده باشد. (آن را v بنامید) این دور را d_v (تعداد همسایه*های v) بار طی می*کنیم. حتما یک بار پلیس جاده*ی منتهی به شهر بازدید نشده را باز می*کند. تناقض...
//==================================================
سوال ۵:
توضیح بیشتر در مورد الگوریتم داده شده:
در ابتدا n دسته*ی ۱ عضوی داریم. هر بار، دو دسته*ی دلخواه را انتخاب می*کنیم، و همه*ی اعضای دسته*ی کوچکتر را در دسته بزرگ می*ریزیم و به اندازه*ی تعداد اعضای دسته*ی کوچک پول خرج می*کنیم (به b اضافه می*کنیم)
الف) در هر مرحله، اگر x دسته داشته باشیم، به x/2 تا دسته ۲تایی تقسیم می*کنیم. و دو به دو با هم تلفیق می*کنیم.
ب) هر عدد حداکثر در k عملیات جابه*جایی شرکت داشته. (چرا؟) پس در کل k * 2^k تا عمل انجام شده.
(برای اطلاعات بیشتر در مورد کاربرد این الگوریتم، در مورد داده*ساختار DisjointSet تحقیق کنید. منابع: ویکی*پدیا، CLRS، Creative و JBL)
جوابی که قرمز کردم به نظرت غلط نیست؟ من فکر میکنم 1/4 بشه!
سوالشم اینه:
علی یک سکه را آنقدر پرتاب میکند تا نتیجه ی دو پرتاب متوالی، مثل هم بیاید (هر دو رو یا هر دو پشت). چقدر احتمال دارد که علی بیش از 4 سکه را پرتاب کند؟ 1/4 یا 1/8 یا ...
کلا من با کارای علی مشکل دارم! مثل مرحله یک امسال!
آخرین ویرایش توسط مدیر
C
پاسخ : حل سوالات تشريحي مرحله دوم بيستمين المپياد كامپيوتر
میشه حالتاتون رو بگید؟
0.oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
1.tt
2.thh
3.thtt
4.thth++++++++++++
5.hh
6.htt
7.hthh
8.htht+++++++++++++++
0.000000000000000000000000000000000000000000000000000000000000000000000000000000
میشه حالتاتون رو بگید؟
0.oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
1.tt
2.thh
3.thtt
4.thth++++++++++++
5.hh
6.htt
7.hthh
8.htht+++++++++++++++
0.000000000000000000000000000000000000000000000000000000000000000000000000000000
میشه دو تا از هشت تا که میشه 1/4.
پاسخ : حل سوالات تشريحي مرحله دوم بيستمين المپياد كامپيوتر
خوب از متمم استفاده میکنیم .
احتمال مطلوب = احتمال نامطلوب - 1
خوب 3 حالات در نظر میگیریم :
1) با انداختن دقیقا 2 سکه به پایان برسد ==> 2 حالت ==> احتمال =
2) با انداختن دقیقا 3 سکه به پایان برسد ==> 2 حالت ==> احتمال =
3) 2) با انداختن دقیقا 4 سکه به پایان برسد ==> 2 حالت ==> احتمال =
بنابراین احتمال اینکه بیشتر از 4 سکه بندازه برابر است با :
=\frac{1}{8})
خوب از متمم استفاده میکنیم .
احتمال مطلوب = احتمال نامطلوب - 1
خوب 3 حالات در نظر میگیریم :
1) با انداختن دقیقا 2 سکه به پایان برسد ==> 2 حالت ==> احتمال =
2) با انداختن دقیقا 3 سکه به پایان برسد ==> 2 حالت ==> احتمال =
3) 2) با انداختن دقیقا 4 سکه به پایان برسد ==> 2 حالت ==> احتمال =
بنابراین احتمال اینکه بیشتر از 4 سکه بندازه برابر است با :