2004 Canadian Computing Competition, Stage 2
Day 1, Problem 1: Scribble
Nixed, he placed the flong into the calathi halfway through the yuga.
Believe it or not, the above sentence is actually a valid English sentence. It also has two other features: it looks like spam, and the words are very valuable.
Valuable, you say? (For some reason, you are doing lots of talking to yourself today).
Yes, valuable, if you are playing Scribble. In the standard game of Scribble, calathi (which means "a vase-shaped basket represented in Greek painting and sculpture") is worth 72 points, nixed (meaning "refused") is worth 26 points, flong (which is "a compressed mass of paper sheets, forming a matrix or mold for stereotype plates") is worth 18 points, and yuga which is "any one of the four ages, Krita, or Satya, Treta, Dwapara, and Kali, into which the Hindus divide the duration or existence of the world" is worth 33 points.
Specifically, as you may know, each letter in Scribble is worth a given number of points. The goal is get the most points with a given set of letters.
For this question, we will modify the game slightly. Suppose you have 7 tiles/letters and you have scores for each letter (where the score sα for each letter α satistisfies 0 < sα < 26), and also you have a dictionary of valid words that you can consult before you play (this is different than the "normal" Scribble play). Your task is the find the highest scoring word.
You are given a number k (1 ≤ k ≤ 7) on the first line of input. On the next k lines, you will be given triples α sα rα, where α is a letter, sα is the score for that letter, and rα is the number of times that letter occurs as a tile. You can assume that
For example, the triple "a 7 2" means you have two tiles marked a and each is worth 7 points. On the next (the k + 2nd) line, there is the number N (0 < N < 100000). On each of the next N lines, there is a word (you can assume the length of each word is at least one).
The output one line long, containing one integer, which is the maximum score. That is, the maximum number of points that can be attained by using the tiles to form one complete word. If no word can be formed, the maximum number of points is zero.
4 a 1 1 b 4 1 c 2 1 d 10 4 3 ab bc c
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 27, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3