المپدیا

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

ابزار کاربر

ابزار سایت


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

ﺷﻨﮕﻮل ﻣﯽﺧﻮاهد داﯾﺮﻩ ﺑﮑﺸﺪ!

ﺷﻨﮕﻮل ﻣﺤﻮر ﻣﺜﺒﺖ اﯾﮑﺲها از ١ ﺗﺎ$\Delta^2$ را در اﺧﺘﯿﺎر دارد. ﺑﺮای هر ﻧﻘﻄﻪی $i$ (ﮐﻪ ‎$(1 \leq i \leq \Delta^2$ اﮔﺮ بزرگ‌ترین ﻣﻘﺴﻮمﻋﻠﯿﻪ ﺗﻮان دوی $i$ ﺑﺎﺷﺪ، ﺷﻨﮕﻮل ﻣﺠﺎز اﺳﺖ ﺑﺎ ﻣﺮﮐﺰﯾﺖ اﯾﻦ ﻧﻘﻄﻪ ﯾﮏ داﯾﺮﻩ ﺑﺎ ﺷﻌﺎع $2^k$ رﺳﻢ ﮐﻨﺪ. ﺑﺮای ﻣﺜﺎل از ﻧﻘﻄﻪی ١٢ ﺗﻨﻬﺎ ﻣﯽﺗﻮان ﯾﮏ داﯾﺮﻩ ﺑﺎ ﺷﻌﺎع ٤ رﺳﻢ ﮐﺮد ﺗﺎ ﺗﻤﺎم ﻧﻘﺎط ٨ و ٩ و ١٠ و … و ١٦ را در ﺑﺮ ﺑﮕﯿﺮد (ﻧﻘﺎط روی داﯾﺮﻩ، زﯾﺮ داﯾﺮﻩ ﻣﺤﺴﻮب ﻣﯽﺷﻮﻧﺪ). ﺷﻨﮕﻮل ﻣﯽﺧﻮاهد ﯾﮏ زﯾﺮﻣﺠﻤﻮﻋﻪﻣﺜﻞ $Q$ از اﯾﻦ ﻧﻘﺎط را اﻧﺘﺨﺎب ﮐﺮدﻩ و ﺑﻪ ﻣﺮﮐﺰﯾﺖ هر ﮐﺪام از ﻧﻘﺎط زﯾﺮﻣﺠﻤﻮﻋﻪی $Q$، داﯾﺮﻩی ﯾﮑﺘﺎی آن ﻧﻘﻄﻪ را ﺑﮑﺸﺪ ﻃﻮری ﮐﻪ ﭘﺲ از رﺳﻢ ﺗﻤﺎﻣﯽ دواﯾﺮ، ﺗﻤﺎﻣﯽ ﻧﻘﺎط ﺗﻮﺳﻂ ﺣﺪاﻗﻞ ﯾﮏ داﯾﺮﻩ ﭘﻮﺷﯿﺪﻩ ﺑﺸﻮﻧﺪ.

ﺗﻮﺟﻪ: در ﺗﻤﺎﻣﯽ ﻗﺴﻤﺖ‌ها ﻋﺪد  را ٣ ﺑﮕﯿﺮﯾﺪ. ﺗﻮﺟﻪ ﮐﻨﯿﺪ ﮐﻪ ﻣﯽﺧﻮاهیم «ﺗﻌﺪاد» داﯾﺮﻩها ﮐﻤﯿﻨﻪ ﺑﺎﺷﺪ و ﻧﻪ ﻣﺴﺎﺣﺖ؛ اﻣﺎ ﺷﻤﺎ ﺑﺎﯾﺪ در ﺧﺮوﺟﯽ هر ﺳﻪ ﻗﺴﻤﺖ ﺣﺎﺻﻞﺟﻤﻊ ﻣﺴﺎﺣﺖهای ﺗﮏ ﺗﮏ اﯾﻦ داﯾﺮﻩهای ﺑﻬﯿﻨﻪ را ﺑﻨﻮﯾﺴﯿﺪ. اﮔﺮ ﺑﻪ دو ﯾﺎ ﭼﻨﺪ ﺣﺎﻟﺖ ﻣﯽﺗﻮان ﺑﺎ ﺗﻌﺪاد ﮐﻤﯿﻨﻪ داﯾﺮﻩ ﮐﻞ ﻧﻘﺎط را ﭘﻮﺷﺎﻧﺪ (ﺣﺎﻟﺖ ﺗﺴﺎوی از ﻧﻈﺮ ﺗﻌﺪاد دواﯾﺮ)، ﺣﺎﻟﺘﯽ ﮐﻪ ﻣﺠﻤﻮع ﻣﺴﺎﺣﺖها کم‌تر اﺳﺖ ﻣﻄﻠﻮب هستند. دﻗﺖ ﮐﻨﯿﺪ ﮐﻪ از ﻧﻘﻄﻪای ﺧﺎرج از اﯾﻦ ﻣﺤﺪودﻩ (ﻣﺜﻞ 1+$\Delta^2$) ﻣﺠﺎز ﺑﻪ رﺳﻢ داﯾﺮﻩ ﻧﯿﺴﺘﯿﻢ، اﻣﺎ داﯾﺮﻩهاﯾﯽ ﮐﻪ ﻣﯽﮐﺸﯿﻢ ﻣﺠﺎز هستند ﺧﺎرج از اﯾﻦ ﻣﺤﺪودﻩ هم ﺑﺮوﻧﺪ.

اﻟﻒ): در اﯾﻦ ﻗﺴﻤﺖ ﺑﺪون ﻣﺤﺪودﯾﺖ اﺿﺎﻓﻪای ﺷﻨﮕﻮل ﻣﯽﺧﻮاهد ﺳﺎﯾﺰ ﻣﺠﻤﻮﻋﻪی $Q$ (ﺗﻌﺪاد دواﯾﺮی ﮐﻪ رﺳﻢ ﻣﯽﺷﻮﻧﺪ) ﮐﻤﯿﻨﻪ ﺑﺸﻮد. در اﯾﻦ ﺣﺎﻟﺖ اﮔﺮ ﻣﺠﻤﻮع ﻣﺴﺎﺣﺖهای اﯾﻦ کم‌ترین ﺗﻌﺪاد داﯾﺮﻩ ${S_1}$ ﺑﺎﺷﺪ، ﺑﺎﻗﯽﻣﺎﻧﺪﻩی ﺗﻘﺴﯿﻢ ${S_1}$ ﺑﺮ $\Delta$ ﭼﻨﺪ اﺳﺖ؟

ب): اﮐﻨﻮن ﻓﺮض ﮐﻨﯿﺪ ﺷﻨﮕﻮل اﺟﺎزﻩی رﺳﻢ داﯾﺮﻩ ﺑﻪ ﻣﺮﮐﺰﯾﺖ اﻋﺪادی ﮐﻪ ﺧﻮدﺷﺎن ﺗﻮان دو هستند (ﻧﻈﯿﺮ ٢،١، ٤ ،۱۶،٨ و …) را ﻧﺪارد. ﻣﯽﺗﻮان ﻧﺸﺎن داد ﮐﻪ ﺑﺎ اﯾﻦ ﺗﻔﺴﯿﺮ ﻧﻘﻄﻪی ١ هرﮔﺰ ﭘﻮﺷﯿﺪﻩ ﻧﻤﯽﺷﻮد. ﺣﺎل اﮔﺮ ﻣﺠﻤﻮع ﻣﺴﺎﺣﺖ کم‌ترین ﺗﻌﺪاد داﯾﺮﻩ ﺑﺮای ﭘﻮﺷﺎﻧﺪن ﻧﻘﺎط ٢ ﺗﺎ $\Delta^2$ ﺑﺮاﺑﺮ ﺑﺎ ${S_2}$ ﺑﺎﺷﺪ، ﺑﺎﻗﯽﻣﺎﻧﺪﻩی ﺗﻘﺴﯿﻢ ${S_2}$ ﺑﺮ $\Delta$ ﭼﻨﺪ اﺳﺖ؟

