المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۲:عملی مقدماتی دوم:سوال ۲

منشور

هفت هزار سال پیش پادشاه کشور توت‌فرنگی‌ها دستور ساخت منشورِ حقوق توت‌فرنگی‌ها را داد. این منشور، شرحی از وقایع حکومت پاد‌شاه کشور توت‌فرنگی‌ها و دستورات وی بود که بر روی لوحی از گل پخته‌ نوشته شده ‌بود. متأسفانه در طی این هفت‌هزار سال کشور توت‌فرنگی‌ها به مدت یک قرن مورد حمله‌ی گروهی از شته‌های متجاوز و ویران‌گر قرار گرفت‎.

شته‌ها در این یک قرن به هیچ چیزی رحم نکردند و کشور توت‌فرنگی‌ها را به یک ویرانه تبدیل کردند. با توجه به این که منشور خیلی مقاوم ساخته‌شده بود، شته‌ها نتوانستند آسیب زیادی به آن برسانند. تنها آسیبی که می‌شد به منشور وارد کرد ایجاد تغییراتی در متن آن بود. متنِ منشور رشته‌ای از حروف کوچک لاتینِ بدون فاصله می‌باشد. هر تغییر در متن منشور یا عوض کردن یک حرف از آن است، یا اضافه کردن یک حرف در جایی از متن و یا حذف یک حرف از آن. ‎ پس از اعمال یک تغییر، ممکن است طول رشته‌ی منشور کم یا زیاد شود. به دلیل استحکام زیاد منشور، شته‌ها برای ایجاد یک تغییر نیاز به یک سال زمان داشتند. پس می‌دانیم که متن منشور دستِ‌بالا ‎$100$‎ بار تغییر کرده است. باستان‌شناسان اخیراً متن اصلی منشور را به دست آورده‌اند. آن‌ها به شما متنی که پس از حمله‌ی شته‌ها بر روی منشور نوشته شده است و متن اصلی منشور را می‌دهند و از شما می‌خواهند برنامه‌ای بنویسید که با دریافت این دو متن حساب کند منشور دست کم چند بار در طول حمله‌ی شته‌ها تغییر داده شده است.

ورودی

  • در سطر اول ورودی متن تغییر یافته‌ی منشور به صورت دنباله‌ای از حروف کوچک لاتین آمده است‎.‎
  • در سطر دوم نیز متن اصلی منشور به همین شکل آمده است.
  • طول متن تغییر‌ یافته‌ی منشور و متن اصلی منشور از ‎$2 \times 10^5$‎ حرف بیشتر نیست‎.

خروجی

در یک خط کم‌ترین میزان تغییراتی که شته‌ها در متن منشور اعمال کرده‌اند را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
kitten
sitting
3

ابزار صفحه