{"raw_statement":[{"iden":"statement","content":"You are the \"do-er\" for the Science Olympiad event \"Write it, Do it\", which means that you have to interpret your event partner's written description of an object and replicate the object based on the description. Unfortunately, your partner is bad at spelling and misspelled a critical word in the description. Your task is to figure out which word your partner most likely meant to write.\n\nThe first line of input contains a string _s_: the word misspelled by your partner. Assume that your partner did not add or remove any letters; they only replaced letters with incorrect ones. The next line contains a single positive integer _n_ indicating the number of possible valid words that your partner could have meant to write. Each of the next _n_ lines contains each of these words. There is guaranteed to be at least one word of the same length as the misspelled word.\n\nOutput a single word _w_: the word in the dictionary of possible words closest to the misspelled word. \"Closeness\" is defined as the minimum number of different characters. If there is a tie, choose the word that comes first in the given dictionary of words.\n\n"},{"iden":"input","content":"The first line of input contains a string _s_: the word misspelled by your partner. Assume that your partner did not add or remove any letters; they only replaced letters with incorrect ones. The next line contains a single positive integer _n_ indicating the number of possible valid words that your partner could have meant to write. Each of the next _n_ lines contains each of these words. There is guaranteed to be at least one word of the same length as the misspelled word."},{"iden":"output","content":"Output a single word _w_: the word in the dictionary of possible words closest to the misspelled word. \"Closeness\" is defined as the minimum number of different characters. If there is a tie, choose the word that comes first in the given dictionary of words."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s $ be the misspelled string.  \nLet $ D = \\{w_1, w_2, \\dots, w_n\\} $ be the dictionary of candidate words, where $ |w_i| = |s| $ for all $ i $ (guaranteed at least one such word).  \n\n**Constraints**  \n1. $ |s| = |w_i| $ for all $ w_i \\in D $  \n2. All strings consist of lowercase letters.  \n\n**Objective**  \nFind $ w^* \\in D $ such that:  \n$$\nw^* = \\arg\\min_{w \\in D} \\text{HammingDistance}(s, w)\n$$  \nIf multiple $ w \\in D $ achieve the minimum Hamming distance, choose the one that appears first in the dictionary order.","simple_statement":"Find the word in the list that differs from the misspelled word in the fewest letters. If tied, pick the first one in the list.","has_page_source":false}