المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۲:سوال ۹

ﺷﻨﮕﻮل ﺑﻪ ﻣﺪرﺳﻪ ﻣﯽرود!

دﯾﺸﺐ ﺷﻨﮕﻮل ﺗﺎ دﯾﺮوﻗﺖ ﻣﺸﻐﻮل دﯾﺪن ﻓﯿﻠﻢ و ﻓﻮﺗﺒﺎل ﺑﻮد و ﺗﺎ ﺻﺒﺢ ﮐﺎﺑﻮس دﯾﺪ! ﺑﻪ ﺷﻨﮕﻮل در ﮐﺎﺑﻮﺳﺶ اﻟﻬﺎم ﺷﺪ ﮐﻪ هر ﻋﺪد ﻃﺒﯿﻌﯽ $X$ را ﻣﯽﺗﻮان ﺑﻪﺻﻮرت $X=2^K M$ ﻧﻮﺷﺖ ﮐﻪ در آن $K$ ﻋﺪدی ﺣﺴﺎﺑﯽ (ﻧﺎﻣﻨﻔﯽ) و $M$ ﻋﺪدی ﻓﺮد اﺳﺖ.

ﺷﻨﮕﻮل ﮐﻪ ﺧﻮﺷﺤﺎل ﺑﻮد ﺣﺘﯽ در ﮐﺎﺑﻮس و رؤﯾﺎ هم ﻋﻠﻢآﻣﻮزی ﻣﯽﮐﻨﺪ، ﻧﺎﮔﻬﺎن ﺧﻮدش را در ﻧﻘﻄﻪی ﺻﻔﺮ و ﺻﻔﺮ (ﻣﺮﮐﺰ) در ﺣﺎﻟﯽ ﮐﻪ رو ﺑﻪ ﺑﺎﻻ (اﻧﺘﻬﺎی ﻣﺤﻮر ﻣﺜﺒﺖ $y$ها در $x$ = ٠) در ﯾک ﺟﺪول ﻣﺨﺘﺼﺎت ﻧﺎﻣﺘﻨﺎهی ﯾﺎﻓﺖ! ﻧﺪاﯾﯽ از دور ﺑﻪ ﺷﻨﮕﻮل ﮔﻔﺖ ﮐﻪ «ﯾﻮها‌ها‌ها! ﺗﻮ در ﻃﻠﺴﻢ ﮐﺎﺑﻮس‌ها ﮔﯿﺮ اﻓﺘﺎدﻩای! ﺗﻮ ﺑﺎﯾﺪ ﺑﺎ ﺷﺮوع از ﻋﺪد ١، در هر ﻣﺮﺣﻠﻪ اﺑﺘﺪا ﻋﺪد ﻣﺮﺣﻠﻪ را ﺑﻪ ﺻﻮرت $2^K M$ که در آن $M$ ﻋﺪدی ﻓﺮد و $K$ ﻋﺪدی ﻧﺎﻣﻨﻔﯽ اﺳﺖ ﺣﺴﺎب ﮐﻨﯽ، ﺳﭙﺲ ﺑﻪﺗﻌﺪاد $K$ ﻣﺮﺗﺒﻪ ﮔﺮدش ٩٠ درﺟﻪ در ﺟﻬﺖ ساعت‌گرد ﺑﮑﻨﯽ، و ﻧﻬﺎﯾﺘﺎً $M$ ﮔﺎم ﺑﻪ ﺟﻠﻮ (در ﺟﻬﺘﯽ ﮐﻪ رو ﺑﻪ آن ﻗﺮار داری) راﻩ ﺑﺮوی!»

ﺷﻨﮕﻮل ﺷﺮوع ﮐﺮد ﺑﻪ راﻩ رﻓﺘﻦ!

  • ﺑﺮای ﻣﺮﺣﻠﻪ اول، او ﺣﺴﺎب ﮐﺮد ﮐﻪ$2^0 \times 1 = 1$ و ﺑﺮای همین در همان ﺟﻬﺖ رو ﺑﻪ ﺷﻤﺎل ای ﮐﻪ ﺑﻮد ﯾﮏ ﮔﺎم ﺑﺮداﺷﺖ ﺗﺎ ﺑﻪ ﺧﺎﻧﻪی (۱, ۰) ﺑﺮﺳﺪ ($x$ = ٠ و $y$ = ١).
  • در ﮔﺎم دوم او دﯾﺪ ﮐﻪ $2^1 \times 1 = 1$ ﺑﺮای همین ﺑﺘﺪا ٩٠ درﺟﻪ ساعت‌گرد ﭼﺮﺧﯿﺪ ﺗﺎ روﯾﺶ ﺑﻪ ﺳﻤﺖ ﺷﺮق ﺑﺸﻮد و ﺳﭙﺲ ﯾﮏ ﮔﺎم ﺑﺮداﺷﺖ ﺗﺎ ﺑﻪ ﺧﺎﻧﻪی (۱, ۱) ﺑﺮﺳﺪ.
  • در ﮔﺎم ﺳﻮم ﺷﻨﮕﻮل ﻣﺠﺒﻮر ﺑﻮد ﻃﺒﻖ $2^0 \times 3 = 3$ ﺑﺪون ﭼﺮﺧﺎﻧﺪن ﺳﺮش ٣ ﮔﺎم ﺑﻪ ﺟﻠﻮ ﺑﺮدارد و در ﻧﺘﯿﺠﻪ ﺑﻪ ﺧﺎﻧﻪی (۱, ۴) رﺳﯿﺪ و …

اﻟﻒ): ﭘﺲ از ٢٠ ﮔﺎم اﮔﺮ ﺷﻨﮕﻮل در ﻧﻘﻄﻪی ($y$, $x$) ﺑﺎﺷﺪ، در اﯾﻦ ﺻﻮرت ﺑﺎﻗﯽﻣﺎﻧﺪﻩی ﺗﻘﺴﯿﻢ $x^9 y^9$ ﺑﺮ $\Delta$ ﭼﻨﺪاﺳﺖ؟

ب): ﭘﺲ از $\Delta ^ 2$ (دﻟﺘﺎ ﺑﻪ ﺗﻮان دو) ﮔﺎم اﮔﺮ ﺷﻨﮕﻮل در ﻧﻘﻄﻪی ($y$, $x$) ﺑﺎﺷﺪ، در اﯾﻦ ﺻﻮرت ﺑﺎﻗﯽﻣﺎﻧﺪﻩی ﺗﻘﺴﯿﻢ $xy + x + y$ ﺑﺮ $\Delta$ ﭼﻨﺪ اﺳﺖ؟

ج): ﻓﺮض ﮐﻨﯿﺪ ﮐﻪ ﺷﻨﮕﻮل ﻣﺠﺎز اﺳﺖ در ﯾﮑﯽ و ﺗﻨﻬﺎ ﯾﮑﯽ از ﻣﺮاﺣﻠﺶ (ﻣﺜﻞ ﻣﺮﺣﻠﻪ $i$) ﺗﻘﻠﺐ ﮐﻨﺪ و ﺑﻪﺟﺎی ﻋﻤﻞ ﮐﺮدن ﻃﺒﻖ ﺗﺠﺰﯾﻪی $i$ ﺑﻪ ﯾﮏ ﺗﻮان دو و ﯾﮏ ﻋﺪد ﻓﺮد، ﯾﮏ ﻋﺪد دﯾﮕﺮی ﮐﻪ ﺧﻮدش دوﺳﺖ دارد را ﺑﻪ ﺟﺎی $i$ در اﯾﻦ ﻣﺮﺣﻠﻪ اﺳﺘﻔﺎدﻩ ﮐﻨﺪ. دﻗﺖ ﮐﻨﯿﺪ ﮐﻪ ﻣﺮﺣﻠﻪ ﺑﻌﺪی (در ﺻﻮرت ﻟﺰوم) اﻟﺰاﻣﺎً ﺑﺎﯾﺪ از $i+1$ دﻧﺒﺎل ﺷﻮد. در اﯾﻦ ﺣﺎﻟﺖ اﮔﺮ ﺑﺪاﻧﯿﻢ راﻩ ﻓﺮار از اﯾﻦ ﺟﺪول ﻃﻠﺴﻢ ﺷﺪﻩ رﺳﯿﺪن ﺑﻪ ﻧﻘﻄﻪی (٦٦٦٠١٦- و ٦٦-)اﺳﺖ، در اﯾﻦﺻﻮرت ﺷﻨﮕﻮل ﭘﺲ از ﭼﻨﺪ ﺑﺎر ﻣﺤﺎﺳﺒﻪ (ﭼﻨﺪﻣﯿﻦ ﻣﺮﺣﻠﻪ) ﻣﯽﺗﻮاﻧﺪ ﺑﻪ اﯾﻦ ﻧﻘﻄﻪ ﺧﺮوج ﺑﺮﺳﺪ؟ ﭘﺎﺳﺦ ﺧﻮد را ﺑﻪ ﺗﻮان دو رﺳﺎﻧﺪﻩ و ﺑﺎﻗﯽ ﻣﺎﻧﺪﻩاش ﺑﺮ $\Delta$ را ﺑﻨﻮﯾﺴﯿﺪ.


ابزار صفحه