المپدیا

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

ابزار کاربر

ابزار سایت


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

Binary Numbers

دو رشته از حروف ‎'a'‎ تا ‎'z'‎ و ‎'0'‎ و ‎'1'‎ به طول یکسان به شما داده شده است. شما باید به جای حروف ‎'a'‎ تا ‎'z'‎ طوری ارقام ‎'0'‎ و ‎'1'‎ را جای‌گزین کنید که اختلاف دو عدد در مبنای دو کمینه شود.‎

ورودی

  • در سطر اول ورودی، دو رشته با انداره برابر از حروف ‎'a'‎ تا 'z' و ‎'0'‎ و ‎'1'‎ آمده است.
  • تعداد حروف هر رشته حداکثر برابر ‎$60$‎ است.‎

خروجی

در تنها سطر خروجی کم‌ترین اختلاف ممکن بین دو عدد را بنویسید. ‎

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
aaa
bbb
0
101
aaa
2
10ab
ab01
1

پاسخ

هر کدام از رشته ها را می‌توان به صورت ضریبی از اعداد و متغیر ها نوشت، برای مثال‎: ‎

$$'a1a0b' = b+20\times a+8$$

پس می‌توان اختلاف بین دو عدد را هم به صورت یک عبارت بر حسب متغیرهای ‎'a'‎ تا 'z'‎ و اعداد نوشت. حال اگر اولین رقم ( از سمت چپ ) که این دو عدد در آن اختلاف دارند را مشخص کنیم، با در نظر گرفتن معادلاتی به صورت 'a'='b'‎ یا ‎'a'=0‎ که از این فرض به‌دست می آیند می‌توانیم به صورت حریصانه Greedy-algorithm‎ طوری اعداد ‎0‎ و ‎1‎ را به متغیرهای نسبت بدهیم که عدد کم‌تر را به عدد بیش‌تر نزدیک کنیم. پس کافیست از میان تمام فرض های ممکن حالتی که اختلاف دو عدد را کمینه می‌کند را به‌دست بیاوریم‎.‎

راه حل دوم‎:

اگر اختلاف بین دو عدد را به صورت عبارتی بر حسب اعداد و متغیرهای ‎'a'‎ تا ‎'z'‎ بنویسیم، می‌توانیم با چک کردن ‎$2^{26}$‎ حالت نسبت دادن اعداد ‎0‎ و ‎1‎ به متغیرها مقدار کمینه را‌به‌دست‌آوریم.زمان‌اجرای‌این الگوریتم زیاد است و نمی‌توان با استفاده از آن سوال را در زمان مناسب حل کرد اما اگر متغیرها را به دو دسته ‎'a'‎ تا ‎'l'‎ و'm'‎ تا 'z'‎ تقیسم کنیم‌و به ازای هر دسته، تمام مقادیر به‌دست آمده‌از نسبت دادن‌اعداد ‎$0$‎ و ‎$1$‎ به متغیرها در عبارت را در یک ‎Binary-search-tree ‎ ذخیره کنیم، می‌توانیم به ازای هر حالت از یک‌دسته، حالتی از دسته دیگر که باعث می‌شود اختلاف دو عدد کمینه شود را در زمان لگاریتمی به‌دست آوریم.

با استفاده از این روش که ‎bidirectional backtracking نام دارد، می‌توان جواب سوال را در زمان‎$o(2^{13} \times‎ ‎log(2^{13}))$‎ به‌دست آورد.


ابزار صفحه