امروز صبح به المپیاد کامپیوتر رفته بودم. گفتم شاید جالب باشه که دفترچه  سوالات مرحله اول بیست و چهارمین دوره المپیاد کامپیوتر سال 1392 را با شما به اشتراک بگذارم.

در المپیاد دو نمونه دفترچه وجود داشت با کد 1 یا 2 که به من کد 2 داده شد. بنابراین سوالات زیر مخصوص دفترچه کد 2 است. ضمنا پاسخ سوالات نیز به زودی گذاشته می شود.

ضمنا سایت این المپیاد هم ببینید.

1.

کاغذی به ضخامت یک دهم میلی متر داده شده است. این کاغذ را بیست بار تا می زنیم. با هر بار تا زدن ضخامت کاغذ دو برابر می شود. ضخامت نهایی کاغذ به کدام عدد نزدیک تر است؟ فرض کنید کاغذ به اندازه کافی برای تا زدن بزرگ است.

 

1)      2 میلی متر

2)      1 متر

3)      100 متر

4)      10cm

5)      2 سانتی متر

2.

می خواهیم اعداد 1 تا 9 را در یک جدول 3×3 بچینیم طوری که اعداد هر سطر از چپ به راست و اعداد هر ستون از بالا به پایین به صورت صعودی مرتب باشند. به چند طریق می توانیم این کار را انجام دهیم، با این فرض که مکان عدد 3 در جدول همانند شکل روبه رو از پیش تعیین شده است؟

 

1)      17

2)      10

3)      16

4)      15

5)      5

3.

کلاس اول مدرسه محمودآباد 12 دانش آموز دارد. معلم کلاس قصد دارد دانش آموزان را به سه دسته تقسیم کند و بین هر دو دانش آموزی که همه دسته نیستند، یک مسابقه برگزار کند. اگر تقسیم بندی طوری انجام شود که تعداد  مسابقات بیشینه شود، این بیش ترین تعداد چند تا است؟

1)      48

2)      42

3)      18

4)      66

5)      24

4.

روی محور اعداد حقیقی 1392 نقطه رنگی متمایز داده شده است که هر یک با یکی از 92 رنگ موجود رنگ شده اند. یک بازه را «مینیمال رنگی» می گوییم اگر همه رنگ ها را پوشش دهد(یعنی از هر رنگی حداقل یک نقطه داخل آن باشد) و هیچ زیر بازه ای از این بازه، همه رنگ ها را پوشش ندهد. حداکثر تعداد بازه های مینیمال رنگی چند تا است؟

1)      1301

2)      1

3)      1391

4)      92

5)      91

5.

ما عادت کرده ایم وقتی عددی را می بینیم آن را به طور پیش فرض در مبنای ده تفسیر می کنیم. حل تصور کنید که استفاده از مبناهای 2 تا 10 به یک اندازه رایج است. در این حالت عدد 12 را می توان به 8 شکل مختلف (در مبناهای 3 تا 10) تفسیر کرد، اما عدد 459 تنها به یک شکل قابل تفسیر است. تعداد اعداد از 1 تا 1392 (در مبنای ده) که تنها به یک شکل قابل تفسیر اند، چند تا است؟ دقت کنید که اعداد تک رقمی تنها به یک شکل قابل تفسیر اند.

1)      271

2)      348

3)      349

4)      358

5)      440

6.

جدولی 1392×1392 داریم که خانه (1,1) آن رنگ شده است. در هر مرحله جدول را از یکی از خطوط موازی اضلاع تا می کنیم. در صورتی که یک خانه رنگی روی یک خانه بی رنگ قرار گیرد، هر دو رنگی می شوند. پس از هر مرحله، جدول را به حالت اولیه بر می گردانیم. حداقل چند حرکت لازم است تا تمامی خانه های جدول رنگی شوند؟

1)      20

2)      22

3)      11

4)      10

5)      21

7.

درخت وراثت نموداری برای نشان دادن میزان ارثی است که به هر یک از اعضای یک خانواده طی سال ها رسیده است. فرض کنید تمام اموال هر فرد بین فرزندانش (در صورتی که فرزندی داشته باشد) تقسیم می شود. میزان ارث هر نفر عددی صحیح و نامنفی است. به چند طریق می توان درخت وراثت روبه رو را تکمیل نمود؟

1)      2016

2)      3780

3)      1512

4)      1134

5)      4032

8.

