المپدیا

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

ابزار کاربر

ابزار سایت


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

ﺷﻨﮕﻮل در راﻩ ﺣﻞ ﻣﻌﺎدﻟﻪ!

ﺷﻨﮕﻮل ﻣﺤﻮ ﻣﻌﺎدﻟﻪی زﯾﺮ ﺷﺪﻩ اﺳﺖ!

M = ((A B) $\star$ C)  $\oplus$D

در اﯾﻦ ﻣﻌﺎدﻟﻪ

  • ﻋﻤﻠﮕﺮ ﮐﺎر OR ﺑﯿﺘﯽ را ﻣﯽﮐﻨﺪ؛ ﺑﻪ اﯾﻦ ﺻﻮرت ﮐﻪ هر دو ﻋﺪد را اﺑﺘﺪا ﺑﻪ ﻣﺒﻨﺎی دو ﻣﯽﺑﺮد (در ﺻﻮرﺗﯽ ﮐﻪ ﻃﻮﻟﺸﺎن ﺑﺮاﺑﺮ ﻧﺒﻮد ﺑﻪ ﺳﻤﺖ ﭼﭗ ﻋﺪد کوچک‌تر ﺗﺎ ﺣﺪ ﻻزم ﺻﻔﺮ اﺿﺎﻓﻪ ﻣﯽﮐﻨﺪ)، ﺳﭙﺲ ﻋﺪد ﺟﺪﯾﺪی را ﺑﻪﻋﻨﻮان ﺟﻮاب ﻣﯽﺳﺎزد ﮐﻪ هر ﺑﯿﺖ آن در ﺻﻮرﺗﯽ ﯾﮏ اﺳﺖ ﮐﻪ ﺣﺪاﻗﻞ ﯾﮑﯽ از ﺑﯿﺖهای ﻣﺘﻨﺎﻇﺮ (از ﻧﻈﺮ اﻧﺪﯾﺲ) در دو ﻋﻤﻠﻮﻧﺪ دادﻩ ﺷﺪﻩ، ﯾﮏ ﺑﺎﺷﺪ. ﺑﺮای ﻣﺜﺎل .10=28 و اﺳﺖ 7=35
  • ﻋﻤﻠﮕﺮ $\star$ همان ﻋﻤﻠﮕﺮ ب.م.م. ﻣﻌﺮوف اﺳﺖ ﮐﻪ ﺑﺰرگ‌ترین ﻣﻘﺴﻮم ﻋﻠﯿﻪ ﻣﺸﺘﺮک دو ﻋﺪد دو ﻃﺮﻓﺶ را ﺑﺮ ﻣﯽﮔﺮداﻧﺪ.
  • ﻋﻤﻠﮕﺮ $\oplus$ ﮐﺎر $XOR$ ﺑﯿﺘﯽ را ﻣﯽﮐﻨﺪ؛ ﮐﻪ ﺑﺴﯿﺎر ﺷﺒﯿﻪ $OR$ اﺳﺖ ﻣﻨﺘﻬﯽ هر ﺑﯿﺖ ﻣﺘﻨﺎﻇﺮ ﻋﺪد ﺟﻮاب ﺗﻨﻬﺎ در ﺻﻮرﺗﯽ ﯾﮏ اﺳﺖ ﮐﻪ دﻗﯿﻘﺎً (ﻧﻪ ﺣﺪاﻗﻞ) ﯾﮑﯽ از ﺑﯿﺖهای ﻣﺘﻨﺎﻇﺮ ﻋﻤﻠﻮﻧﺪهاﯾﺶ ﯾﮏ ﺑﺎﺷﺪ. ﺑﺮای ﻣﺜﺎل $5\oplus3=۶$ اﺳﺖ و $2\oplus8=10$.

اﻟﻒ): اﮔﺮ هر ﯾﮏ از ﭘﺎراﻣﺘﺮهای $C$ ،$B$ ،$A$ و $D$ ﺑﺘﻮاﻧﻨﺪ ﻣﻘﺎدﯾﺮ ﺑﯿﻦ ١ ﺗﺎ ١٠ را ﺑﮕﯿﺮﻧﺪ، و ﺗﻌﺪاد ﺟﻮاب‌های ﻣﺨﺘﻠﻒ ﻗﺎﺑﻞ ﺗﻮﻟﯿﺪ ﺑﺮای $M$ ﺑﺮاﺑﺮ ﺑﺎ $T$ ﺑﺎﺷﺪ، در اﯾﻦ ﺻﻮرت ﺑﺎﻗﯽﻣﺎﻧﺪﻩی ﺗﻘﺴﯿﻢ $T^{9}$ ﺑﺮ $\Delta$ ﭼﻨﺪ اﺳﺖ؟

ب): ﻓﺮض ﮐﻨﯿﺪ اﯾﻦ ﭼﻬﺎر ﭘﺎراﻣﺘﺮ ﻓﻘﻂ ﺑﺘﻮاﻧﻨﺪ اﻋﺪاد اول کوچک‌تر از ١٠٠٠ را در ﺧﻮد ﺟﺎی دهند. اﮔﺮ بیش‌تر و کم‌ترین ﻣﻘﺪار ﻗﺎﺑﻞ ﺗﻮﻟﯿﺪ ﺑﺮای $M$ ﺑﻪ ﺗﺮﺗﯿﺐ $X$ و $Y$ ﺑﺎﺷﻨﺪ، آنﮔﺎﻩ ﺑﺎﻗﯽﻣﺎﻧﺪﻩی ﺗﻘﺴﯿﻢ ${Y^4}+{X^2}$ ﺑﺮ $\Delta$ ﭼﻨﺪ اﺳﺖ؟ ﭘﺎﺳﺦ

ج): اﮔﺮ اﯾﻦ ﭘﺎراﻣﺘﺮهای $C$ ،$B$ ،$A$ و $D$ ﺑﺘﻮاﻧﻨﺪ اﻋﺪاد ﻃﺒﯿﻌﯽ کوچک‌تر از $\Delta$ را ﺑﮕﯿﺮﻧﺪ، و بیش‌ترین و کم‌ترین ﻣﻘﺪار ﻣﻤﮑﻦ ﺑﺮای $M$ ﺑﻪ ﺗﺮﺗﯿﺐ $w$ و $z$ ﺑﺎﺷﻨﺪ، ﺑﺎﻗﯽﻣﺎﻧﺪﻩی $7w(1+8z)$ ﺑﺮ $\Delta$ ﭼﻨﺪ اﺳﺖ؟


ابزار صفحه