025. Write It, Do It

Codeforces

IDCF10269025

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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. 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. 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. ## Input 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. ## Output 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. [samples]

**Definitions** Let $ s $ be the misspelled string. Let $ 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). **Constraints** 1. $ |s| = |w_i| $ for all $ w_i \in D $ 2. All strings consist of lowercase letters. **Objective** Find $ w^* \in D $ such that: $$ w^* = \arg\min_{w \in D} \text{HammingDistance}(s, w) $$ If multiple $ w \in D $ achieve the minimum Hamming distance, choose the one that appears first in the dictionary order.

API Response (JSON)

{
  "problem": {
    "name": "025. Write It, Do It",
    "description": {
      "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_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269025"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**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 wor...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments