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

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#1
سلام!!

توی این تاپیک می خوام هر روز چند تا از سوالات شبیه به مرحله دوم تستی(یا مرحله 1!) بذارم.

اگه کسی سوالی رو حل کرد با ذکر شماره سوال جوابش رو بذاره و اگه خواست می تونه یه سوال دیگه خودش بذاره!

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

اگه تا 2 روز دیگه هیچ استقبالی نشد جم می کنم می رم!!!:D

=====================

سوال 1 :


به یه دنباله "پالیدروم" می گیم که اگه از هر طرف خونده بشه نمیانگر یه عدد باشه : مثل 12321 .

الف) چند دنباله پالیندروم 5 رقمی داریم که مجموع ارقامش فرد باشه؟

الف) 330 ب) 420 ج) 450 د) 380 ه) 530

ب) فرض کنید دو عمل زیر را می توانیم روی یک دنباله انجام دهیم :

1) اگه یه دنباله پالیدروم 3 تایی در دنباله وجود داشت آن را حذف کنیم(3 عدد باید متوالی باشند)
2) به یکی از ارقام کوچکتر از 9 یک واحد اضافه کنیم.

مثلا برای حذف دنباله 132 باید ابتدا به 1 ، یک وجاد اضافه کنیم که بشه 232 بعد با یک حرکت همه رو حذف کنیم!

حداقل به چند حرکت از شماره 2 نبازه تا دنباله 294563011 رو حذف کنیم؟
الف) 2 ب) 3 ج) 4 د) 5 ه) 6

==========

سوال 2 :

به یک عدد (مثل n ) در مبنای 2 ، k-باینری گوییم اگر عددی که از بسط مبنای 2 ، n به وجود می آید بر k بخش پذیر باشد . مثلا عدد 12 ، 4-باینری است! (چون 1100|4 )

الف ) چند عدد 4-باینری کوچکتر از 128 داریم ؟

ب) چند عدد 5-باینری کوجکتر از 128 داریم؟

ج) چند عدد 6-باینری کوچکتر از 128 داریم؟

----

پ.ن : سوال 2 رو خودم طرح کردم اگه خیلی چرت شد ببخشید دیگه!! :31:
 
آخرین ویرایش توسط مدیر

hoco.hc

New Member
ارسال ها
388
لایک ها
267
امتیاز
0
#2
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

سلام!!

توی این تاپیک می خوام هر روز چند تا از سوالات شبیه به مرحله دوم تستی(یا مرحله 1!) بذارم.

اگه کسی سوالی رو حل کرد با ذکر شماره سوال جوابش رو بذاره و اگه خواست می تونه یه سوال دیگه خودش بذاره!

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

اگه تا 2 روز دیگه هیچ استقبالی نشد جم می کنم می رم!!!:D

=====================

سوال 1 :


به یه دنباله "پالیدروم" می گیم که اگه از هر طرف خونده بشه نمیانگر یه عدد باشه : مثل 12321 .

الف) چند دنباله پالیندروم 5 رقمی داریم که مجموع ارقامش فرد باشه؟

الف) 330 ب) 420 ج) 450 د) 380 ه) 530

ب) فرض کنید دو عمل زیر را می توانیم روی یک دنباله انجام دهیم :

1) اگه یه دنباله پالیدروم 3 تایی در دنباله وجود داشت آن را حذف کنیم(3 عدد باید متوالی باشند)
2) به یکی از ارقام کوچکتر از 9 یک واحد اضافه کنیم.

مثلا برای حذف دنباله 132 باید ابتدا به 1 ، یک وجاد اضافه کنیم که بشه 232 بعد با یک حرکت همه رو حذف کنیم!

حداقل به چند حرکت از شماره 2 نبازه تا دنباله 294563011 رو حذف کنیم؟
الف) 2 ب) 3 ج) 4 د) 5 ه) 6

==========

سوال 2 :

به یک عدد (مثل n ) در مبنای 2 ، k-باینری گوییم اگر عددی که از بسط مبنای 2 ، n به وجود می آید بر k بخش پذیر باشد . مثلا عدد 12 ، 4-باینری است! (چون 1100|4 )

الف ) چند عدد 4-باینری کوچکتر از 128 داریم ؟

ب) چند عدد 5-باینری کوجکتر از 128 داریم؟

ج) چند عدد 6-باینری کوچکتر از 128 داریم؟

----

پ.ن : سوال 2 رو خودم طرح کردم اگه خیلی چرت شد ببخشید دیگه!! :31:
1) الف: ج 450
1) ب : ج 4

2) الف: اگه صفر هم حساب باشه میشه 32
2) ب : اگه صفر هم حساب باشه می شه 64
2) ج :
البته اگه صفر هم حساب باشه.

اگه درسته بگو بگم سوال بعدیا
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#3
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

1) الف: ج 450
1) ب : ج 4

