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

[darrande]

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

فکر کنم تعمیمش اینه که به ازای هر 2^n(دو به نمای ان)مهره ما به n+1 رنگ نیاز داریم
اثباتش هم با استقرا هست (نمیدونم چرا وقتی این سوال رو دیدم یاد سوال ترکیبیات ریاضی امسال م دو افتادم)

 

[darrande]

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

سوال 6
​

حالا یه سوال تکراری ولی قشنگ
به چند طریق میشه n مهره که دور یک دایره اند رو با k رنگ رنگ کرد طوری که هیچ دو مهره مجاوری هم رنگ نباشد(خوب فکر کنید)

 

[rezashiri]

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

سوال 6
​

حالا یه سوال تکراری ولی قشنگ
به چند طریق میشه n مهره که دور یک دایره اند رو با k رنگ رنگ کرد طوری که هیچ دو مهره مجاوری هم رنگ نباشد(خوب فکر کنید)

این سوال فکر کنم توی مرحله 1 ریاضی امسال بود (همون آشپزه ) که حالت خاصی از این بود (n=7 , k=3) و فکر کنم بازگشتی حل می شه ...

برای دیدن راه حل کامل می تونید حل سوال 15 این فایل رو ببینید .

 

[rezashiri]

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

فکر کنم تعمیمش اینه که به ازای هر 2^n(دو به نمای ان)مهره ما به n+1 رنگ نیاز داریم
اثباتش هم با استقرا هست (نمیدونم چرا وقتی این سوال رو دیدم یاد سوال ترکیبیات ریاضی امسال م دو افتادم)

این سوال ماله مرحله 2 تستی کامپیوتر پارسال بوده !

 

[darrande]

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

این سوال فکر کنم توی مرحله 1 ریاضی امسال بود (همون آشپزه ) که حالت خاصی از این بود (n=7 , k=3) و فکر کنم بازگشتی حل می شه ...

برای دیدن راه حل کامل می تونید حل سوال 15 این فایل رو ببینید .

من میخواستم جواب بسته ای نسبت به n و k بدست بیارید
خب چون رابطه بازگشتیش رو بدست آوردید با فصل روابط بازگشتی علیپور میتونید فرم بسته ای نسبت به n , k بیابید
ضمنا اون سوال قبلیه جدا سوال سال قبل بود؟
من که اصلا یادم نیست!
خب سوال 7
فرض کنید 1391مهره را در دو ظرف قراردادیم(یعنی مجموع تعداد مهره های دو ظرف میشه 1391)
حال دو نفر هر یک به نو بت مقداری مهره دلخواه تنها از یک ظرف بر میدارد
بازنده کسی است که نتواند حرکتی انجام دهد (یعنی مهره ای نباشه که بگیره)
استراتژِی بردی وجود دارد؟برای کدام یک ؟ چرا؟

 

[erfan_ashorion]

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

نفر اول استراتژِی برد دارد ابتدا نفر اول مقداری از ظرف بیشتر بر میدارد تا مقدار مهره های دو ظرف برابر شود و بعد از آن نفر دوم هر مقدار از هر ظرف برداشت نفر اول به همان مقدار از آن یکی ظرف بر میدارد بدین گونه نفر اول میبرد....!

 

[rezashiri]

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

تو سوال قبلی اگه تعداد مهره ها فرد باشه نفر اول می بره و اگه زوج باشه در یک حالت نفر دوم (تعداد هر دسته برابر باشد) ورگرنه نفر اول!

سوال 8 :

http://bng.netau.net/photos/d128c1d4a331.gif

 

[erfan_ashorion]

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

