+ محدودیت زمان: ۳.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مانی که به تازگی تایپ ده‌انگشتی یاد گرفته است، سخت به دنبال این است که سرعت تایپ خودش را بالا ببرد! اما از آنجا که مانی همیشه می‌خواهد خاص باشد، تصمیم گرفت که به جای اینکه تمرین بیشتری کند، ساختار کیبورد خود را عوض کند! کیبورد مانی به شکل یک جدول **$3 \times 10$** است که ستون‌های آن از چپ به راست و همچنین سطرهای آن از بالا به پایین شماره‌گذاری شده‌اند. همچنین او $n$ کلمه در لیست تمرین خود دارد که قصد تایپ کردنشان را دارد. برای این کار، او می‌خواهد که **۳۰** کلیدی که بر روی کیبورد خود قرار دارد را در این جدول طوری بچیند که بیشترین سرعت تایپ را کسب کند. مانی که برای اینکار، نیاز به معیاری برای مقایسه‌ی بین کیبوردها داشت، تصمیم گرفت که به هر چینش از کلیدها، عددی را نسبت دهد. او ابتدا برای هر کلمه، امتیازی در نظر گرفت که آن را به صورت زیر تعریف کرد: برای هر کلمه‌ی به شکل $s_{1}s_{2}...s_{k}$ که در آن $s_{i}$ نشان‌دهنده‌ی حرف $i$اُم در آن است، **امتیاز آن کلمه** برابر با مقدار زیر است: $$\sum_{i=1}^{k-1}difference\left(s_{i},\,s_{i+1}\right)$$ که در آن، تابع $difference$، **اختلاف شماره ستون** دو حرف ورودی را بر می‌گرداند. همچنین، او برای یک ترتیب از قرارگیری کلیدها در کیبورد نیز یک عدد در نظر می‌گیرد و آن را **امتیاز کیبورد** می‌نامد. این عدد برابر است با **مجموع امتیاز $n$ کلمه‌ی موجود** در لیست تمرین. مانی که تصمیم داشت کیبورد با بیشترین امتیاز را به دست آورد، از شما می‌خواهد که برای او، کیبوردی با بیشینه امتیاز را پیدا کنید. اما از آنجا که مانی می‌داند سؤال به اندازه‌ی کافی سخت است، تصمیم گرفت که در ازای پیدا کردن کیبوردی با امتیاز بیشتر، نمره‌ی بیشتری به شما دهد! (در نتیجه در این سؤال به دنبال پیدا کردن کیبورد با بیشترین امتیاز نیستیم و هر چقدر راه‌حل شما، کیبورد با امتیاز بیشتری پیدا کند، امتیاز بیشتری از این سؤال دریافت خواهید کرد) # ورودی در خط اول ورودی عدد طبیعی $n$ آمده است و در $n$ خط بعدی و در هر خط یک کلمه آمده است که نشان‌دهنده‌ی کلمه‌های موجود در لیست تمرین مانی است. $$1 \le n \le 5\ 000$$ **تضمین می‌شود طول هر کلمه از ۱۰ بیشتر نیست و همچنین تمام کلمه‌ها، تنها شامل حروف کوچک انگلیسی و ارقام ۱ تا ۴ هستند.** # خروجی در خط اول خروجی، ابتدا بیشترین امتیاز کیبورد را چاپ کنید و سپس در سه خط بعدی و در هر خط، ۱۰ کارکتر که با فاصله از هم جدا شده‌اند چاپ کنید. این کارکترها نشان‌دهنده‌ی کلیدهای کیبورد می‌باشند (برای درک بهتر نحوه‌ی خروجی دادن، خروجی‌های نمونه را مشاهده کنید). **در کیبورد خروجی، تمام حروف کوچک انگلیسی و همچنین ارقام ۱ تا ۴، باید دقیقاً یکبار ظاهر شوند.** ## ورودی نمونه ۱ ``` 2 ab t2 ``` ## خروجی نمونه ۱ ``` 18 t o 3 x r j z h n a b 1 f 4 w i k u y 2 d m p q c s l e g v ``` اختلاف شماره‌ی ستون دو کاراکتر $a$ و $b$ و همچنین دو کاراکتر $t$ و $2$ برابر با ۹ است و در نتیجه پاسخ برابر با ۱۸ است. (توجه کنید که کیبورد چاپ شده، تنها یکی از پاسخ‌های ممکن است) ## ورودی نمونه ۲ ``` 3 abc 123 f4r ``` ## خروجی نمونه ۲ ``` 51 2 r z t m l s g 3 c b i w q x p n y 1 a f e k h o j d v u 4 ```

حل سؤال در بانک سؤالات