{"raw_statement":[{"iden":"statement","content":"You're phone has incorrectly autocorrected some of your recent texts, and you're trying to make a more effective autocorrect system.\n\nYou're given an incorrectly spelled word. The _similarity index_ of two words $s$ and $t$ is calculated as follows:\n\n1. Define two variables: $t o t$, representing the total pairs checked, and $m a t$, representing the matches found.\n\n2. Iterate through all pairs of letters in $s$ and $t$.\n\n3. Increment $t o t$ by one, and if the letters are equal, increment $m a t$ by one as well.\n\nThe similarity index is calculated as mat / tot.\n\nGiven several words, your autocorrect system will choose the word which is the most similar to the original word, using the algorithm described above.\n\nThe first line of input contains a single word $w$: the incorrectly spelled word, consisting only of lowercase characters. The next line contains a single positive integer $n$: the number of correctly spelled words in the dictionary. The next $n$ lines each contain a correctly spelled word $s$: a dictionary entry, consisting of only lowercase characters.\n\nOutput $n$ lines. Each line should contain a word from the dictionary, and its similarity index, *rounded to two decimal places*. The words should be sorted from highest to lowest by their similarity index. If two words have the same similarity index, sort them alphabetically *in reverse order*.\n\n"},{"iden":"input","content":"The first line of input contains a single word $w$: the incorrectly spelled word, consisting only of lowercase characters. The next line contains a single positive integer $n$: the number of correctly spelled words in the dictionary. The next $n$ lines each contain a correctly spelled word $s$: a dictionary entry, consisting of only lowercase characters."},{"iden":"output","content":"Output $n$ lines. Each line should contain a word from the dictionary, and its similarity index, *rounded to two decimal places*. The words should be sorted from highest to lowest by their similarity index. If two words have the same similarity index, sort them alphabetically *in reverse order*."},{"iden":"examples","content":"Inputhello\n5\nhelo\nhelllo\nyello\nhellow\nhelpo\nOutputhelllo 0.30\nhelo 0.25\nyello 0.24\nhellow 0.23\nhelpo 0.20\nInputcoderams\n8\ncauliflower\ncoders\ncodered\nclassroom\ncodeforces\ncontest\ncode\ncoding\nOutputcoders 0.12\ncodered 0.12\ncode 0.12\ncodeforces 0.11\nclassroom 0.11\ncontest 0.07\ncoding 0.06\ncauliflower 0.06\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ w \\in \\Sigma^* $ be the incorrectly spelled word, where $ \\Sigma = \\{a, b, \\dots, z\\} $.  \nLet $ D = \\{s_1, s_2, \\dots, s_n\\} \\subseteq \\Sigma^* $ be the dictionary of correctly spelled words.  \n\nFor any two words $ s, t \\in \\Sigma^* $, define:  \n- $ \\text{tot}(s, t) = \\min(|s|, |t|) $,  \n- $ \\text{mat}(s, t) = \\sum_{i=1}^{\\min(|s|, |t|)} \\mathbf{1}_{s[i] = t[i]} $,  \n- The similarity index: $ \\text{sim}(s, t) = \\frac{\\text{mat}(s, t)}{\\text{tot}(s, t)} $.  \n\n**Constraints**  \n1. $ |w| \\geq 1 $, $ |s_i| \\geq 1 $ for all $ i \\in \\{1, \\dots, n\\} $.  \n2. All characters are lowercase English letters.  \n3. $ 1 \\leq n \\leq 1000 $.  \n\n**Objective**  \nFor each $ s_i \\in D $, compute $ \\text{sim}(w, s_i) $, rounded to two decimal places.  \nOutput the dictionary words sorted in descending order of $ \\text{sim}(w, s_i) $.  \nIn case of ties, sort alphabetically in reverse (i.e., descending lexicographical) order.","simple_statement":"Given a misspelled word and a dictionary of correct words, calculate the similarity index between the misspelled word and each dictionary word. The similarity index is the ratio of matching letter pairs to total letter pairs compared (including all pairs of positions, even if words have different lengths). Output each dictionary word with its similarity index (rounded to two decimal places), sorted by index descending, and alphabetically reverse if tied.","has_page_source":false}