خانه توسعه‌دهنده با کوئرا | توسعه‌دهنده مسابقات و رویدادها مسابقه الگوریتمی شماره ۴۴ (آموزشی) + راه‌حل‌ها

مسابقه الگوریتمی شماره ۴۴ (آموزشی) + راه‌حل‌ها

۴ تیر ۱۴۰۱

زمان مطالعه: 4 دقیقه

1583

سلام!

مسابقه‌ی الگوریتمی شماره‌ی ۴۴، یک مسابقه آموزشی هست که با هدف تمرین و یادگیری بیشتر برای شما طراحی شده.

این مسابقه شامل ۵ سؤال الگوریتمی هست.
حل سؤالات این مسابقه بر روی امتیاز کوئرایی شما تأثیر نداره.
زمان برگزاری مسابقه، سه‌شنبه ۷ تیر ساعت ۲۰ هست و شما ۲ ساعت زمان دارید تا به سؤالات پاسخ بدید.
ثبت‌نام این مسابقه در صفحه مسابقه الگوریتمی شماره ۴۴ انجام می‌شه و تا ۷ام تیر برای ثبت‌نام فرصت دارید.

راه‌حل‌های این مسابقه، بلافاصله بعد از پایان مسابقه در همین پست منتشر می‌شن و شما می‌تونید از اون‌ها برای حل سؤالات مسابقه در بانک سؤالات استفاده کنید.

فهرست مطالب

پی‌نوشت: راه‌حل‌های مسابقه

معادله خط

اگر مقدار $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$ تقسیم کنیم تا جواب مسئله به دست آید.