المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۱۲

در خانه‌ی (۰,۰) جدول مختصات عدد ۱ را می‌نویسیم. فرض کنید در ابتدای هر مرحله در خانه‌ی $(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$ بوده و عدد قبل از آن $\frac{6039-3}{4}$ یعنی ۱۵۰۹ می‌باشد. عدد ۱۵۰۹ به صورت $4k+1$ می‌باشد٬ بنابراین حرکت آخر $u$ بوده و عدد قبل از آن $\frac{1509-1}{4}$ یعنی ۳۷۷ می‌باشد. عدد ۳۷۷ به صورت $4k+1$ می‌باشد. بنابراین حرکت آخر $u$ بوده و عدد قبل از آن $\frac{377-1}{4}$ یعنی ۹۴ می‌باشد. عدد ۹۴ به صورت $4k+2$ می‌باشد٬ بنابراین حرکت آخر $l$ بوده و عدد قبل از آن $\frac{94-2}{4}$ یعنی ۲۳ می‌باشد. عدد ۲۳ به صورت $4k+3$ می‌باشد٬ بنابراین حرکت آخر $d$ بوده و عدد قبل از آن $\frac{23-3}{4}$ یعنی ۵ می‌باشد. عدد ۵ به صورت $4k+1$ می‌باشد٬ بنابراین حرکت آخر $u$ بوده و عدد قبل از آن ۱ می‌باشد.

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

2)

$1082=4k+2 \Longrightarrow k=270 , move=l$

$270=4k+2 \Longrightarrow k=67 , move=l$

$67=4k+3 \Longrightarrow k=16 , move=d$

$16=4k \Longrightarrow k=4 , move=r$

$4=4k \Longrightarrow k=1 , move=r$

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

3)

$1347=4k+3 \Longrightarrow k=336 , move=d$

$336=4k \Longrightarrow k=84 , move=r$

$84=4k \Longrightarrow k=21 , move=r$

$21=4k+1 \Longrightarrow k=5 , move=u$

$5=4k+1 \Longrightarrow k=1 , move=u$

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

4)

$5132=4k \Longrightarrow k=1283 , move=r$

$1283=4k+3 \Longrightarrow k=320 , move=d$

$320=4k \Longrightarrow k=80 , move=r$

$80=4k \Longrightarrow k=20 , move=r$

$20=4k \Longrightarrow k=5 , move=r$

$5=4k+1 \Longrightarrow k=1 , move=u$

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

5)

$5921=4k+1 \Longrightarrow k=1480 , move=u$

$1480=4k \Longrightarrow k=370 , move=r$

$370=4k+2 \Longrightarrow k=92 , move=l$

$92=4k \Longrightarrow k=23 , move=r$

$23=4k+3 \Longrightarrow k=5 , move=d$

$5=4k+1 \Longrightarrow k=1 , move=u$

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


ابزار صفحه