روی یک خط 1392 درخت قرار گرفته اند که فاصله هر دو درخت متوالی از هم 100 واحد است. ارتفاع درخت ها یک عدد صحیح از 1 تا 1392 است و ارتفاع هیچ دو درختی برابر نیست. ما می توانیم در هر گام یکی از درخت ها را انتخاب کرده، آن را ببریم. هر درخت پس از بریده شدن به سمت راست می افتند و در صورتی برخورد می کنند که ارتفاع درخت افتاده بیش تر یا مساوی فاصله دو درخت باشد. با توجه به این که اطلاعی درباره ترتیب قرار گرفتن درخت ها نداریم، حداقل باید چند درخت را قطع کنیم تا تمامی درخت ها بیافتند؟

1)      100

2)      50

3)      696

4)      1292

5)      37

 

9.

در مسئله قبل، فرض کنید تعداد درخت ها 50 و ارتفاع هر درخت یک عدد صحیح غیر تکراری از 1 تا 50 است. همچنین فاصله بین تمامی درخت ها عدد صحیح x است. در ضمن ترتیب چیدن درخت ها نیز در اختیار ما است. می خواهیم x را طوری تعیین کنیمکه بتوان با یک برش تمامی درخت ها را انداخت. مقدار x حداکثر چند است؟

1)      20

2)      19

3)      18

4)      17

5)      16

 

10.

تعدادی شش ضلعی همانند شکل مقابل داریم که داخل هر خانه یک عدد نوشته شده است. در هر مرحله می توان یکی از خانه هایی را که دقیقا شش همسایه دارد انتخاب کرد و تمام شش ضلعی های دور آن را در جهت عقربه های ساعت چرخاند. می خواهیم مجموع اعداد در خانه های خاکستری بیشینه شود. این مجموع بیشینه چند است؟ دقت کنید که در حین چرخش اعداد جابه جا می شوند ولی رنگ خانه ها ثابت می ماند.

1)      32

2)      26

3)      36

4)      30

5)      18

 

11.

به چند حالت می توان چهار وزیر را روی یک صفحه شطرنج 4×4 قرارداد طوری که یک دیگر را تهدید نکنند؟ دو وزیر یک دیگر را تهدید می کنند اگر هم سطر، هم ستون یا هم قطر باشند. فرض کنید صفحه شطرنج ثابت است و نمی چرخد.

1)      4

2)      8

3)      1

4)     0

5)      2

 

12.

یک صفحه شطرنج 6×6 داریم که یک مهره اسب در خانه (1,1) آن قرار گرفته است. می دانیم که اسب به شکل L روی صفحه حرکت می کند. روی هر خانه حداقل تعداد حرکات لازم برای رسیدن اسب به آن خانه را نوشته ایم. بزرگ ترین این اعداد چند است؟

1)      2

2)      5

3)      1

4)      4

5)      3

 

13.

یک جدول 8×8 داریم. هر خانه یک خانه قرینه نسبت به نقطه وسط دارد. برای مثال خانه 3 در شکل قرینه خانه 1 نسبت به نقطه وسط می باشد. همچنین هر خانه یک خانه قرینه نسبت به خطر عمودی مرکزی نیز دارد. برای مثال خانه 2 قرینه خانه 1 نسبت به خطر عمودی مرکزی می باشد. می خواهیم این جدول را با 3 رنگ، رنگ کنیم به شرطی که هر خانه این جدول حداقل با یکی از دو خانه قرینه خود( قرینه نسبت به خانه مرکز و قرینه نسبت به خط عمودی وسط) همرنگ باشد. به چند طریق می توان این کار را انجام داد؟

 

1)     1516

2)     364

3)     1615

4)     916

5)     316

 

14.

برای مرتب سازی، عمل «ابر جابه جایی»  را چنین تعریف می کنیم. در هر ابر جا به جایی، یک زیر رشته دلخواه از دنباله داده شده را معکوس می کنیم. برای مثال دنباله (1,4,3,2,5)  با یک ابرجا به جایی مرتب می شود. کافی است زیر رشته (4,3,2) را معکوس کنیم. ولی برای مرتب سازی دنباله (4,2,3,1) دو ابر جا به جایی نیاز داریم. ابتدا کل دنباله را معکوس می کنیم تا به (1,3,2,4) برسیم. سپس زیر رشته (3,2) را معکوس می کنیم. حداقل تعداد ابرجابه جایی که برای مرتب سازی هر دنباله دلخواه به طول 4 کافی است، چند است؟

1)      3

2)      در برخی حالات مرتب سازی با ابرجا به جایی ممکن نیست.

3)      4

4)      2

5)      5

 

15.

