بررسی مرحله دوم بیست و یکمین المپیاد کامپیوتر
C
پاسخ : بررسی مرحله دوم بیست و یکمین المپیاد کامپیوتر
من تو کف ای شااززز م جوابارو گذاشته:
دانلود جواب ها
من تو کف ای شااززز م جوابارو گذاشته:
دانلود جواب ها
پاسخ : بررسی مرحله دوم بیست و یکمین المپیاد کامپیوتر
این پاسخنامه ی روز اوله که توسط شااززز و olyampiads.blogfa.com و ... اعلام شده است:
1. الف
2. ه
3. ه
4. د
5. ج
6. ج
7. د
8. د
9. الف
10. ج
11. د
12. الف
13. ب
14. ب
15. ه
16. ب
17. ب
18. د
این پاسخنامه به احتمال 99.99% درسته
در ضمن تو olyampiads.blogfa.com نوشته بود کف حدود 32 از 84 است یعنی 38.1%
این پاسخنامه ی روز اوله که توسط شااززز و olyampiads.blogfa.com و ... اعلام شده است:
1. الف
2. ه
3. ه
4. د
5. ج
6. ج
7. د
8. د
9. الف
10. ج
11. د
12. الف
13. ب
14. ب
15. ه
16. ب
17. ب
18. د
این پاسخنامه به احتمال 99.99% درسته
در ضمن تو olyampiads.blogfa.com نوشته بود کف حدود 32 از 84 است یعنی 38.1%
پاسخ : بررسی مرحله دوم بیست و یکمین المپیاد کامپیوتر
اینم پاسخنامه ی روز دوم المپیاد که من شرکت نکردم
برگرفته از شااززز)
اینم پاسخنامه ی روز دوم المپیاد که من شرکت نکردم
برگرفته از شااززز)سوال تبديل دو دويي
بيتي مي توان به حالت هاي ديگر آن رفت
n با استفاده از استقرا ثابت مي کنيم که از هر حالتي از يک رشته
پايه استقرا
بديهتا با يک بار فشار دادن دکمه اول بيت اول را مي توان از ۱ به ۰ و از ۰ به ۱ تغيير داد
. n = به ازاي ۱
فرض استقرا
بيت را مي توان با دکمه هاي اول و دوم توليد کرد، حال مي خواهيم رشته هاي به
k فرض مي کنيم تمام رشته هاي به طول
بيت اول را يکي کرد و دو k هر دو رشته يکي بود که طبق فرض استقرا مي توان k+ را بسازيم. در صورتي که بيت ۱ k+ طول ۱
رشته را در کل يکي کرد.
بيت اول را يکي کرد و دو k هر دو رشته يکي بود که طبق فرض استقرا مي توان k+ را بسازيم. در صورتي که بيت ۱ k+ طول ۱
رشته را در کل يکي کرد.
بيت اول را تبديل مي کنيم به
k اختلاف داشته باشند، حال با استفاده از فرض استقرا k+ حال در صورتي که دو رشته در بيت ۱
تغيير مي کند تا دو رشته در k+ ام يک باشد و بقيه بيت ها صفر، سپس دکمه اول را فشار مي دهيم و بيت ۱ k رشته اي که بيت
بيت اول را يکي کرد. k يکي شوند، سپس طبق فرض استقرا مي توان k+ بيت ۱
تغيير مي کند تا دو رشته در k+ ام يک باشد و بقيه بيت ها صفر، سپس دکمه اول را فشار مي دهيم و بيت ۱ k رشته اي که بيت
بيت اول را يکي کرد. k يکي شوند، سپس طبق فرض استقرا مي توان k+ بيت ۱
سوال در هم ساز
الف
باشد، سپس از هر حالتي که به حالت ديگر برويم
( با اين n گرافي تشکيل مي دهيم که هر راس آن يکي از جايگشت هاي ۱ تا
آرايش خانه هاي علامت دار ) يک يال جهت دار قرار مي دهيم از مبدا به مقصد.
آرايش خانه هاي علامت دار ) يک يال جهت دار قرار مي دهيم از مبدا به مقصد.
در اين گراف از هر راس تنها يک يال خارج مي شود و يک يال به آن وارد مي شود
( بديهي است ) پس اين گراف اجتماعي از
دور ها هست، پس بعد از چند حرکت روي اين دور ها به حالت اوليه مي رسيم.
دور ها هست، پس بعد از چند حرکت روي اين دور ها به حالت اوليه مي رسيم.
ب
را به
i برود j قرار دارد به خانه i براي اين قسمت مسئله گراف جايگشت را رسم مي کنيم ( اگر با يک حرکت عددي که در خانه
وصل مي کنيم) اين گراف نيز بديهتا اجتماعي از دور ها است مانند استدلال قسمت الف پس هر عدد بعد از طي کردن تعدادي j
وصل مي کنيم) اين گراف نيز بديهتا اجتماعي از دور ها است مانند استدلال قسمت الف پس هر عدد بعد از طي کردن تعدادي j
مرحله
( به اندازه طول دوري در گراف جايگشت که در آن قرار دارد ) ، پس با طي کردن ک.م.م طول تمام دور ها به جايگشت
قبلي مي رسيم(چرا؟)، پس اگر گراف قسمت الف را در نظر بگيريم تعداد جايگشت هايي که با هم در يک دور قرار دارند به اندازه
همين ک.م.م است. اگر بخواهيم از تمام حالت ها به حالت مرتب شده برسيم بايد طول دوري که جايگشت ها در آن قرار دارند
باشد ( که تمام جايگشت ها در يک دور باشند ) n!
قبلي مي رسيم(چرا؟)، پس اگر گراف قسمت الف را در نظر بگيريم تعداد جايگشت هايي که با هم در يک دور قرار دارند به اندازه
همين ک.م.م است. اگر بخواهيم از تمام حالت ها به حالت مرتب شده برسيم بايد طول دوري که جايگشت ها در آن قرار دارند
باشد ( که تمام جايگشت ها در يک دور باشند ) n!
نيست حتما
. پس حتما نمي توان چنين ترتيبي رسم کرد. n! باشد n اما ک.م.م يک سري عدد که مجموعشان
سوال مرتب سازي
را با عنصر اول جا به جا مي کنيم، به کمک
i+ عنصر اول را نسبت به هم مي دانيم. عنصر ۱ i ترتيب i فرض مي کنيم در مرحله
عنصر اول مي فهميم. به اين ترتيب با ۹۹ جا به جايي i+ را در ۱ i+ تغيير وارونگي داده شده توسط دستگاه، جايگاه عنصر ۱
جايگاه هر صد عنصر را مي فهميم سپس با ۹۹ حرکت آنها را در محل خود قرار مي دهيم. در جمع ۱۹۸ حرکت انجام داده ايم.
عنصر اول مي فهميم. به اين ترتيب با ۹۹ جا به جايي i+ را در ۱ i+ تغيير وارونگي داده شده توسط دستگاه، جايگاه عنصر ۱
جايگاه هر صد عنصر را مي فهميم سپس با ۹۹ حرکت آنها را در محل خود قرار مي دهيم. در جمع ۱۹۸ حرکت انجام داده ايم.
سوال درخت ريشه دار
الف
عمق يک درخت
: طول طولاني ترين مسير از ريشه به رأس ها (طول مسير برابر تعداد يالهاي آن است)
۱۴ مرحله بعد مي توان همه يال ها را از بين برد
. به اين ترتيب ‐i ۱۴ باشد، در ‐i عمق يک درخت کمتر يا مساوي i اگر در مرحله
۱۴ بود، طولاني ترين مسير از ريشه به ‐i که در هر مرحله يا لهاي متصل به ريشه را حذف مي کنيم. اگر عمق درخت بيشتر از
۱۴ بود، طولاني ترين مسير از ريشه به ‐i که در هر مرحله يا لهاي متصل به ريشه را حذف مي کنيم. اگر عمق درخت بيشتر از
.
(۱۴‐i+ بچه ها را حذف م يکنيم (تعداد يال هاي حذف شده حد اقل ۱
۱۴ کمتر بود م يتوان در ١٤ مرحله همه يال ها را حذف کرد. چنين حالتي حتما پيش ‐i اگر در يک مرحله عمق همه درخت ها از
مي آيد!زيرا: اگر در هيچ يک از مراحل حالتي پيش نيايد بعد از ۱۴ مرحله،درهرمرحله با حذف طولاني ترين مسير از ريشه به
۱۴ يال و در کل حداقل ١١٩ يال حذف شده. تناقض! ‐i+ بچه ها حداقل ۱
۱۵ + ۱۴ + ۱۳ + ۱۲ + ۱۱ + ۱۰ + ۹ + ۸ + ۷ + ۶ + ۵ + ۴ + ۳ + ۲ = ۱۱۹ > ۱۰۰
۱۴ کمتر بود م يتوان در ١٤ مرحله همه يال ها را حذف کرد. چنين حالتي حتما پيش ‐i اگر در يک مرحله عمق همه درخت ها از
مي آيد!زيرا: اگر در هيچ يک از مراحل حالتي پيش نيايد بعد از ۱۴ مرحله،درهرمرحله با حذف طولاني ترين مسير از ريشه به
۱۴ يال و در کل حداقل ١١٩ يال حذف شده. تناقض! ‐i+ بچه ها حداقل ۱
۱۵ + ۱۴ + ۱۳ + ۱۲ + ۱۱ + ۱۰ + ۹ + ۸ + ۷ + ۶ + ۵ + ۴ + ۳ + ۲ = ۱۱۹ > ۱۰۰
ب
مرحله براي پايان يافتن به اين کار لازم داريم
. n راس موجود مي باشد که حداقل به n ثابت م يکنيم گرافي با 2 n ب ) به ازاي هر
۲ باشد. براي اين کار از استقراي رياضي استفاده مي کنيم. n- و عمق آن ٢
گرافي با ۴ راس را مي توان مسيري در نظر گرفت که راس ۲ آن ريشه مي باشد اين گراف به حداقل ۲ n = پاي استقرا به ازاي ۲
مرحله نياز دارد.
۲ باشد. براي اين کار از استقراي رياضي استفاده مي کنيم. n- و عمق آن ٢
گرافي با ۴ راس را مي توان مسيري در نظر گرفت که راس ۲ آن ريشه مي باشد اين گراف به حداقل ۲ n = پاي استقرا به ازاي ۲
مرحله نياز دارد.
درست باشد
. n = k- حل فرض کنيد براي ١
(k
‐1) گراف را بدين گونه ميسازيم که يک راس را به عنوان ريشه قرار ميدهيم که ۲ بچه دارد . يکي از بچه هاي آن گراف ي با 2
۲ يال ادامه
k - عمليات نياز دارد تا يالهايش پايان يابد . راس ديگرش را به صورت مسيري به طول ١ k- راس هست که به ١
k
- ۲ يال هست . حال اگر يالهاي ريشه را حذف کنيم گراف ١ k - ميدهيم . ميدانيم در حال حاضر بلند ترين مسير گراف همين ١
تا م يخواهد . پس در هر صورت k- عمليات ميخواد و اگر بلن دترين مسير را حذف کنيم باز هم ميماند که ١ k - سالم ميماند که ١
مرحله براي اين گراف نياز داريم . که اين نشان دهنده صحت حکم استقراي ماست. k ما به
تا م يخواهد . پس در هر صورت k- عمليات ميخواد و اگر بلن دترين مسير را حذف کنيم باز هم ميماند که ١ k - سالم ميماند که ١
مرحله براي اين گراف نياز داريم . که اين نشان دهنده صحت حکم استقراي ماست. k ما به
سوال جدول جادويي
الف
ستون ها را ۰ تا ۹۹ شماره گذاري مي کنيم
. اين شماره ها را در رشته هاي دو دويي کد م يکنيم.
.
i = حال به ازاي ٧ تا ١
۲ واحد کم مي کنيم . (i‐ ام آنها ۱ مي باشد را به همراه همه سطر ها انتخاب کرده و از همه ( 1 i ام ستون هايي را که بيت i در مرحله
حال محتواي همه ستو نها از بالا به پائين به ترتيب ۱ تا ۱۰۰ مي باشد .عکس اين کار را براي سطر ها انجام ميدهيم و جدولي به
دست ميايد که همه خانه هاي آن ۱ مي باشد . حال کل جدول را ۱ واحد کم مي کنيم . جدول تمام صفر به دست ميايد
۲ واحد کم مي کنيم . (i‐ ام آنها ۱ مي باشد را به همراه همه سطر ها انتخاب کرده و از همه ( 1 i ام ستون هايي را که بيت i در مرحله
حال محتواي همه ستو نها از بالا به پائين به ترتيب ۱ تا ۱۰۰ مي باشد .عکس اين کار را براي سطر ها انجام ميدهيم و جدولي به
دست ميايد که همه خانه هاي آن ۱ مي باشد . حال کل جدول را ۱ واحد کم مي کنيم . جدول تمام صفر به دست ميايد
ب
برهان خلف
: فرض مي کنيم با ١٣ مرحله اين کار انجام پذير است. به هر يک از خانه هاي جدول يک رشته ١٣ تايي از ٠ و ١
ام، اين خانه را تغيير دهيم. حال تمام حالت هاي i ام هر راس، يک است اگر و تنها اگر در مرحله i اختصاص مي دهيم. که بيت
اين رشته ها ۲۱۳ مي باشد که از تعداد خانه هاي جدول کمتر است پس دو خانه هستند که رشته آنها يکي باشد. اين دو خانه،
در يک قطر قرار دارند ( چرا ؟ ) پس خانه اي که در سطر خانه بالاتر و ستون خانه پايين تر قرار دارد، رشته آن خانه نيز با اين دو
خانه يکي است پس عددي که در ابتدا داشت نيز بايد با اين دو خانه يکي باشد که اين امر امکان پذير نيست.
لینک دانلود
ام، اين خانه را تغيير دهيم. حال تمام حالت هاي i ام هر راس، يک است اگر و تنها اگر در مرحله i اختصاص مي دهيم. که بيت
اين رشته ها ۲۱۳ مي باشد که از تعداد خانه هاي جدول کمتر است پس دو خانه هستند که رشته آنها يکي باشد. اين دو خانه،
در يک قطر قرار دارند ( چرا ؟ ) پس خانه اي که در سطر خانه بالاتر و ستون خانه پايين تر قرار دارد، رشته آن خانه نيز با اين دو
خانه يکي است پس عددي که در ابتدا داشت نيز بايد با اين دو خانه يکي باشد که اين امر امکان پذير نيست.
لینک دانلود
- ارسال ها
- 40
- لایک ها
- 10
- امتیاز
- 8
پاسخ : بررسی مرحله دوم بیست و یکمین المپیاد کامپیوتر
سوال ایدین اگه ایدین اول باشه 4روشن می مونه
چون ایدین می خواد کمترین تعداد روشن باشه برا همین دفعه اول 1111101رو ایدین انجام می ده چون ضرب در 1 بود و نبودش فرقی نداره بعدشم مرتضی هر کاری کنه حداکثر 4 تا می مونه مثلا مرتضی 1101101 یا 1111001رو انجام میده
اینی که می گم اشتباهه؟
سوال ایدین اگه ایدین اول باشه 4روشن می مونه
چون ایدین می خواد کمترین تعداد روشن باشه برا همین دفعه اول 1111101رو ایدین انجام می ده چون ضرب در 1 بود و نبودش فرقی نداره بعدشم مرتضی هر کاری کنه حداکثر 4 تا می مونه مثلا مرتضی 1101101 یا 1111001رو انجام میده
اینی که می گم اشتباهه؟