06 Apr Aurora Saturday 14:30 Python Practice 21.04.03.
Question:
Jack doesn’t like the new smart phones with full keypads and still uses the old keypads which require you to tap a key multiple times to type a single letter. For example, if the keyboard has two keys, one with the letters “adef” and the other one with the letters “zyx”, then typing ‘a’ requires one keystroke, typing ‘f’ requires four keystrokes, typing ‘y’ requires two keystrokes, and so on.
He recently moved to a new country where the language is such that his keypad is not the most efficient. In every language some characters occur more often than others. He wants to create a specific keyboard for this language that uses N different letters. He has a large body of text in this language, and has already analyzed it to find the frequencies of all N letters of its alphabet.
You are given an array ‘frequencies’ with N elements. Each element of frequencies is the number of times one of the letters in the new language appears in the text Jack has. Each element of frequencies will be strictly positive. (I.e., each of the N letters occurs at least once.)
You are also given an array keySize. The number of elements of keySize is the number of keys on the keyboard. Each element of keySize gives the maximal number of letters that maybe put on one of the keys.
Find an assignment of letters to keys that minimizes the number of keystrokes needed to type the entire text. Output that minimum number of keystrokes. If there is not enough room on the keys and some letters of the alphabet won’t fit, Output -1 instead.
Input Specification
The first line will contain a number ‘N’ that specifies the size of ‘frequencies’ array
The second line will contain N numbers that form the frequencies array
The third line contains a number ‘K’ that specifies the size of the ‘keySize’ array
The fourth line contains K numbers that form the keySize array
Output Specification
Output a single integer that is answer to the problem.
Constraints
frequencies will contain between 1 and 50 elements, inclusive.
Each element of frequencies will be between 1 and 1,000, inclusive.
keySizes will contain between 1 and 50 elements, inclusive.
Each element of keySizes will be between 1 and 50, inclusive.
Sample Input 4 7 3 4 1 2 2 2 Sample Output 19 Explanation The foreign language has four letters. Let us call them W, X, Y and Z. Jack's text contains seven Ws, three Xs, four Ys, and one Z. The keyboard has two keys, each of them may contain at most two letters. One optimal solution is to use the keys "WZ" and "YX". We can then type each W and each Y using a single keystroke, and we need two keystrokes for each X and each Z. Therefore, the total number of keystrokes when typing the entire text will be 71 + 32 + 41 + 12 = 19.
Sorry, the comment form is closed at this time.