بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

[nima tn]

با سلام و خسته نباشید .

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

یه سری قوانینی هست که باید رعایت کنین:
1- سوالاتو شماره گذاری کنید
2- صحبت از کف و این جور چیزا هم نکنید
3-کلا هم پست های بیهوده نگذارید

با تشکر

نقد و بررسی روند برگزاری مرحله دوم المپیادهای علمی سال 91 در تاپیک زیر انجام میشود. قبل از ارسال مطلب، حتما پست اول تاپیک را به دقت بخوانید:

http://www.irysc.com/forum/t7623/
​

 

[bgo]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

آقا اگه یه آدم خیراندیش سوالا رو بذاره خیلی خوب میشه..............:3:

 

[goodarz]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

یه خَیِّری بیاد سوالا رو بذاره......دوباره عین مرحله1 نشه که ما مجبور باشیم کل روز منتظر سوالا بشینیم....

 

[threehandsnal]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

یه خَیِّری بیاد سوالا رو بذاره......دوباره عین مرحله1 نشه که ما مجبور باشیم کل روز منتظر سوالا بشینیم....

باو آدم هر چقدر هم حافظه داشته باشه اون سوالا یادش نمیمونه :4:
هر کدوم یه کتاب بود واسه خودش.... :4:

 

[math]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

باو آدم هر چقدر هم حافظه داشته باشه اون سوالا یادش نمیمونه :4:
هر کدوم یه کتاب بود واسه خودش.... :4:

یعنی دفترچه سوالا رو ندادن؟؟؟؟؟؟

 

[threehandsnal]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

یعنی دفترچه سوالا رو ندادن؟؟؟؟؟؟

