Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۳:سوال ۱۲

سؤال ۱۲

در خانه‌ی (۰,۰) جدول مختصات عدد ۱ را می‌نویسیم. فرض کنید در ابتدای هر مرحله در خانه‌ی (x,y) عدد i نوشته شده است. در آن مرحله i را پاک می‌کنیم و یکی از چهار حرکت زیر را انجام می‌دهیم:

  • در خانه‌ی (x+۱,y) عدد ۴i را می‌نویسیم،
  • در خانه‌ی (x,y+۱) عدد ۴i+۱ را می‌نویسیم،
  • در خانه‌ی (x۱,y) عدد ۴i+۲ را می‌نویسیم، یا
  • در خانه‌ی (x,y۱) عدد ۴i+۳ را می‌نویسیم.

پس از انجام چند مرحله متوجه می‌شویم در خانه (۱,۱) عدد K نوشته شده است. K کدام گزینه می‌تواند باشد؟

  1. ۶۰۳۹
  2. ۱۰۸۲
  3. ۱۳۴۷
  4. ۵۱۳۲
  5. ۵۹۲۱

پاسخ

گزینه (۵) درست است.

حرکت به سمت‌های راست٬ چپ٬ بالا و پایین را به ترتیب u،l،r و d نمایش می‌دهیم. حال گزینه‌ها را یکی پس از دیگری امتحان کرده و جایگاه آن‌هارا مشخص می‌کنیم:

1) عدد ۶۰۳۹ به صورت 4k+3 می‌باشد٬ بنابراین حرکت آخر d بوده و عدد قبل از آن 603934 یعنی ۱۵۰۹ می‌باشد. عدد ۱۵۰۹ به صورت 4k+1 می‌باشد٬ بنابراین حرکت آخر u بوده و عدد قبل از آن 150914 یعنی ۳۷۷ می‌باشد. عدد ۳۷۷ به صورت 4k+1 می‌باشد. بنابراین حرکت آخر u بوده و عدد قبل از آن 37714 یعنی ۹۴ می‌باشد. عدد ۹۴ به صورت 4k+2 می‌باشد٬ بنابراین حرکت آخر l بوده و عدد قبل از آن 9424 یعنی ۲۳ می‌باشد. عدد ۲۳ به صورت 4k+3 می‌باشد٬ بنابراین حرکت آخر d بوده و عدد قبل از آن 2334 یعنی ۵ می‌باشد. عدد ۵ به صورت 4k+1 می‌باشد٬ بنابراین حرکت آخر u بوده و عدد قبل از آن ۱ می‌باشد.

باتوجه به توضیحات فوق معلوم می‌شود که عدد ۶۰۳۹ بعد از دنباله udluud نوشته می‌شود که جایگاه آن باتوجه به شکل زیر در نقطه (۱-،۱-) خواهد بود:

2)

1082=4k+2k=270,move=l

270=4k+2k=67,move=l

67=4k+3k=16,move=d

16=4kk=4,move=r

4=4kk=1,move=r

عدد ۱۰۸۲ بعد از دنباله rrdll نوشته می‌شود که جایگاه آن نقطه (۱-,۰) می‌باشد.

3)

1347=4k+3k=336,move=d

336=4kk=84,move=r

84=4kk=21,move=r

21=4k+1k=5,move=u

5=4k+1k=1,move=u

عدد ۱۳۴۷ بعد از دنباله uurrd نوشته می‌شود که جایگاه آن نقطه (۲,۱) می‌باشد.

4)

5132=4kk=1283,move=r

1283=4k+3k=320,move=d

320=4kk=80,move=r

80=4kk=20,move=r

20=4kk=5,move=r

5=4k+1k=1,move=u

عدد ۵۱۳۲ بعد از دنباله urrrdr نوشته می‌شود که جایگاه آن نقطه (۴,۰) می‌باشد.

5)

5921=4k+1k=1480,move=u

1480=4kk=370,move=r

370=4k+2k=92,move=l

92=4kk=23,move=r

23=4k+3k=5,move=d

5=4k+1k=1,move=u

عدد ۵۹۲۱ از دنباله udrlru نوشته می‌شود که جایگاه آن نقطه (۱,۱) می‌باشد.


ابزار صفحه