Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

C. Symmetry Makes Perfect time limit per test. 1 second memory limit per test: 256 megabytes input: standard input output: standard output Yihan is shopping

image text in transcribed

C. Symmetry Makes Perfect time limit per test. 1 second memory limit per test: 256 megabytes input: standard input output: standard output Yihan is shopping for candies for her student again, and this time she wants something new. Because Yihan has spent a lot of money at the candy store, the owner of the store decided to give Yihan a candy string for free. A candy string is a string of candies (of course), each of a different flavor. There is one candy string that was made up by the salesman already in the store. There are also bulks of single candies of each flavor (say, an infinite number for each). The price for different flavor is also different. Suppose the price of flavor x is p[x]. Yihan likes the idea of candy string. However, she doesn't like the particular candy string in the store, because it is not symmetric. For example, if there are four flavors a,b,c and d, a candy string of abcdcba or aabbaa is symmetric, while abcdabcd or aaab is not. Yihan wants to DIY a new candy string based on the current candy string she has. However she was told that, she need to pay for the extra cost to make it symmetric. Well, she is OK with that because she just cannot tolerate it to be asymmetric. In particular, she will insert some candies into the candy string to make it symmetric. To inserting a candy with a certain flavor anywhere in the candy string, Yihan has to pay the price of the inserted flavor. That is, Yihan has to buy that new candy and add it to the candy string. Yihan won't delete or replace any candy from the string since it's already free, and she's greedy. Yihan wants to know how much she needs to pay at least to make the candy string symmetric. Input The first line contains two numbers n(1n103) and k(1k26), and 1p[x]103. n is the length of the candy string, k is the number of flavors. Only, first k letters would appear in string input and you can only use the first k in making the symmetry. The next k lines are the prices for each flavor. The (i+1)-th line is the price for flavor ip[x](1p[x]1000), p[x] is the value of alphabet x. In the next line there are n characters, which is the initial flavor of candies in the candy string. Suppose there are in total 26 flavors, denoted as lowercase letters ' a ' to ' z '. The flavors are ordered alphabetically. Only the first k letters will appear in this string. Output The output contains only one number, which is the lowest price Yihan needs to pay to make the candy string symmetric

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

MongoDB Applied Design Patterns Practical Use Cases With The Leading NoSQL Database

Authors: Rick Copeland

1st Edition

1449340040, 978-1449340049

More Books

Students also viewed these Databases questions

Question

What is the principle of corresponding states?

Answered: 1 week ago

Question

Plot all the points on the same axes. (0, -1)

Answered: 1 week ago

Question

Describe ERP and how it can create efficiency within a business

Answered: 1 week ago

Question

Writing a Strong Introduction

Answered: 1 week ago