ج): اﮐﻨﻮن ﻓﺮض ﮐﻨﯿﺪ ﺷﻨﮕﻮل ﻣﺠﺪداً اﺟﺎزﻩی رﺳﻢ داﯾﺮﻩ از ﺗﻤﺎم ﻧﻘﺎط را دارد. اﻣﺎ اﯾﻦﺑﺎر دواﯾﺮ ﻧﺒﺎﯾﺪ ﺟﺰ روی ﻣﺮزهاﯾﺸﺎن ﺑﺎ هم ﺗﻼﻗﯽ ﯾﺎ همﭘﻮﺷﺎﻧﯽ داﺷﺘﻪ ﺑﺎﺷﻨﺪ. ﺑﺮای ﻣﺜﺎل ﻧﻤﯽ ﺗﻮان از ١٢ و ٨ هم‌زﻣﺎن داﯾﺮﻩ رﺳﻢ ﮐﺮد، اﻣﺎ ﻣﯽﺗﻮان از ١٢ و ١٨ هم‌زﻣﺎن داﯾﺮﻩ ﮐﺸﯿﺪ ﺗﺎ ﺑﺎ هم ﻧﻘﺎط ٨ اﻟﯽ ٢٠ (ﺑﺎزﻩی ﺑﺴﺘﻪ) را ﺑﭙﻮﺷﺎﻧﻨﺪ. ﯾﺎ ﻣﯽﺗﻮان ﺑﺎ ﮐﺸﯿﺪن دو داﯾﺮﻩ ﺑﻪ ﻣﺮﮐﺰﯾﺖ ٨ و ٢٤ ﮐﻠﯿﻪ ﻧﻘﺎط کوچک‌تر ﯾﺎ ﻣﺴﺎوی ٣٢ را ﭘﻮﺷﺎﻧﺪ. در اﯾﻦ ﺣﺎﻟﺖ اﮔﺮ ﻣﺠﻤﻮع ﻣﺴﺎﺣﺖهای اﯾﻦ کم‌ترین ﺗﻌﺪاد داﯾﺮﻩ ${S_3}$ ﺑﺎﺷﺪ، ﺑﺎﻗﯽﻣﺎﻧﺪﻩی ﺗﻘﺴﯿﻢ ${S_3}$ ﺑﺮ $\Delta$ ﭼﻨﺪ اﺳﺖ؟


ابزار صفحه