نه.. مثل ریاضی بود... سوالا توی پاسخنامه بود...
حداقل واسه رشت که اینجوری بود!!!!!!‌(چون از باشگاه بعید نیست سوالای شهرای مختلف رو برای تنوع فرق بذاره... :4

 

[b_delshad]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

صورت سوال طولانی بود خب بچه ها حق دارن. سوال یکش که یه صفحه بود.
سوال دو: یه صفحه ی n*n را لاتینی گوییم هر گاه با اعداد 1 تا n پرشده باشد به گونه ای که در هیچ سطر و ستونی دو عدد تکراری نیامده باشد. n بزرگ تر از 1000 هست(البته نکته انحرافی بود) و !n نفر دارن با هم با یه صفحه ی n*n لاتینی بازی می کنند. هر کس تو نوبت خودش جای دو تا سطر یا دو تا ستون رو عوض می کنه به طوری که پس از این کار جدول به حالتی جدید که در هیچ یک از مراحل قبلی نبود، در بیاید. کسی که در نوبتش نتواند حرکتی انجام دهد بازنده است.
حالا n! -1 نفر اول می خوان طوری تبانی کنند که نفر !n ببازد. چجوری؟(اثبات کنید می تونن)

سوال سه: (1)w و (2)w و ... و (w(n ، رشته هایی هستند که از حروف کوچک انگلیسی تشکیل شده اند. به طوری که جمع طول همه ی آن ها از q تجاوز نمی کند. یک رشته w هم داریم به طول q.
(a(i رو تعداد تکرار رشته (w(i در w قرار می دهیم. ثابت کنید:

سوال 4 اش هم طولانیه یه صفحه هست. ببخشید دیگه کامل هم یادم نیست.

 

[mojtabaaa1373]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

‫سعید دارای ماشین عجیبی است که دارای
‎1000‎ خانه حافظه می‌باشد. به هر خانه حافظه یک ‎بیت‎ گفته می‌شود و
بیت ‎i‎ام را با ‎M‎ نشان می‌دهیم. هر بیت حافظه یکی از دو مقدار ‎0‎
و ‎1‎ را در خود ذخیره می‌کند.
متاسفانه مقادیر ذخیره شده در حافظه ماشین قابل رویت نیست. تنها
می‌دانیم اعداد ذخیره شده در بیت‌های ‎801‎ تا ‎900‎ برابر ‎0‎ و اعداد
ذخیره شده در بیت‌های ‎901‎ تا ‎1000‎ برابر ‎1‎ هستند.
این ماشین عجیب تنها توانایی اجرای دستورات زیر را دارد:
M= M[i_1 ]∧ M[i_2 ]⋯∧ M[i_k]‎ : با اجرای این دستور در صورتی
که اعداد ذخیره شده در بیت‌های ‎i_1‎ام، ‎i_2‎ام و ‎⋯‎ و ‎i_k‎ام برابر
‎1‎ باشند مقدار ‎M‎ یک و در غیر این صورت صفر خواهد شد.
M= M[i_1 ]∨ M[i_2 ]⋯∨ M[i_k]‎ : با اجرای این دستور در
صورتی که اعداد ذخیره شده در بیت‌های ‎i_1‎ام، ‎i_2‎ام و ‎⋯‎ و ‎i_k‎ام
برابر ‎0‎ باشند مقدار ‎M‎ صفر و در غیر این صورت یک خواهد شد.
M= M[i_1 ]⊕ M[i_2 ]⋯⊕ M[i_k]با اجرای این دستور در صورتی که
تعداد یک‌های ذخیره شده در
بیت‌های ‎i_1‎ام، ‎i_2‎ام و ‎⋯‎ و ‎i_k‎ام فرد باشد مقدار ‎M‎ یک و در
غیر این صورت صفر خواهد شد.
در واقع این سه دستور به ترتیب ‎and‎، ‎or‎ و ‎xor‎ منطقی می‌باشند.
بدیهی است که بلافاصله بعد از این که سعید به دستگاه دستور می‌دهد،
دستگاه دستور را اجرا می‌کند. توجه کنید اندیس‌های ‎i‎,‎i_1,⋯‎,‎i_k‎
حداقل ‎1‎ و حداکثر ‎1000‎ می‌باشند و ‎k‎ نیز حداقل ‎1‎ و حداکثر
‎1000‎ می‌باشد.
در کنار دستورات فوق، این ماشین عجیب به سوال زیر هم پاسخ می‌دهد. آیا
هنوز اعداد ذخیره شده در بیت‌های ‎801‎ام تا 900‎ام برابر با ‎0‎ و اعداد
ذخیره شده در بیت‌های ‎ 901‎ام تا 1000‎ام برابر با ‎1‎ است؟
جواب ماشین به این سوال بله یا خیر خواهد بود.
سعید می ‌خواهد در مورد عدد ‎x = 8× M[1]‎ + ‎4× M[2]‎ + ‎2× M[3]‎ +
‎M[4]‎ اطلاعاتی کسب کند. او دوست دارد این اطلاعات را با اجرای کمترین
تعداد دستور و تنها یک بار سوال پرسیدن کسب کند. به او کمک کنید تا
اطلاعات زیر را بدست اورد.
توجه: در هر قسمت‌ ابتدا دستورات خود را نوشته و سپس آن را در چند سطر
توضیح دهید. در هر قسمت باید از کمترین تعداد دستور ممکن استفاده کنید،
اما نیازی به اثبات کمینه بودن تعداد دستورات نیست . دقت کنید در هر
قسمت فقط یک‌بار می‌توانید سوال بپرسید.

الف) آیا ‎x بزرگتر از ‎5‎ است؟
ب) آیا x‎ توانی از ‎2‎ است؟ (دقت کنید که ‎1‎ توانی از ‎2‎ است).
پ) آیا x‎ بر ‎3‎ بخش‌پذیر است؟

 

[mojtabaaa1373]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

[x_1,y_1 ]‎,‎[x_2‎,‎y_2 ]‎,‎⋯‎,‎[x_n‎,‎y_n]‎، ‎n‎ بازه‌ روی محور
اعداد حقیقی باشند. می‌خواهیم این بازه‌ها را با تعدادی رنگ که هر رنگ با
یک عدد طبیعی شناخته می‌شود، رنگ‌آمیزی کنیم.
در یک رنگ‌آمیزی، ‎f(x)‎ را برابر بزرگترین رنگ بازه‌ها بین بازه‌هایی که
شامل نقطه‌ی ‎x‎ می‌شوند، تعریف می‌کنیم. بدیهی است که ‎f(x)‎ فقط برای
نقاطی که حداقل درون یک بازه قرار دارند تعریف می‌شود. به یک رنگ‌آمیزی
زیبا می‌گوییم، اگر برای هر نقطه مثل ‎x‎ روی محور اعداد حقیقی که حداقل
درون یک بازه قرار دارد، دقیقا یک بازه با رنگ ‎f(x)‎ شامل نقطه‌ی ‎x‎
شود.
ما در ابتدا همه‌ی بازه‌ها را در اختیار نداریم و بازه‌ها یکی یکی در
اختیار ما قرار می‌گیرند. به محض آنکه یک بازه را دریافت کردیم باید یک
رنگ به آن اختصاص دهیم و مجاز به تغییر آن در آینده نیستیم. از روش زیر
برای رنگ‌آمیزی بازه‌ها استفاده می‌کنیم:
فرض کنید بازه ‎v را دریافت کرده باشیم. رنگ‌های ‎ 1,2‎,‎3‎,‎⋯‎را به
ترتیب از کوچک به بزرگ امتحان می کنیم تا به اولین رنگی برسیم که اگر آن
رنگ را به بازه‌ی ‎v‎ اختصاص بدهیم، رنگ‌آمیزی زیبا بماند. (با توجه به
محدود بودن تعداد بازه‌ها، چنین رنگی حتما وجود دارد‎.)‎ بازه‌ی v‎ را با
آن رنگ، رنگ می‌کنیم و به سراغ بازه‌ی بعد می‌رویم و تا آخرین بازه همین
روند را انجام می‌دهیم.
الف) فرض کنید ‎i‎امین بازه‌ای که دریافت می‌کنیم ‎[x_i,y_i]‎
باشد و در ضمن بدانیم ‎x_1< x_2 <⋯ <x_n‎ و ‎y_1 < y_2<⋯ < y_n‎.
نشان دهید بعد از دریافت ‎n‎ بازه، تعداد رنگ‌های استفاده شده، از
‎\log_2 n‎ + ‎1‎ تجاوز نمی‌کند.
ب) با فرض آنکه بازه‌ها دلخواه باشند و با یک ترتیب دلخواه
بازه‌ها را دریافت کنیم، نشان دهید بعد از دریافت ‎n‎ بازه، تعداد
رنگ‌های استفاده شده، از ‎3√n‎ تجاوز نمی‌کند.

 

[mojtabaaa1373]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

به یک جدول ‎n× n‎ یک مربع لاتین می‌گوییم، هرگاه درهر یک از خانه‌های
آن یکی از اعداد ‎1‎,‎2‎,‎⋯‎,‎n‎ نوشته شده باشد و در هیچ سطر و هیچ
ستونی عدد تکراری نداشته باشیم. فرض کنید ‎n‎ عددی طبیعی و بزرگتر از
1000‎ است. n!‎ نفر روی یک مربع لاتین ‎n× n‎ دلخواه شروع به بازی
می‌کنند. هر کس درنوبت خود می‌تواند جای دو سطر و یا دو ستون از جدول را
با هم عوض کند. اولین کسی که حرکتی انجام بدهد که یک مربع لاتین تکراری‌
ایجاد شود بازنده‌ی بازی است و بقیه افراد برنده می‌شوند. ثابت کنید
‎n!-1‎ نفر اول می‌توانند با هم تبانی کنند تا نفر ‎n!‎ام (آخرین نفری که
حرکت اولش را انجام می‌دهد) بازنده شود.

 

[mehran.mojdeh]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

سوال 2(جدول n*n ) با استقرا راحت حل میشه!
ثابت میشه اگر برای تمامی مقادیر n<k+1 بتوان با n!-1 حرکت کاری کرد که با حرکت !n ام جدول تکراری ساخته شه!(یعنی همه ی جدول ها رو ساخت!) برای n=k+1 هم میشه با k+1)!-1) حرکت همچین کاری کرد!
:148:

 

