113. Airplane!

Codeforces

IDCF10269113

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You're flying an airplane, but you forgot to forgot to refill the fuel tank before you trip. Therefore, you must decide which airport to land at based on a number of factors: proximity, available runway space, and direction. If an airport has no available spaces, you cannot go there. If an airport is too far away, you cannot go there. You will receive 3 lines of input, the first being n number of airports, the second being how many miles you can fly, and the third being the direction of the wind (N,S,W,E,NW,NE,SW,SE). Then you will receive n lines of input consisting of 3 variables separated by spaces: the number of available runway spaces, the distance to the airport in miles, and the direction you must fly to get to the airport. You will output a number that represents which airport you should fly to. If you are flying with the wind direction, the amount of fuel you need to use is halved. If you are flying against the wind direction, it takes two times as much fuel to get to the airport. ## Input You will receive 3 lines of input, the first being n number of airports, the second being how many miles you can fly, and the third being the direction of the wind (N,S,W,E,NW,NE,SW,SE). Then you will receive n lines of input consisting of 3 variables separated by spaces: the number of available runway spaces, the distance to the airport in miles, and the direction you must fly to get to the airport. ## Output You will output a number that represents which airport you should fly to. [samples] ## Note If you are flying with the wind direction, the amount of fuel you need to use is halved. If you are flying against the wind direction, it takes two times as much fuel to get to the airport.

**Definitions** Let $ n \in \mathbb{Z} $ be the number of airports. Let $ d_{\text{max}} \in \mathbb{R}^+ $ be the maximum distance (in miles) the plane can fly. Let $ w \in \{\text{N}, \text{S}, \text{W}, \text{E}, \text{NW}, \text{NE}, \text{SW}, \text{SE}\} $ be the wind direction. For each airport $ i \in \{1, \dots, n\} $: - Let $ r_i \in \mathbb{Z}_{\geq 0} $ be the number of available runway spaces. - Let $ d_i \in \mathbb{R}^+ $ be the distance (in miles) to airport $ i $. - Let $ \delta_i \in \{\text{N}, \text{S}, \text{W}, \text{E}, \text{NW}, \text{NE}, \text{SW}, \text{SE}\} $ be the direction to airport $ i $. Define the fuel multiplier $ m_i $ as: $$ m_i = \begin{cases} 0.5 & \text{if } \delta_i = w \\ 2.0 & \text{if } \delta_i \neq w \text{ and } \delta_i \neq \text{opposite}(w) \\ 1.0 & \text{otherwise} \end{cases} $$ *(Note: "opposite" means N↔S, E↔W, NW↔SE, NE↔SW)* **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ d_{\text{max}} > 0 $ 3. $ r_i \geq 0 $, $ d_i > 0 $ for all $ i $ 4. Airport $ i $ is viable **iff**: - $ r_i > 0 $ - $ d_i \cdot m_i \leq d_{\text{max}} $ **Objective** Select the airport $ i^* \in \{1, \dots, n\} $ with the **maximum** $ r_i $ among all viable airports. If multiple airports tie in $ r_i $, select the one with **minimum** $ d_i \cdot m_i $. If still tied, select the one with **lowest index** $ i $. Output $ i^* $.

API Response (JSON)

{
  "problem": {
    "name": "113. Airplane!",
    "description": {
      "content": "You're flying an airplane, but you forgot to forgot to refill the fuel tank before you trip. Therefore, you must decide which airport to land at based on a number of factors: proximity, available runw",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269113"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You're flying an airplane, but you forgot to forgot to refill the fuel tank before you trip. Therefore, you must decide which airport to land at based on a number of factors: proximity, available runw...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of airports.  \nLet $ d_{\\text{max}} \\in \\mathbb{R}^+ $ be the maximum distance (in miles) the plane can fly.  \nLet $ w \\in \\{\\text{N}, \\text{S}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments