Sense and Sensibility
All submissions for this problem are available.
Prabhu and Raghu work in adjacent labs in the CSA department. Occasionally they get together to solve puzzles in order to de-stress themselves. During one such session Prabhu gave Raghu a set of random looking strings. Each of them consisted of a single string letter without any spaces. At first the strings appeared gibberish but on closer observation Raghu could see that there were proper words in these otherwise gibberish strings. Prabhu also gave a Raghu a dictionary which consisted of the "sense scores" for each word. Meaning each word in this dictionary was associated with a score eg: at=2, before=3, artificial=1 etc. There was no relation between the length of the strings and the score attached to them in the dictioanry. Raghu's job was simple(according to Prabhu), he had to find out appropriate splits in these otherwise random strings such that these strings make the most sense i.e have the highest "sense score." The "sense score" of a string was the sum total of the sense scores of the split strings, such that the split consisted of only words which had sense scores attached to them in the dictionary.
Random string: called
Dictionary: at=2, al=1, cal=4, le=1, led=3
Highest Sense score of string= cal+led=4+3=7
The first line of input contains 'D', the number of words in the dictionary (1<=D<=1000). This is followed by 'D' lines. Each line has a word and its sense score, separated by a space. This is followed by a blank line. The next line of input contains 'T', the number of test cases (1<=T<=1000). This is followed by T test cases. Each test case consists of one line containing the string (of length upto 100000) to be parsed.
The output should consist of 'T' lines corresponding to the 'T' test cases. Each line should contain one number, which is the best sense score for the input string.
Input: 3 ant 4 an 2 tan 3 4 antant tan antsan nats Output: Output: 8 3 6 0
|Time Limit:||0.275862 - 0.9763 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.