- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۶۴ مگابایت
یک دستگاه خودپرداز داریم که روی آن ۱۰ دکمه برای وارد کردن هر رقم و یک دکمه برای پاک کردن سمت راست‌ترین رقم عدد وارد شده، وجود دارد.
می‌خواهیم با این دستگاه، عدد $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$ وارد دستگاه می‌شود.
ارسال پاسخ برای این سؤال