2) الف: اگه صفر هم حساب باشه میشه 32
2) ب : اگه صفر هم حساب باشه می شه 64
2) ج :
البته اگه صفر هم حساب باشه.

اگه درسته بگو بگم سوال بعدیا
درسته ! فقط 2 : ج درسته؟ فکر کنم مضارب 3 رو حساب کردی!!

سوال بعد رو بذار!!
 

hoco.hc

New Member
ارسال ها
388
لایک ها
267
امتیاز
0
#4
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

درسته ! فقط 2 : ج درسته؟ فکر کنم مضارب 3 رو حساب کردی!!

سوال بعد رو بذار!!
قسمت 2 ج می گه که باید بر 6 بخش پذیر باشه. یعنی هم بر 2 و هم بر 3 بخش پذیر باشه. یعنی یکانش باید 0 باشه. حالا برای این که به 3 بخش پذیر باشه باید مجموعش بر 3 بخش پذیر باشه که می تونه هیچی 1 نباشه، 3 تا یک باشه، یا 6 تا یک باشه.

سوال بعدی: یک جایگشت مرتبه n دنباله ای از اعداد 1 تا n است. برای مثال ( 3.1.4.2 ) یک جایگشت مرتبه 4 است. جدول ضرب یک جایگشت< p1,p2,p3, ... , pn > یک جدول n*n است که مقدار خانه سطر i ام و ستون j ام آن برابر pi*pj می باشد.
آیدا و آیدین بازی زیر را انجام می دهند. ابتدا آیدین از اتاق بیرون می رود و آیدا یک جایگشت مرتبه 8 انتخاب می کند و جدول ضرب آن را می نویسد و بر رو هر کدام از 64 خانه جتدول یک سکه می گذارد.
آیدین به اتاق بر میگردد و k تا از خانه ای جدول را انتخاب می کند و ازآیدا می خواد تا سکه های آن k خانه را همزمان از روی صفحه بردار . بعد از انجام این کار، اگر آیدین بتواند جایگشت آیدا را دقیقا تعیین کند ، برنده می شود. کمترین مقدار k که آیدین بتواند همواره برنده شود چند است؟ ( اثبات کنید کمتر نمی شه )
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#5
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

قسمت 2 ج می گه که باید بر 6 بخش پذیر باشه. یعنی هم بر 2 و هم بر 3 بخش پذیر باشه. یعنی یکانش باید 0 باشه. حالا برای این که به 3 بخش پذیر باشه باید مجموعش بر 3 بخش پذیر باشه که می تونه هیچی 1 نباشه، 3 تا یک باشه، یا 6 تا یک باشه.

سوال بعدی: یک جایگشت مرتبه n دنباله ای از اعداد 1 تا n است. برای مثال ( 3.1.4.2 ) یک جایگشت مرتبه 4 است. جدول ضرب یک جایگشت< p1,p2,p3, ... , pn > یک جدول n*n است که مقدار خانه سطر i ام و ستون j ام آن برابر pi*pj می باشد.
آیدا و آیدین بازی زیر را انجام می دهند. ابتدا آیدین از اتاق بیرون می رود و آیدا یک جایگشت مرتبه 8 انتخاب می کند و جدول ضرب آن را می نویسد و بر رو هر کدام از 64 خانه جتدول یک سکه می گذارد.
آیدین به اتاق بر میگردد و k تا از خانه ای جدول را انتخاب می کند و ازآیدا می خواد تا سکه های آن k خانه را همزمان از روی صفحه بردار . بعد از انجام این کار، اگر آیدین بتواند جایگشت آیدا را دقیقا تعیین کند ، برنده می شود. کمترین مقدار k که آیدین بتواند همواره برنده شود چند است؟ ( اثبات کنید کمتر نمی شه )
این سوال قبلا توی این تاپیک مطرح شده و جواب داده شده(البته هنوز اثبات نشده که از این کمتر نمیشه!)

=========

سوال چهارم :

علی و رضا روی یک صفحه 1*n بازی می کنند . علی که شروع کننده ی بازی هست در هر خانه علامت X و رضا در هر خانه علامت O قرار می دهد و تنها قانون بازی این است که در هیچ دو خانه ی مجاوری نمی تواند علامت مشابه قرار گیرد. برای n های مختلف استراتژی برد با کیست؟
 

crazyboy

New Member
ارسال ها
413
لایک ها
539
امتیاز
0
#6
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

این سوال قبلا توی این تاپیک مطرح شده و جواب داده شده(البته هنوز اثبات نشده که از این کمتر نمیشه!)

=========

سوال چهارم :