خب سوال حیفه که بسوزه من پله پله راهنمایی مینویسم خودتون هی یه پله جواب بخونید بعد اگه فکر کردید حل نشود برید پله بعد!!(البته جوگیر بازیه اخه سوال آسونه
اگه سوال سخت بود اره ولی این....!)
پله اول»دقت کنید Cیکی در میون داره 0و1 میشه پس C+1یکی در میون 1و2میشه!!
پله دوم»دقت کنید که میاد عدد رو میبره تو مبنای دو بعد میاد هی یک رقم یک رقم میخونه بعد اگه ارزش مکانیش(یعنی این که صفرمین رقم باشه یا اولین یا....!)
زوج باشه ضرب در 1 میکنه اگه ارزش مکانیش فرد باشه ضرب در دو میکنه!!
پله سوم»

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

 

[darrande]

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

سوال 9-
​

یکی از قشنگ ترین سوالایی که من دیدم اینه(زیبا بودن سوال ربطی به سخت بودنش نداره)
صد گلوله داریم که مجموع وزن آنها 2s هست حداکثر چند kمختلف میتوان یافت که مجموع وزن kگلوله sشود
(راه حل رو کامل بگید)

 

[hoco.hc]

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

فکر کنم تعمیمش اینه که به ازای هر 2^n(دو به نمای ان)مهره ما به n+1 رنگ نیاز داریماثباتش هم با استقرا هست (نمیدونم چرا وقتی این سوال رو دیدم یاد سوال ترکیبیات ریاضی امسال م دو افتادم)

در حقیقت تعمیمش اینه که به ازای هر n به lg(n+1) رنگ نیازه

 

[darrande]

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

در حقیقت تعمیمش اینه که به ازای هر n به lg(n+1) رنگ نیازه

