مسابقه الگوریتمی شماره ۴۴ (آموزشی) + راه‌حل‌ها
سلام!
مسابقه‌ی الگوریتمی شماره‌ی ۴۴، یک مسابقه آموزشی هست که با هدف تمرین و یادگیری بیشتر برای شما طراحی شده.
- این مسابقه شامل ۵ سؤال الگوریتمی هست.
- حل سؤالات این مسابقه بر روی امتیاز کوئرایی شما تأثیر نداره.
- زمان برگزاری مسابقه، سه‌شنبه ۷ تیر ساعت ۲۰ هست و شما ۲ ساعت زمان دارید تا به سؤالات پاسخ بدید.
- ثبت‌نام این مسابقه در صفحه مسابقه الگوریتمی شماره ۴۴ انجام می‌شه و تا ۷ام تیر برای ثبت‌نام فرصت دارید.
راه‌حل‌های این مسابقه، بلافاصله بعد از پایان مسابقه در همین پست منتشر می‌شن و شما میتونید از اون‌ها برای حل سؤالات مسابقه در بانک سؤالات استفاده کنید.
پی‌نوشت: راه‌حل‌های مسابقه
معادله خط
اگر مقدار a ناصفر باشد، معادله جواب یکتا دارد (x = \frac{-b}{a}). اما اگر مقدار a برابر صفر باشد، در صورتی که b ناصفر باشد، معادله هیچ جوابی ندارد و در غیر این صورت (یعنی a و b هر دو صفر باشند) این معادله بی‌شمار جواب دارد.
مساحت پیچیده
راه‌حل اول
همان طور که انتظار می‌رود، راه‌حل اولیه‌ی این سؤال کمی پیچیده است. بیاید مساحت قسمت‌های مختلف را حساب کرده و قدم‌به‌قدم به جواب نزدیک شویم.
ناحیه‌ی سبز یک قطاع ۶۰ درجه از دایره‌ای به شعاع a است. بنابراین مساحت ناحیه‌ی سبز برابر است با:
\frac{60}{360} \pi a^2 = \frac{\pi}{6} a^2
ناحیه‌ی بنفش یک مثلث متساوی‌الاضلاع به ضلع a است. بنابراین مساحت ناحیه‌ی بنفش برابر است با:
\frac{\sqrt{3}}{4} a^2
ناحیه‌ی گنبدی شکل از دو برابر جمع ناحیه‌ی سبزرنگ منهای ناحیه‌ی بنفش بدست می‌آید. بنابراین مساحت این ناحیه برابر است با:
2(\frac{1}{6} \pi a^2) - \frac{\sqrt{3}}{4} a^2 = (\frac{\pi}{3} - \frac{\sqrt{3}}{4}) a^2
ناحیه‌ی صورتی یک قطاع ۹۰ درجه از دایره‌ای به شعاع a است و مساحت آن برابر است با:
\frac{90}{360} \pi a^2 = \frac{\pi}{4} a^2
ناحیه‌ی زردرنگ را می‌توان مربعی در نظر گرفت که مساحت دو قطاع ۹۰ درجه از آن کم و مساحت یک گنبد به آن اضافه شده است. بنابراین مساحت این نوار زرد برابر است با:
a^2 - 2(\frac{\pi}{4} a^2) + (\frac{\pi}{3} - \frac{\sqrt{3}}{4}) a^2 =
\\
(1 - \frac{\pi}{2} + \frac{\pi}{3} - \frac{\sqrt{3}}{4}) a^2 =
\\
(1 - \frac{\pi}{6} - \frac{\sqrt{3}}{4})a^2
ناحیه‌ی نارنجی را می‌توان به صورت یک مربع در نظر گرفت که مساحت یک قطاع ۹۰ درجه از دایره و دو ناحیه‌ی زردرنگ از آن کم شده است. بنابراین مساحت این ناحیه برابر است با:
a^2 - \frac{\pi}{4}a^2 - 2 (1 - \frac{\pi}{6} - \frac{\sqrt{3}}{4})a^2 =
\\
(1 - \frac{\pi}{4} - 2 + \frac{\pi}{3} + \frac{\sqrt{3}}{2}) a^2 =
\\
(-1 + \frac{\pi}{12} + \frac{\sqrt{3}}{2}) a^2
حال مساحت ناحیه‌ی خواسته‌شده در سؤال یک مربع است که ۴ ناحیه‌ی نارنجی‌رنگ و ۴ ناحیه‌ی زردرنگ از آن کم شده است. بنابراین پاسخ مسئله برابر است با:
a^2 - 4(-1 + \frac{\pi}{12} + \frac{\sqrt{3}}{2}) a^2 - 4(1 - \frac{\pi}{6} - \frac{\sqrt{3}}{4})a^2 =
\\
(1 + 4 -\frac{\pi}{3} - 2\sqrt{3} - 4 + \frac{2\pi}{3} + \sqrt{3})a^2 =
\\
(1 + \frac{\pi}{3} - \sqrt{3})a^2
راه‌حل دوم
مساحت ناحیه‌ی حساب‌شده در ورودی نمونه‌ی اول برای مربعی به ضلع ۱ داده شده است. برای اینکه جواب را برای مربعی به ضلع a حساب کنیم، کافی است جواب ورودی نمونه‌ی اول را در a^2 ضرب کنیم.
توجه کنید سیستم داوری انتظار دارد جواب شما تا ۶ رقم بعد از اعشار درست باشد. باتوجه به خطای گردکردن اعداد و محدودیت a، باید حداقل جواب نمونه‌ی اول را تا دقت ۶ + ۴ + ۱ = ۱۱ رقم بردارید.
سینوس طبیعی
راه‌حل اول
بعد از ورودی گرفتن k، با ایجاد یک حلقه به‌راحتی می‌توانید مقدار n مطلوب را پیدا کنید.
راه‌حل دوم
عدد n = 208341 به اندازه‌ی کافی کوچک (کمتر از \frac{1}{100000}) است. پس می‌توانید همین عدد را چاپ کنید.
اتومورفیک
راه‌حل اول
عدد k رقمیِ a اتومورفیک است اگر و تنها اگر:
10^k | a(a - 1)
به همین دلیل می‌توان تشخیص داد که a یا a - 1 باید تعداد زیادی عامل ۵ داشته باشد.
با همین استدلال می‌توان ۳۶ عدد اتومورفیکِ اول را شناسایی و ذخیره کرد.
راه‌حل دوم
این دنباله معروف است و می‌توانید آن را در این سایت پیدا کرده و ۳۶ جمله‌ی اول آن را چاپ کنید.
یک‌سازی
شرط لازم و کافی وجود چنین مضربی برای a این است که gcd(a, 10) برابر ۱ باشد. (یعنی عامل ۲ یا ۵ نداشته باشد)
اثبات اعداد زیر را در نظر بگیرید:
r_1 = 1 \\ r_2 = 11 \\ r_3 = 111 \\ \dots \\ r_a = 11\dots1 \\ \dots
اگر در یکی از اعداد r_1 تا r_a عددی مضرب a باشد، مسئله تمام می‌شود. اما اگر هیچ‌کدام مضرب a نباشند، دو عدد صحیح i و j چنان موجود است که:
i < j, \quad a \,|\, r_j - r_i = 10^i \times r_{j - i}اما چون می‌دانیم a نسبت به ۱۰ اول است داریم:
a | r_{j - i}
و این تناقض نشان می‌دهد که همواره چنین مضربی وجود دارد.
برای اعدادی مثل a که نسبت به ۱۰ اول نیستند هم می‌توان گفت که چنین مضربی ندارند؛ چون اگر a نسبت به ۱۰ اول نباشد، یا زوج است یا مضرب ۵ و این یعنی یکان آن نمی‌تواند ۱ باشد. پس چنین مضربی ندارد.
اگر به اثبات بالا توجه کنیم، متوجه می‌شویم که این مضرب برای a حداکثر aرقمی خواهد بود. بنابراین می‌توان همه‌ی اعدادی که ارقام آن‌ها از ۱ تولید شده‌اند را به پیمانه a حساب و عددی که باقی‌مانده آن بر a صفر است را پیدا کرده و بر a تقسیم کنیم تا جواب مسئله به دست آید.
