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

یک دستگاه خودپرداز داریم که روی آن ۱۰ دکمه برای وارد کردن هر رقم و یک دکمه برای پاک کردن سمت راست‌ترین رقم عدد وارد شده، وجود دارد.

می‌خواهیم با این دستگاه، عدد nn را وارد کنیم. اما می‌دانیم ۱۰ دکمه ارقام این دستگاه خراب است ولی دکمه پاک کردن، به درستی کار می‌کند.

توضیح تصویر

ما مشکل دستگاه را فهمیده‌ایم و می‌دانیم اگر دکمه رقم dd وارد شود، رشته sds_d (به همان ترتیب) وارد دستگاه می‌شود. همچنین مطمئن هستیم که رقم اول رشته sds_d خود dd است. ممکن است sds_d شامل رقم تکراری باشد.

حال از شما می‌خواهیم کمترین تعداد فشار دادن دکمه‌ها که برای وارد کردن عدد nn لازم است را محاسبه کنید.

ورودی

در سطر اول ورودی عدد صحیح و مثبت nn داده می‌شود. 1n1010001 \leq n \leq 10^{1000} در ۱۰ سطر بعدی در سطر ddام رشته sds_d آمده است. 1sd10 1 \leq |s_d| \leq 10 تضمین می‌شود که رقم اول sds_d خود dd است ولی ممکن است sds_d رقم تکراری داشته باشد.

خروجی

در تنها سطر خروجی، کمینه تعداد عملیات لازم برای وارد کردن عدد nn را بنویسید.

مثال‌ها


ورودی نمونه ۱

140102
0
1
2
3
4
5
6
7
8
9
Plain text

خروجی نمونه ۱

6
Plain text

توضیح نمونه ۱

دستگاه خودپرداز بالا سالم است. یعنی با فشار دادن دکمه هر رقم، فقط همان رقم نوشته می‌شود؛ پس کافی است برای نوشتن عدد 140102140102 به صورت زیر عمل کنیم.

  • عملیات اول. قبل از انجام این عملیات، هیچ رقمی وارد دستگاه نشده است، پس با فشار دادن دکمه ‍‍1، عدد 11 وارد دستگاه می‌شود.
  • عملیات دوم. تا قبل از این عملیات عدد 11، وارد شده است. در این عملیات با فشار دادن دکمه 4، عدد 1414 وارد دستگاه می‌شود.
  • عملیات سوم. تا قبل از این عملیات عدد 1414، وارد شده است. در این عملیات با فشار دادن دکمه 0، عدد 140140 وارد دستگاه می‌شود.
  • عملیات چهارم. تا قبل از این عملیات عدد 140140، وارد شده است. در این عملیات با فشار دادن دکمه 1، عدد 14011401 وارد دستگاه می‌شود.
  • عملیات پنجم. تا قبل از این عملیات عدد 14011401، وارد شده است. در این عملیات با فشار دادن دکمه 0، عدد 1401014010 وارد دستگاه می‌شود.
  • عملیات ششم. تا قبل از این عملیات عدد 1401014010، وارد شده است. در این عملیات با فشار دادن دکمه 2، عدد 140102140102 وارد دستگاه می‌شود.

ورودی نمونه ۲

18415
0
15
2
3
415
59
6
7
84
9
Plain text

خروجی نمونه ۲

4
Plain text

توضیح نمونه ۲

دستگاه فوق خراب است. برای وارد کردن عدد 1841518415 با کمترین تعداد عملیات می‌توانیم به صورت زیر عمل کنیم.

  • عملیات اول. قبل از انجام این عملیات، هیچ رقمی وارد دستگاه نشده است، پس با فشار دادن دکمه ‍‍1، عدد 1515 وارد دستگاه می‌شود.
  • عملیات دوم. تا قبل از این عملیات عدد 1515، وارد شده است. در این عملیات با پاک کردن آخرین رقم، عدد وارد شده به 11 تغییر می‌کند.
  • عملیات سوم. تا قبل از این عملیات عدد 11، وارد شده است. در این عملیات با فشار دادن دکمه 8، عدد 184184 وارد دستگاه می‌شود.
  • عملیات چهارم. تا قبل از این عملیات عدد 184184، وارد شده است. در این عملیات با فشار دادن دکمه 1، عدد 1841518415 وارد دستگاه می‌شود.

ورودی نمونه ۳

18415
0
16
2
3
415
59
6
7
84
9
Plain text

خروجی نمونه ۳

5
Plain text

توضیح نمونه ۳

دستگاه فوق خراب است. برای وارد کردن عدد 1841518415 با کمترین تعداد عملیات می‌توانیم به صورت زیر عمل کنیم.

  • عملیات اول. قبل از انجام این عملیات، هیچ رقمی وارد دستگاه نشده است، پس با فشار دادن دکمه ‍‍1، عدد 1616 وارد دستگاه می‌شود.
  • عملیات دوم. تا قبل از این عملیات عدد 1616، وارد شده است. در این عملیات با پاک کردن آخرین رقم، عدد وارد شده به 11 تغییر می‌کند.
  • عملیات سوم. تا قبل از این عملیات عدد 11، وارد شده است. در این عملیات با فشار دادن دکمه 8، عدد 184184 وارد دستگاه می‌شود.
  • عملیات چهارم. تا قبل از این عملیات عدد 184184، وارد شده است. در این عملیات با پاک کردن آخرین رقم، عدد وارد شده به 1818 تغییر می‌کند.
  • عملیات پنجم. تا قبل از این عملیات عدد 184184، وارد شده است. در این عملیات با فشار دادن دکمه 4، عدد 1841518415 وارد دستگاه می‌شود.

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.