156. Closest Houses

Codeforces

IDCF10269156

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

For this problem, you will be tasked with sorting a series of houses by how close they are to a given house. The rules for house distances are as follows: houses on the same street will have have a distance of the difference between their house numbers, and houses on different streets will experience a distance equal to the difference between their house numbers times the difference between their street numbers. Houses will be each provided with a unique name, such as "h1", and will also have a street number that represents which street they live on as well as a house number that represents their position on the street. For this problem, you will be given a series of houses and their respective values and you will need to determine which house is the closest to a specified house. For example, you may be given h1,h2,h3,h4,h5, then asked to find the closest house to h3. The first line of input contains a single integer $n$ that represents the number of houses that are contained in the set. The next $n$ lines each contain information about a different house in the format: "name streetnum housenum". After $n$ lines, there will be one line that lists the name of the house that should be used in the nearest house computation. A single string that represents the house that is closest to the given house name. ## Input The first line of input contains a single integer $n$ that represents the number of houses that are contained in the set. The next $n$ lines each contain information about a different house in the format: "name streetnum housenum". After $n$ lines, there will be one line that lists the name of the house that should be used in the nearest house computation. ## Output A single string that represents the house that is closest to the given house name. [samples]

**Definitions** Let $ H = \{ ( \text{name}_i, s_i, h_i ) \mid i \in \{1, \dots, n\} \} $ be the set of houses, where: - $ \text{name}_i \in \mathbb{S} $ is the unique name of house $ i $, - $ s_i \in \mathbb{Z}^+ $ is the street number, - $ h_i \in \mathbb{Z}^+ $ is the house number on the street. Let $ q \in \mathbb{S} $ be the query house name, and let $ (s_q, h_q) $ be its street and house numbers. **Distance Function** For two houses $ i $ and $ j $: $$ d(i, j) = \begin{cases} |h_i - h_j| & \text{if } s_i = s_j, \\ |h_i - h_j| \cdot |s_i - s_j| & \text{if } s_i \ne s_j. \end{cases} $$ **Constraints** 1. $ 1 \le n \le 100 $ 2. All names are unique. 3. $ s_i, h_i \ge 1 $ for all $ i $. **Objective** Find the house $ \text{name}_k \in H \setminus \{q\} $ such that: $$ k = \arg\min_{i: \text{name}_i \ne q} d(i, q) $$ If multiple houses achieve the minimum distance, return any one of them.

API Response (JSON)

{
  "problem": {
    "name": "156. Closest Houses",
    "description": {
      "content": "For this problem, you will be tasked with sorting a series of houses by how close they are to a given house. The rules for house distances are as follows: houses on the same street will have have a di",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269156"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For this problem, you will be tasked with sorting a series of houses by how close they are to a given house. The rules for house distances are as follows: houses on the same street will have have a di...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ H = \\{ ( \\text{name}_i, s_i, h_i ) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of houses, where:  \n- $ \\text{name}_i \\in \\mathbb{S} $ is the unique name of house $ i $,  \n- $ s_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments