{"problem":{"name":"122. Autocorrect","description":{"content":"You're phone has incorrectly autocorrected some of your recent texts, and you're trying to make a more effective autocorrect system. You're given an incorrectly spelled word. The _similarity index_ o","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10269122"},"statements":[{"statement_type":"Markdown","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## Input\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\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10269122","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}