علی و رضا روی یک صفحه 1*n بازی می کنند . علی که شروع کننده ی بازی هست در هر خانه علامت X و رضا در هر خانه علامت O قرار می دهد و تنها قانون بازی این است که در هیچ دو خانه ی مجاوری نمی تواند علامت مشابه قرار گیرد. برای n های مختلف استراتژی برد با کیست؟
کسی برنده میشود که دو خانه n و 1 رو علامت زده باشه و در غیر اینصورت بازی مساوی میشه !
باید اینو اثبات هم کنم ؟
 
آخرین ویرایش توسط مدیر

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#7
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

من اینو نمیفهمم :
استراتژی برد با کیست؟
یعنی کی(چه کسی!) می تونه یه طوری بازی کنه که برنده باشه!
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#8
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

کسی برنده میشود که دو خانه n و 1 رو علامت زده باشه و در غیر اینصورت بازی مساوی میشه !
باید اینو اثبات هم کنم ؟
یعنی شما می گی مثلا برای n=3 حتما بازی مساوی می شه!!

اینی که شما می گی به نظر من غلطه حالا اگه می خواید اثباتتون رو بگید!
 

crazyboy

New Member
ارسال ها
413
لایک ها
539
امتیاز
0
#9
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

یعنی شما می گی مثلا برای n=3 حتما بازی مساوی می شه!!

اینی که شما می گی به نظر من غلطه حالا اگه می خواید اثباتتون رو بگید!
نه ! من میگم کسی که تونسته باشه خانه n و 1 رو علامت زده باشه برنده میشه !
اگر همچین چیزی نباشه حتما مساوی میشه ! شما مثال نقض میتونی بیاری ؟
اگر تو n=3 طرف بتونه اون یکی رو گول بماله جوری که دو تا خونه 1 و n رو زده باشه برنده میشه در غیر اینصورت بازی همیشه مساوی هست !
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#10
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

نه ! من میگم کسی که تونسته باشه خانه n و 1 رو علامت زده باشه برنده میشه !
اگر همچین چیزی نباشه حتما مساوی میشه ! شما مثال نقض میتونی بیاری ؟
مثال نقض : X - - o ==> x o x o الآن نفر دوم برده!!
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#12
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

الان n=4 بعد از x-oxo بعد نمیشه زد xoxo ؟
فکر کنم شما سوال رو بد متوجه شدید ، سوال می گه کسی که نتونه حرکتی کنه بازنده است نه این که هرکس تعداد خونه های بیشتری برداره ، برنده است!!!
 

hoco.hc

New Member
ارسال ها
388
لایک ها
267
امتیاز
0
#13
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

اگه اونی که نتونه بازی کنه بازنده بشه ، نفر دوم همیشه می تونه برنده بشه.
اگه زوج بشه n ، نفر دوم قرینه نفر اوّل بازی می کنه.
اگه هم فرد باشه، و نفر اول توی خونه i مهره بزاره ، نفر دوم تو فرض می کنه یا خونه راستی یا چپی اون وجود نداره. ==> برای زوچ می تونه نفر دوم ببره. و نفر اوّل هم هیچ وقت نمی تونه تو خونه راستی یا چپی اوّلین خونه ای که گذاشته مهره قرار بده
 

crazyboy

New Member
ارسال ها
413
لایک ها
539
امتیاز
0
#14
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

ادامه نمی دید ؟
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#15
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

سوال پنجم:

50 نقطه روی یک خط قرار دارد می خواهیم هر نقطه را با یکی از رنگ های 1 تا k طوری رنگ کنیم که به ازای هر تعداد نقطه متوالی دلخواه ، حداقل یک رنگ وجود داشته باشد که دقیقا یک بار در بین این نقاط ظاهر شده است . حداقل مقدار k را بیابید.
 

crazyboy

New Member
ارسال ها
413
لایک ها
539
امتیاز
0
#17
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

سوال پنجم:

50 نقطه روی یک خط قرار دارد می خواهیم هر نقطه را با یکی از رنگ های 1 تا k طوری رنگ کنیم که به ازای هر تعداد نقطه متوالی دلخواه ، حداقل یک رنگ وجود داشته باشد که دقیقا یک بار در بین این نقاط ظاهر شده است . حداقل مقدار k را بیابید.
حداقل یک رنگ وجود داشته باشد که دقیقا یک بار در بین این نقاط ظاهر شده است یعنی یک رنگ حداکثر یک بار تکرار شده باشه ؟
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#18
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

حداقل یک رنگ وجود داشته باشد که دقیقا یک بار در بین این نقاط ظاهر شده است یعنی یک رنگ حداکثر یک بار تکرار شده باشه ؟
نه دیگه منظورش دقیقا همین جمله است نمی تونم توضیح بدمش !!

مثلا این مطلوبه 1و2و1و3و1
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#19

hoco.hc

New Member
ارسال ها
388
لایک ها
267
امتیاز
0
#20
پاسخ : ماراتن سوالات تستی مرحله دوم المپیاد کامپیوتر

می شه 6 تا فکر کنم. lg n فکر کنم بشه
 
بالا