F. Nate and Fan Meet-and-Greet

Codeforces

IDCF10205F

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Nate is attending a meet-and-greet for his favorite celebrity voice actress, Hana Kanazawa! You might know her from her voice-over work in the Mono Guitar Hero series, Doreimon, its sequel Durararaemon, and of course, Angel Beats Agents. She announced that she would give a signed copy of her new album to whomever could guess the serial number on Volume $x$ of her favorite manga. Nate, of course, knows that this would be the volume of The World Dog Only Knows that introduces the character Shiori, whom she voices in the anime. He also happens to know that for this series, the serial number of Volume $n$, $s_n$, satisfies the following: Here, $s_{n -1}$ is the serial number of Volume $n -1$ and $s_{n -2}$ is the serial number of Volume $n -2$. Nate can't think well under pressure, and a signed album from his favorite celebrity is in jeopardy! Can you help him find the serial number of Volume $x$? The input consists of a line with only a single integer $x$, the volume whose serial number must be found. *Constraints* $1 <= x <= 10^(18)$ Output a single integer, the serial number of Volume $x$. The serial number of Volume $1$ is given from the definition. The serial number of Volume $2$ is $2 s_1 -s_0 = 2$. ## Input The input consists of a line with only a single integer $x$, the volume whose serial number must be found.*Constraints*$1 <= x <= 10^(18)$ ## Output Output a single integer, the serial number of Volume $x$. [samples] ## Note The serial number of Volume $1$ is given from the definition. The serial number of Volume $2$ is $2 s_1 -s_0 = 2$.

**Definitions** Let $ \mathcal{S} \subset \mathbb{R}^3 $ be a solid sphere with center $ \mathbf{o} = (o_x, o_y, o_z) $ and radius $ r > 0 $. Let $ \mathbf{s} = (s_x, s_y, s_z) $, $ \mathbf{t} = (t_x, t_y, t_z) \in \mathbb{R}^3 $ be two points such that $ \|\mathbf{s} - \mathbf{o}\| \geq r $ and $ \|\mathbf{t} - \mathbf{o}\| \geq r $. **Constraints** 1. $ 1 \leq T \leq 1000 $ 2. $ 1 \leq o_x, o_y, o_z, r, s_x, s_y, s_z, t_x, t_y, t_z \leq 1000 $ 3. $ \mathbf{s}, \mathbf{t} \notin \text{int}(\mathcal{S}) $ **Objective** Compute the shortest path length from $ \mathbf{s} $ to $ \mathbf{t} $ in $ \mathbb{R}^3 \setminus \text{int}(\mathcal{S}) $, i.e., the minimum distance avoiding the interior of the sphere: $$ \min_{\gamma: \mathbf{s} \to \mathbf{t},\ \gamma \cap \text{int}(\mathcal{S}) = \emptyset} \text{length}(\gamma) $$

API Response (JSON)

{
  "problem": {
    "name": "F. Nate and Fan Meet-and-Greet",
    "description": {
      "content": "Nate is attending a meet-and-greet for his favorite celebrity voice actress, Hana Kanazawa! You might know her from her voice-over work in the Mono Guitar Hero series, Doreimon, its sequel Durararaemo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10205F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Nate is attending a meet-and-greet for his favorite celebrity voice actress, Hana Kanazawa! You might know her from her voice-over work in the Mono Guitar Hero series, Doreimon, its sequel Durararaemo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ \\mathcal{S} \\subset \\mathbb{R}^3 $ be a solid sphere with center $ \\mathbf{o} = (o_x, o_y, o_z) $ and radius $ r > 0 $.  \nLet $ \\mathbf{s} = (s_x, s_y, s_z) $, $ \\mathbf{t} = (...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments