- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۶۴ مگابایت
یک دستگاه خودپرداز داریم که روی آن ۱۰ دکمه برای وارد کردن هر رقم و یک دکمه برای پاک کردن سمت راستترین رقم عدد وارد شده، وجود دارد.
میخواهیم با این دستگاه، عدد \(n\) را وارد کنیم. اما میدانیم ۱۰ دکمه ارقام این دستگاه خراب است ولی دکمه پاک کردن، به درستی کار میکند.
ما مشکل دستگاه را فهمیدهایم و میدانیم اگر دکمه رقم \(d\) وارد شود، رشته \(s_d\) (به همان ترتیب) وارد دستگاه میشود. همچنین مطمئن هستیم که رقم اول رشته \(s_d\) خود \(d\) است. ممکن است \(s_d\) شامل رقم تکراری باشد.
حال از شما میخواهیم کمترین تعداد فشار دادن دکمهها که برای وارد کردن عدد \(n\) لازم است را محاسبه کنید.
ورودی
در سطر اول ورودی عدد صحیح و مثبت \(n\) داده میشود. \[1 \leq n \leq 10^{1000}\] در ۱۰ سطر بعدی در سطر \(d\)ام رشته \(s_d\) آمده است. \[ 1 \leq |s_d| \leq 10\] تضمین میشود که رقم اول \(s_d\) خود \(d\) است ولی ممکن است \(s_d\) رقم تکراری داشته باشد.
خروجی
در تنها سطر خروجی، کمینه تعداد عملیات لازم برای وارد کردن عدد \(n\) را بنویسید.
مثالها
ورودی نمونه ۱
140102
0
1
2
3
4
5
6
7
8
9
خروجی نمونه ۱
6
توضیح نمونه ۱
دستگاه خودپرداز بالا سالم است. یعنی با فشار دادن دکمه هر رقم، فقط همان رقم نوشته میشود؛ پس کافی است برای نوشتن عدد \(140102\) به صورت زیر عمل کنیم.
- عملیات اول. قبل از انجام این عملیات، هیچ رقمی وارد دستگاه نشده است، پس با فشار دادن دکمه
1، عدد \(1\) وارد دستگاه میشود. - عملیات دوم. تا قبل از این عملیات عدد \(1\)، وارد شده است. در این عملیات با فشار دادن دکمه
4، عدد \(14\) وارد دستگاه میشود. - عملیات سوم. تا قبل از این عملیات عدد \(14\)، وارد شده است. در این عملیات با فشار دادن دکمه
0، عدد \(140\) وارد دستگاه میشود. - عملیات چهارم. تا قبل از این عملیات عدد \(140\)، وارد شده است. در این عملیات با فشار دادن دکمه
1، عدد \(1401\) وارد دستگاه میشود. - عملیات پنجم. تا قبل از این عملیات عدد \(1401\)، وارد شده است. در این عملیات با فشار دادن دکمه
0، عدد \(14010\) وارد دستگاه میشود. - عملیات ششم. تا قبل از این عملیات عدد \(14010\)، وارد شده است. در این عملیات با فشار دادن دکمه
2، عدد \(140102\) وارد دستگاه میشود.
ورودی نمونه ۲
18415
0
15
2
3
415
59
6
7
84
9
خروجی نمونه ۲
4
توضیح نمونه ۲
دستگاه فوق خراب است. برای وارد کردن عدد \(18415\) با کمترین تعداد عملیات میتوانیم به صورت زیر عمل کنیم.
- عملیات اول. قبل از انجام این عملیات، هیچ رقمی وارد دستگاه نشده است، پس با فشار دادن دکمه
1، عدد \(15\) وارد دستگاه میشود. - عملیات دوم. تا قبل از این عملیات عدد \(15\)، وارد شده است. در این عملیات با پاک کردن آخرین رقم، عدد وارد شده به \(1\) تغییر میکند.
- عملیات سوم. تا قبل از این عملیات عدد \(1\)، وارد شده است. در این عملیات با فشار دادن دکمه
8، عدد \(184\) وارد دستگاه میشود. - عملیات چهارم. تا قبل از این عملیات عدد \(184\)، وارد شده است. در این عملیات با فشار دادن دکمه
1، عدد \(18415\) وارد دستگاه میشود.
ورودی نمونه ۳
18415
0
16
2
3
415
59
6
7
84
9
خروجی نمونه ۳
5
توضیح نمونه ۳
دستگاه فوق خراب است. برای وارد کردن عدد \(18415\) با کمترین تعداد عملیات میتوانیم به صورت زیر عمل کنیم.
- عملیات اول. قبل از انجام این عملیات، هیچ رقمی وارد دستگاه نشده است، پس با فشار دادن دکمه
1، عدد \(16\) وارد دستگاه میشود. - عملیات دوم. تا قبل از این عملیات عدد \(16\)، وارد شده است. در این عملیات با پاک کردن آخرین رقم، عدد وارد شده به \(1\) تغییر میکند.
- عملیات سوم. تا قبل از این عملیات عدد \(1\)، وارد شده است. در این عملیات با فشار دادن دکمه
8، عدد \(184\) وارد دستگاه میشود. - عملیات چهارم. تا قبل از این عملیات عدد \(184\)، وارد شده است. در این عملیات با پاک کردن آخرین رقم، عدد وارد شده به \(18\) تغییر میکند.
- عملیات پنجم. تا قبل از این عملیات عدد \(184\)، وارد شده است. در این عملیات با فشار دادن دکمه
4، عدد \(18415\) وارد دستگاه میشود.