رمز قصير
Problem
يحتوي كود إيفان على متغيرات n. لكل متغير اسم فريد يتكون فقط من أحرف إنجليزية صغيرة (صغيرة). ذات يوم قرر إيفان تقصير رمزه.
إنه يريد استبدال اسم كل متغير ببادته غير الفارغة بحيث تظل الأسماء الجديدة مميزة بشكل زوجي (لكن الاسم الجديد لبعض المتغيرات قد يكون هو نفسه الاسم القديم لهذا المتغير أو متغير آخر). من بين كل هذه البدائل الممكنة ، يريد العثور على واحد يكون الطول الإجمالي لأسماء المتغيرات فيه ضئيلاً.
السلسلة a هي بادئة من السلسلة b إذا كان بإمكانك إزالة بعض الأحرف (ربما لا شيء) من نهاية السلسلة b والحصول على a.
أوجد الحد الأدنى للطول الإجمالي المحتمل للأسماء الجديدة.
الإدخال:
يحتوي السطر الأول على عدد صحيح واحد n (1 & le؛ n & le؛ 10 5 ) & mdash؛ عدد المتغيرات في كود إيفان.
تحتوي الأسطر n التالية على أسماء متغيرة ، واحد لكل سطر. كل اسم ليس سلسلة فارغة ويحتوي فقط على أحرف إنجليزية صغيرة (صغيرة). الطول الإجمالي لكل هذه السلاسل لا يزيد عن 10 5 . جميع أسماء المتغيرات مختلفة.
الإخراج:
طباعة عدد صحيح واحد و [مدش] ؛ أقل طول إجمالي ممكن لأسماء المتغيرات الجديدة.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
3
كود |
6 |
5
أبا
ABB
أب
أأ
aacada |
11 |
3
برقية
الرقمية
المقاومة |
3 |
التفسيرات:
في المثال الأول ، سيكون أحد أفضل الخيارات هو تقصير الأسماء بالترتيب الذي تم إدخالها به إلى "cod" و "co" و "c".
في المثال الثاني ، يمكنك تقصير الاسم الأخير إلى "aac" والاسم الأول قبل & quot؛ a & quot؛ دون تغيير أسماء المتغيرات الأخرى.