«جدول صفر و یک» به جدولی می گوییم که در هر خانه آن صفر یا  یک قرار گرفته است. عملی را تعریف می کنیم که از روی یک جدول صفر و یک 4×4 ، یک جدول صفر و یک 4×4 دیگر را به این شکل می سازد که هر خانه جدول جدید برابر حاصل ضرب خانه های مجاور آن خانه در جدول قدیمی است ( خانه مجاور یک خانه، خانه ای است که با آن خانه یک ضلع مشترک دارد). برای مثال با دو بار اعمال این عمل روی جدول زیر به «جدول تمام صفر» ( جدولی که تمام خانه ها آن صفر است ) می رسیم.

 

تعداد کل جدول های صفر و یک 4×4 که با تکرار این عمل روی آن ها به جدول تمام صفر نمی رسیم چند تا است؟

1)      0

2)      120

3)      3

4)      511

5)      1

 

16.

تعداد رشته های 10 تایی از ارقام را بیابید که در هر یک از آن رشته هر رقم برابر با تعداد رقم های یک مجاورش باشد.

1)      20

2)      14

3)      1

4)      2

5)      12

 

17.

تعداد رشته های 10تایی از ارقامل را بیابید که در هر یک از آن رشته ها هر رقم برابر با تعداد رقم های صفر مجاورش باشد.

1)      16

2)      20

3)      10

4)      14

5)      22

 

18.

1393 بادکنک را به ترتیب در یک ردیف قرار داده ایم. در هر مرحله می توانیم یکی از بادکنک ها را بترکانیم. فقط باید این شرط رعایت شود که هر بادکنکی که می ترکد تعداد بادکنک های سمت چپ و راست آن که ترکیده اند حداکثر یکی اختلاف داشته باشد. به چند طریق می توانیم این بادکنک ها را بترکانیم؟

1)     21393

2)     2696

3)     2697

4)     3697

5)     3696

 

19.

خیکوله و خیکولتا روی جدول 4×4 زیر بازی زیر را انجام می دهند:

1. ابتدا خیکوله سطر ها را به دلخواه جا به جا می کند. ( سطر ها را جایگشت می دهد)

2. سپس ستون ها را به دلخواه جابه جا می کند ( ستون ها را جیگشت می دهد )

3. سپس خیکولتا تعداد جفت 1 های مجاور را می شمارد ( دو خانه ای که ضلع مشترک دارند مجاورند) و به تعداد آن به خیکوله شکلات می دهد.

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

1)      17

2)      15

3)      14

4)      13

5)      16

 

20.

تعدادی آجر همانند شکل زیر داده شده اند. هر آجر روی یک یا دو آجر دیگر و یا روی زمین قرار دارد. آجری که روی زمین نیست تنها زمانی می افتد که آجر دیگری زیر قرار نداشته باشد. میخواهیم تعدادی از آجر ها را برداریم طوری که آجر های سطر بالا برداشته نشوند و هیچ آجری نیافتد. در این صورت حداکثر چند آجر را می توان برداشت؟

1)      15

2)      14

3)      12

4)      13

5)      11

 

21.

همانند مسئله قبل آجر هایی همانند شکل روبه رو داریم، با این تفاوت که آجر های خاکستری نباید برداشته شوند. در این صورت حداکثر چند آحر را می توان برداشت؟

1)      5

2)      9

3)      7

4)      6

5)      8

 

22.

جدولی 1392×1392 داریم. خانه های این جدول را به ترتیب با اعداد 0 تا 1 – ² 1392 به ترتیب سزری از بالا به پایین و سپس ستونی از چپ به راست شماره گذاری می کنیم. به این ترتیب خانه های سطر iام با اعداد 1392×i تا 1-(1392)(i+1) از چپ به راست شماره گذاری شده اند. دو خانه از جدول را مجاور می نامیم در صورتی که در یک ضلع اشتراک داشته باشند و آن ضلع توسط هیچ کدام از آن دو خانه بسته نشده باشد. طریقه بسته شدن اضلاع جدول این گونه است که عدد نوشته شده در خانه را به صورت دودویی می نویسیم. در صورتی که این عدد کمتر از چهار رقم داشت با گذاشتن 0 در پشت عدد، آن را چهار رقمی می کنیم.  حال یک بودن هرکدام از چهار رقم اول این عدد باعث بسته شدن ضلع متناظرش می شود. ارقام اول تا چهارم به ترتیب با ضلع های بالا، راست، پایین و چپ آن خانه متناظرند. (رقم اول کم ارزش ترین رقم در نمایش دودویی است). یک حرکت مجاز را رفتن از خانه ای به یکی از خانه های مجاورش تعریف می کنیم. حال در جدول ساخته شده به یک مجموعه از خانه ها «همبند» می گوییم اگر هر دو خانه با انجام تعدادی حرکت مجاز از یک دیگر قابل دسترسی باشند. اندازه بزرگ ترین مجموعه همبند این جدول را محاسبه کنید.

1)      6960

