المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۵۰

Expression

به شما ‎$n$‎ عدد ‎$a_1$‎ تا ‎$a_n$‎ و ‎$m$‎ عدد ‎$b_1$‎ تا ‎$b_m$‎ داده شده است ، شما باید یک عبارت ریاضی از کاراکترهای ‎'0'‎ ، ‎'1'، ‎'(' ‎،')'‎ ، ‎'=' ، '*'‎ ، ‎'+'‎ و ‎'-'‎ چاپ کنید که در مبناهای ‎$a_1$‎ تا ‎$a_n$‎ برقرار باشد و در مبناهای ‎$b_1$‎ تا ‎$b_m$‎ برقرار نباشد.‎

ورودی

  • در سطر اول ورودی، دو عدد ‎$1 \leq n \leq 9$‎ و ‎$1 \leq m \leq 9$‎ آمده‌اند.‎
  • در دو سطر بعد اعداد ‎$a_1$‎ تا ‎$a_n$‎ و ‎$b_1$‎ تا ‎$b_m$‎ آمده اند.‎
  • ‎$n+m$‎ کمتر یا مساوی $9$‎ است و تمام اعداد ‎$a_i$‎ و ‎$b_i$‎ بین ‎$2$‎ تا ‎$10$‎ هستند. ورودی طوری طراحی شده که حتماً سوال دارای جواب باشد.

خروجی

در تنها سطر خروجی پاسخ سوال را چاپ نمایید. ‎white space‎ها در خروجی نادیده گرفته می‌شوند‎.‎ تعداد کاراکترهای خروجی باید کم‌تر از ‎$1000$‎ باشد و دقیقاً یکی از کاراکترهای خروجی باید برابر یا ‎'='‎ باشد. ‎

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
1 1
2
3
‎1+1=10‎

پاسخ

یک عبارت معتبر را در نظر بگیرید. می‌توان فرض کرد که در این عبارت هر عدد متشکل از یک ‎$1$‎ و تعدادی ‎$0$‎ جلوی آن است. (یعنی به شکل ‎$0 \cdots 10$)‎ چون در غیر این صورت هر عدد را می‌توان به صورت جمع یکسری از عدد به شکل مورد نظر نوشت.(مثلا ‎$1010 = 1000‎ + ‎10$.) در این عبارت اگر یک ‎$1$‎ تنها آمده باشد در هر مبنایی که در نظر بگیریم همان مقدار یک را دارد. اما اگر یک ‎$1$‎ به همراه ‎$n$‎ صفر جلوی آن داشته باشیم، این عدد در مبنای ‎$b$‎ مقدار ‎$b^n$‎ خواهد داشت. حالا عبارت معتبر مورد نظر را می‌توان با باز کردن تمام پرانتز‌ها و بردن تمام جملات به یک طرف، یک سمت را تبدیل به یک چند جمله‌ای کرد که متغییر آن همان مبنایی است که با آن کار می‌کنیم و طرف دیگر صفر باشد. حالا زمانی عبارت مورد نظر برقرار می‌شود که مبنای‌مان ریشه‌ی چند جمله‌ای باشد. در واقع برعکس این گزاره هم درست است یعنی به ازای یک مبنا عبارت برقرار است اگر و تنها اگر آن مبنا ریشه‌ی چند جمله‌ای باشد. پس کافی است ما یک چند جمله‌ای درست کنیم که ریشه هایش ‎$a_1$‎ تا ‎$a_n$‎ باشند. که این هم به شکل زیر می شود‎:‎ ‎$$(x-a_1 ) \times (x-a_2 )\cdots(x-a_n )=0$$‎ پس عبارت مورد نظر آن به شکل ‎$(10 – 1 – 1‎ - ‎\cdots‎ -‎1) (10 – 1-1 – \cdots‎ -‎1)\cdots (10 – 1 – 1‎ -‎\cdots-1) = 0$ می شود که تعداد منفی یک‌ها در پرانتز ‎$i$‎ ام برابر با ‎$a_i$‎ است. با توجه به توضیحات بالا واضح است که این عبارت فقط در مبناهای‎$a_1$‎ تا ‎$a_n$‎ برقرار است. و در ضمن طولش از ‎$1000$‎ کاراکتر کمتر است. (حداکثر ‎$9$‎ پرانتز خواهیم داشت که هر کدام حداکثر ‎$24$‎ کاراکتر هستند‎.(‎ ‎‎


ابزار صفحه