Gutenberg's algorithmic printing press - 1

Computer Science Level 4

In Gutenberg's printing press, each line of text is assembled by placing individual metal letters in a rack, applying ink to the letters and then pressing them onto paper. Gutenberg needs to print N words using his printing press, one word at a time. The printing press allows the following operations:  Add a letter to the end of the word currently in the rack.  Remove the last letter from the word currently in the rack.  Print the word currently in the rack.

Initially, the rack is empty; it contains no metal letters. At the end of printing, Gutenberg is allowed to leave letters in the rack. Also, he is allowed to print the words in any order that he likes. As each operation requires time, he wants to minimize the total number of operations. For instance, if Gutenberg is supposed to print out three words, {print, the, poem}, he could do it using 20 operations: add t, add h, add e, print, remove last letter (three times), add p, add o, add e, add m, print, remove last letter (three times), add r, add i, add n, add t, print. In each of the following cases, determine the minimum number of operations required to print out all the words in the set, in any order, one word at a time.

{ there, theirs, her, shore, three, tree, rest, hence, thorium, therefore, threshold }

 [This is question from zonal Informatics Olympiad , India ]

Problem Loading...

Note Loading...

Set Loading...