2)      2784

3)      4176

4)      5568

5)      1392

 

23.

دنباله (0,0,0,0,0,0) بر روی کاغذ نوشته شده است. در هر مرحله می توان یکی از تغییرات زیر را روی دنباله اعمال کرد:

• تمامی اعداد داخل لیست در دو ضرب می شوند.
• یکی از اعداد دنباله انتخاب و به علاوه یک می شود.

کم ترین تعداد مرحله برای رسیدن به دنباله  (7,11,5,1,3,8) چند است؟

1)      16

2)      15

3)      17

4)      18

5)      14

 

24.

مار کوچکی متشکل از 8 مکعب به ضلع 1 همانند شکل زیر داریم که از سر تا دم با شماره های 1 تا 8 شماره گذاری شده اند. هر دو مکعب پشت سر هم با مفصل کوچکی به هم وصل شده اند و فقط قابلیت چرخش نسبت به یک دیگر را دارند. این مار کوچک را به چند حالت مختلف می تواند در یک جعبه مکعبی به ضلع 2 جا داد؟ دو حالت مختلف در نظر گرفته می شوند اگر دو قطعه با شماره های مختلف از بدن مار در یک مکان از جعبه مکعبی قرار بگیرند. یعنی اگر دو حالت با چرخش مکعبی به هم تبدیل شوند، یکسان نیستند.

 

برنامه زیر را در نظر بگیرید:

مقدار s را برابر با 0 قرار بده.

به ازای i = 1 , 2 , … , x عملیات زیر را انجام بده:

اگر x به i بخش پذیر بود، مقدار s را برابر با x + i قرار بده.

مقدار s را گزارش کن.

فرض کنید خروجی برنامه بالا برابر باشد با:

f(x)

به طور مثال اگر x را برابر با 4 قرار دهیم، به ازای i = 1 ، i = 2 و i = 4 مقدار s  افزایش پیدا می کند. پس مقدار (f (4 برابر با 7 خواهد بود.

25.

مقدار (f(441 برابر چند است؟

1)      762

2)      362

3)      740

4)      300

5)      741

26. مقدارعبارت زیر چند است؟

f(1) + f(2) + f(3) + … + f(100)

1)      8249

2)      8354

3)      3249

4)      3299

5)      8299

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

27.

اگر کشور پنیر شمالی 100 نیرو  و کشور پنیر جنوبی 45 نیرو در اختیار داشته باشد. کشور پنیر شمالی حداکثرچند جزیره را می تواند تصاحب کند؟

1)      6

2)      7

3)      4

4)      3

5)      5

 

28.

اگر کشور پنیر جنوبی 45 نیرو در اختیار داشته باشد، کشور پنیر شمالی حداقل چند نیرو باید داشته باشد تا مطمئن باشد که نیمی از جزیره ها را تصاحب می کند؟

1)      73

2)      70

3)      69

4)      75

5)      68

 

شش نفر دور یک میز نشسته اند که هر یک از آن ها کلاهی بر سر دارد. کلاه ها به رنگ های قرمز، آبی و سبز هستند. می دانیم که از هر رنگ حداقل یک کلاه وجود دارد. هر کسی می تواند رنگ کلاه پنج نفر دیگر را ببیند، اما توان دیدن رنگ کلاه خود را ندارد. این شش نفر بسیار باهوش هستند و در صورتی که از لحاظ منطقی امکان تشخیص رنگ کلاه خود با توجه به رنگ کلاه دیگران وجود داشته باشد، رنگ کلاه خود را تشخیص می دهند. برای مثال اگر شخصی هیچ کلاهی با رنگ آبی روی سز پنج نفر دیگر نبیند، متوجه می شود که رنگ کلاه او آبی است، چرا که می داند از هر رنگ باید حداقل یک کلاه، در بین کلاه ها موجود باشد.

 

29.

اگر از این شش نفر بخواهیم در صورتی که توان تشخیص رنگ کلاه خود را دارند، دست خود را هم زمان بلند کنند، با فرض پاسخ صادقانه حداقل و حداکثر چند نفر ممکن است دست خود را بلند کنند؟

1)      2 و 6

2)      6 و 6

3)      2 و 2

4)      صفر و 6

5)      صفر و 2

30.

حالا پس از این پاسخ صادقانه، مجددا از این شش نفر می خواهیم که در صورتی که هم اکنون رنگ کلاه خود را می دانند، دست خود را بلند کنند. در این حالت (باز با فرض پاسخ صادقانه) حداقل و حداکثر چند نفر ممکن است دست خود را بلند کنند؟

1)      2 و 6

2)      صفر و 6

3)      2 و 2

4)      6 و 6

5)      صفر و 2