مه ب اون چیزی که گفتم فرق داره؟
جفتشون یه چیز رو میگن (از دو طرف من lgبگیر همون میشه
راستی یه راهنماییبرای سوال 9
مسلما 1و 100 نمیشه .
سعی کنید خودتون یه چیزی ارائه بدید که ماکسیمم بشه

 

[POURIYA- F]

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

سوال 9-
​

یکی از قشنگ ترین سوالایی که من دیدم اینه(زیبا بودن سوال ربطی به سخت بودنش نداره)
صد گلوله داریم که مجموع وزن آنها 2s هست حداکثر چند kمختلف میتوان یافت که مجموع وزن kگلوله sشود
(راه حل رو کامل بگید)

75تا میشه؟
اگر جواب درسته(که بعید میدونم) من گفتم در حالتی که تعداد K حداکثر باشه 50 تا گلوله با وزن زوج و 50 تا با وزن فرد داریم و تعداد اونایی که میتونن 2s بشن رو شمردم!

 

[nima tn]

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

70 ميشه؟؟؟؟

 

[darrande]

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

75تا میشه؟
اگر جواب درسته(که بعید میدونم) من گفتم در حالتی که تعداد K حداکثر باشه 50 تا گلوله با وزن زوج و 50 تا با وزن فرد داریم و تعداد اونایی که میتونن 2s بشن رو شمردم!

نه بیشتر میشه
یه چیز ساده ای که خیلی ها سر حل کرن حواسشون نیست اینه که اگه جمع یه سری s بشه جمع بقیه هم S هست.
از این میتونید کمکک بگیرید

aچیه رو خودتون حدس بزنیدو...خب حالا حل کنید

 

[hoco.hc]

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

فکر کنم جواب بشه 97 .

 

[darrande]

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

فکر کنم جواب بشه 97 .

آ فرین
خب گفتم که جواب رو که نباید برای من بگی راه کامل رو بگو (یکی از قوانین ماراتن ها اینه که سوال رو با پاسخ کامل بنویسیدتا بقیه متوجه شوند)
سوال 10
این سوال دیگه برای تستی نیت
تشریحی
در یک مربع 4*4 در هر خانه فقط یک مهره وجود دارد(همه مهره هایی که در خانه ها قرار دارند مساوی اند(اگه فهمیدید از این چه استفاده ای میشه (ضمنا بدون اینم حل میشه ولی با این بسیار با مزه هست))
در هر حرکت ما میتوانید از دو خانه عمودی یا افقی که یک خانه فاصله دارندکه هر کدام یک مهره برداشته و دو مهره را در خانه وسطی قرار دهیم.
یا عکس این حالت یعنی در خانه ای که حداقل دو مهره قرار دارند دو مهره برداشته ویکی را بالا و یکی را پایین و یا یکی راست و یکی چپ قرار دهیم
آیا با این حرکات میتوان همه مهره ها را دریکی از چهار خانه وسط قرارداد

 

[hoco.hc]

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

آ فرین
خب گفتم که جواب رو که نباید برای من بگی راه کامل رو بگو (یکی از قوانین ماراتن ها اینه که سوال رو با پاسخ کامل بنویسیدتا بقیه متوجه شوند)
سوال 10
این سوال دیگه برای تستی نیت
تشریحی
در یک مربع 4*4 در هر خانه فقط یک مهره وجود دارد(همه مهره هایی که در خانه ها قرار دارند مساوی اند(اگه فهمیدید از این چه استفاده ای میشه (ضمنا بدون اینم حل میشه ولی با این بسیار با مزه هست))
در هر حرکت ما میتوانید از دو خانه عمودی یا افقی که یک خانه فاصله دارندکه هر کدام یک مهره برداشته و دو مهره را در خانه وسطی قرار دهیم.
یا عکس این حالت یعنی در خانه ای که حداقل دو مهره قرار دارند دو مهره برداشته ویکی را بالا و یکی را پایین و یا یکی راست و یکی چپ قرار دهیم
آیا با این حرکات میتوان همه مهره ها را دریکی از چهار خانه وسط قرارداد

راحت ثابت می شه با بیشتر از 97 تا نمی شه ( اعداد 1 و 99 و 100 نمی شند ) بقیه اعداد هم به صورت s/2 , 2/2 , s/4 , s/4 , ... هستند. راحت می فهمید که به ازای بقیه اعداد می شه.

 

[darrande]

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

راحت ثابت می شه با بیشتر از 97 تا نمی شه ( اعداد 1 و 99 و 100 نمی شند ) بقیه اعداد هم به صورت s/2 , 2/2 , s/4 , s/4 , ... هستند. راحت می فهمید که به ازای بقیه اعداد می شه.

آفرین فقط اینم بگو که آخری یه چیزی میشه !
خب برین رو سوال 10
یکی ازایدههای رایج ناوردایی هست با اون راه میتونید حل کنید ولی
من با مفاهیم فیزیکی(منسوب به فیزیک) حل کردم

 

[Olympiad]

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

سوال 10
این سوال دیگه برای تستی نیت
تشریحی
در یک مربع 4*4 در هر خانه فقط یک مهره وجود دارد(همه مهره هایی که در خانه ها قرار دارند مساوی اند(اگه فهمیدید از این چه استفاده ای میشه (ضمنا بدون اینم حل میشه ولی با این بسیار با مزه هست))
در هر حرکت ما میتوانید از دو خانه عمودی یا افقی که یک خانه فاصله دارندکه هر کدام یک مهره برداشته و دو مهره را در خانه وسطی قرار دهیم.
یا عکس این حالت یعنی در خانه ای که حداقل دو مهره قرار دارند دو مهره برداشته ویکی را بالا و یکی را پایین و یا یکی راست و یکی چپ قرار دهیم
آیا با این حرکات میتوان همه مهره ها را دریکی از چهار خانه وسط قرارداد

اصلا میشه تمام مهره ها رو توی یک خونه جمع کرد ؟!؟! (اگه نمیشه این کار رو کرد بگید راه حلمو بگم !!!!!!!!!!!:d)

 

[hoco.hc]

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

اصلا میشه تمام مهره ها رو توی یک خونه جمع کرد ؟!؟! (اگه نمیشه این کار رو کرد بگید راه حلمو بگم !!!!!!!!!!!:d)

خب یعنی چی؟ اگه شما یه راه حل دارید که می گه نمی شه، خب یعنی نمی شه دیگه.