[mojtabaaa1373]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

[x_1,y_1 ]‎,‎[x_2‎,‎y_2 ]‎,‎⋯‎,‎[x_n‎,‎y_n]‎، ‎n‎ بازه‌ روی محور
اعداد حقیقی باشند. می‌خواهیم این بازه‌ها را با تعدادی رنگ که هر رنگ با
یک عدد طبیعی شناخته می‌شود، رنگ‌آمیزی کنیم.
در یک رنگ‌آمیزی، ‎f(x)‎ را برابر بزرگترین رنگ بازه‌ها بین بازه‌هایی که
شامل نقطه‌ی ‎x‎ می‌شوند، تعریف می‌کنیم. بدیهی است که ‎f(x)‎ فقط برای
نقاطی که حداقل درون یک بازه قرار دارند تعریف می‌شود. به یک رنگ‌آمیزی
زیبا می‌گوییم، اگر برای هر نقطه مثل ‎x‎ روی محور اعداد حقیقی که حداقل
درون یک بازه قرار دارد، دقیقا یک بازه با رنگ ‎f(x)‎ شامل نقطه‌ی ‎x‎
شود.
ما در ابتدا همه‌ی بازه‌ها را در اختیار نداریم و بازه‌ها یکی یکی در
اختیار ما قرار می‌گیرند. به محض آنکه یک بازه را دریافت کردیم باید یک
رنگ به آن اختصاص دهیم و مجاز به تغییر آن در آینده نیستیم. از روش زیر
برای رنگ‌آمیزی بازه‌ها استفاده می‌کنیم:
فرض کنید بازه ‎v را دریافت کرده باشیم. رنگ‌های ‎ 1,2‎,‎3‎,‎⋯‎را به
ترتیب از کوچک به بزرگ امتحان می کنیم تا به اولین رنگی برسیم که اگر آن
رنگ را به بازه‌ی ‎v‎ اختصاص بدهیم، رنگ‌آمیزی زیبا بماند. (با توجه به
محدود بودن تعداد بازه‌ها، چنین رنگی حتما وجود دارد‎.)‎ بازه‌ی v‎ را با
آن رنگ، رنگ می‌کنیم و به سراغ بازه‌ی بعد می‌رویم و تا آخرین بازه همین
روند را انجام می‌دهیم.
الف) فرض کنید ‎i‎امین بازه‌ای که دریافت می‌کنیم ‎[x_i,y_i]‎
باشد و در ضمن بدانیم ‎x_1< x_2 <⋯ <x_n‎ و ‎y_1 < y_2<⋯ < y_n‎.
نشان دهید بعد از دریافت ‎n‎ بازه، تعداد رنگ‌های استفاده شده، از
‎\log_2 n‎ + ‎1‎ تجاوز نمی‌کند.
ب) با فرض آنکه بازه‌ها دلخواه باشند و با یک ترتیب دلخواه
بازه‌ها را دریافت کنیم، نشان دهید بعد از دریافت ‎n‎ بازه، تعداد
رنگ‌های استفاده شده، از ‎3√n‎ تجاوز نمی‌کند.

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

 

[popular]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

سوال 2(جدول n*n ) با استقرا راحت حل میشه!
ثابت میشه اگر برای تمامی مقادیر n<k+1 بتوان با n!-1 حرکت کاری کرد که با حرکت !n ام جدول تکراری ساخته شه!(یعنی همه ی جدول ها رو ساخت!) برای n=k+1 هم میشه با k+1)!-1) حرکت همچین کاری کرد!
:148::148::148::148::148::148::148::148::148::148::148::148::148::148::148::148::148::148::148::148::148:

لطفا جوابتونو کامل بزارید با این دو خطی که نوشتین هیچی ثابت نمیشه

 

[popular]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

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

 

[mehran.mojdeh]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

من واسه سوال 4 قسمت آ 2تا استقرا و یه ناوردایی زدم!!!:188::188::188:
میشه شما هم جوابتونو بذارید؟:217::217::217::217::217::217::217::217:

 

[popular]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

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

 

[popular]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

من واسه قسمت آ 2تا استقرا و یه ناوردایی زدم!!!:188::188::188:
میشه شما هم جوابتونو بذارید؟:217::217::217::217::217::217::217::217:

اگه منظورت سوال 2 باشه من کل صفحه هام پرشد ولی درکل ثابت کردم که تعداد کل مربع های جادویی n! است و (n!-1)نفر همینقدر شکل درست میکنند که تکراری نیست و یک شکل هم که شکل اولیه بوده یعنی کل حالت ها درست شده و نفر اخر شکل تکراری درست می کنه که از استقرا هم کمک گرفتم ولی فکر کنم از راه های دیگه ای هم میشه حل کرد

 

[mojtabaaa1373]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

‫سعید دارای ماشین عجیبی است که دارای
‎1000‎ خانه حافظه می‌باشد. به هر خانه حافظه یک ‎بیت‎ گفته می‌شود و
بیت ‎i‎ام را با ‎M‎ نشان می‌دهیم. هر بیت حافظه یکی از دو مقدار ‎0‎
و ‎1‎ را در خود ذخیره می‌کند.
متاسفانه مقادیر ذخیره شده در حافظه ماشین قابل رویت نیست. تنها
می‌دانیم اعداد ذخیره شده در بیت‌های ‎801‎ تا ‎900‎ برابر ‎0‎ و اعداد
ذخیره شده در بیت‌های ‎901‎ تا ‎1000‎ برابر ‎1‎ هستند.
این ماشین عجیب تنها توانایی اجرای دستورات زیر را دارد:
M= M[i_1 ]∧ M[i_2 ]⋯∧ M[i_k]‎ : با اجرای این دستور در صورتی
که اعداد ذخیره شده در بیت‌های ‎i_1‎ام، ‎i_2‎ام و ‎⋯‎ و ‎i_k‎ام برابر
‎1‎ باشند مقدار ‎M‎ یک و در غیر این صورت صفر خواهد شد.
M= M[i_1 ]∨ M[i_2 ]⋯∨ M[i_k]‎ : با اجرای این دستور در
صورتی که اعداد ذخیره شده در بیت‌های ‎i_1‎ام، ‎i_2‎ام و ‎⋯‎ و ‎i_k‎ام
برابر ‎0‎ باشند مقدار ‎M‎ صفر و در غیر این صورت یک خواهد شد.
M= M[i_1 ]⊕ M[i_2 ]⋯⊕ M[i_k]با اجرای این دستور در صورتی که
تعداد یک‌های ذخیره شده در
بیت‌های ‎i_1‎ام، ‎i_2‎ام و ‎⋯‎ و ‎i_k‎ام فرد باشد مقدار ‎M‎ یک و در
غیر این صورت صفر خواهد شد.
در واقع این سه دستور به ترتیب ‎and‎، ‎or‎ و ‎xor‎ منطقی می‌باشند.
بدیهی است که بلافاصله بعد از این که سعید به دستگاه دستور می‌دهد،
دستگاه دستور را اجرا می‌کند. توجه کنید اندیس‌های ‎i‎,‎i_1,⋯‎,‎i_k‎
حداقل ‎1‎ و حداکثر ‎1000‎ می‌باشند و ‎k‎ نیز حداقل ‎1‎ و حداکثر
‎1000‎ می‌باشد.
در کنار دستورات فوق، این ماشین عجیب به سوال زیر هم پاسخ می‌دهد. آیا
هنوز اعداد ذخیره شده در بیت‌های ‎801‎ام تا 900‎ام برابر با ‎0‎ و اعداد
ذخیره شده در بیت‌های ‎ 901‎ام تا 1000‎ام برابر با ‎1‎ است؟
جواب ماشین به این سوال بله یا خیر خواهد بود.
سعید می ‌خواهد در مورد عدد ‎x = 8× M[1]‎ + ‎4× M[2]‎ + ‎2× M[3]‎ +
‎M[4]‎ اطلاعاتی کسب کند. او دوست دارد این اطلاعات را با اجرای کمترین
تعداد دستور و تنها یک بار سوال پرسیدن کسب کند. به او کمک کنید تا
اطلاعات زیر را بدست اورد.
توجه: در هر قسمت‌ ابتدا دستورات خود را نوشته و سپس آن را در چند سطر
توضیح دهید. در هر قسمت باید از کمترین تعداد دستور ممکن استفاده کنید،
اما نیازی به اثبات کمینه بودن تعداد دستورات نیست . دقت کنید در هر
قسمت فقط یک‌بار می‌توانید سوال بپرسید.

الف) آیا ‎x بزرگتر از ‎5‎ است؟
ب) آیا x‎ توانی از ‎2‎ است؟ (دقت کنید که ‎1‎ توانی از ‎2‎ است).
پ) آیا x‎ بر ‎3‎ بخش‌پذیر است؟

الف 2
ب 3
ج 4

 

[mojtabaaa1373]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

صورت سوال طولانی بود خب بچه ها حق دارن. سوال یکش که یه صفحه بود.
سوال دو: یه صفحه ی n*n را لاتینی گوییم هر گاه با اعداد 1 تا n پرشده باشد به گونه ای که در هیچ سطر و ستونی دو عدد تکراری نیامده باشد. n بزرگ تر از 1000 هست(البته نکته انحرافی بود) و !n نفر دارن با هم با یه صفحه ی n*n لاتینی بازی می کنند. هر کس تو نوبت خودش جای دو تا سطر یا دو تا ستون رو عوض می کنه به طوری که پس از این کار جدول به حالتی جدید که در هیچ یک از مراحل قبلی نبود، در بیاید. کسی که در نوبتش نتواند حرکتی انجام دهد بازنده است.
حالا n! -1 نفر اول می خوان طوری تبانی کنند که نفر !n ببازد. چجوری؟(اثبات کنید می تونن)

سوال سه: (1)w و (2)w و ... و (w(n ، رشته هایی هستند که از حروف کوچک انگلیسی تشکیل شده اند. به طوری که جمع طول همه ی آن ها از q تجاوز نمی کند. یک رشته w هم داریم به طول q.
(a(i رو تعداد تکرار رشته (w(i در w قرار می دهیم. ثابت کنید:

سوال 4 اش هم طولانیه یه صفحه هست. ببخشید دیگه کامل هم یادم نیست.

فرض کنید k-i دنباله به طول b-i داریم مینیمم a-i برای رشته های به طول k-i برابر با q/b-i*k-i میشه پس باید ماکس b-i*k-i رو به دست اورد از طرفی جمع k-i ها n هست با یه میگسینگ به دست بیارید باید همه ی b-i*k-i ها برابر باشن بقیش هم فقط نوشتنه.

 

[mehran.mojdeh]

پاسخ : بررسی آزمون مرحله دوم بیست و دومین المپیاد کامپیوتر(فقط در همین تاپیک)

لطفا جوابتونو کامل بزارید با این دو خطی که نوشتین هیچی ثابت نمیشه

طبق فرض میشه با k!-1 حرکت تمامی حالت های مربع D رو ساخت پس اگر اون حرکت ها رو فقط روی سطر ها و ستون های D انجام بدیم روی A و B هم تاثیر میذاره و میشه همه ی حالت های مجموعه ی A[SUB]^[/SUB]B[SUB]^[/SUB]D ساخته میشه یعنی اگر در C عدد x باشه تمام حالت های بقیه ی عددها (K تا x و K+1 از بقیه) تویه 1- [SUP]2[/SUP](K+1) خونه (A[SUB]^[/SUB]B[SUB]^[/SUB]D ) ساخته میشه! پس برای اینکه این عمل را برای تمامی مقادیر x انجام بدیم مسئله برای n=K+1 ثابت میشه! پس چون x میتونه K+1 عدد باشه و برای هر x نیاز به K!-1 حرکت یعنی(K+1)!-(K+1) و برای اینکه تمامی مقادیر در خانه ی C باشد باید حداقل K حرکت انجام داد که در کل نیاز به K+1)!-(K+1)+K=(K+1)!-1) حرکت است پس حکم درسته!!!