G. Snails

Codeforces

IDCF10238G

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

On Planet E, snails are born in infinitely deep wells! Initially a snail is at $n$ meters below the ground. During the daytime the snail try very hard to climb up, and goes up by $a$ meters. It can escape the well once it touches the ground. However during the night the snail has to sleep and falls back by $b$ meters. Hence it may happens that an unfortunate snail stucks in the well forever. Can you help the snails on Planet E to determine the number of days they need to escape the well? The first line contains a positive integer $T$ ($T <= 10$), the number of testcases. Each testcase contains three integers $n, a, b$ ($1 <= n <= 1000$, $0 <= a <= 1000$, $0 <= b <= 1000$), the initial position of the snail, the length it climbs up during the daytime, and the length it falls during the night. For each testcase, output a single line consisting of the number of days the snail need to escape the well. Output "-1" (without quotes) if it is impossible. ## Input The first line contains a positive integer $T$ ($T <= 10$), the number of testcases.Each testcase contains three integers $n, a, b$ ($1 <= n <= 1000$, $0 <= a <= 1000$, $0 <= b <= 1000$), the initial position of the snail, the length it climbs up during the daytime, and the length it falls during the night. ## Output For each testcase, output a single line consisting of the number of days the snail need to escape the well. Output "-1" (without quotes) if it is impossible. [samples]

**Definitions** Let $ T \in \mathbb{Z}^+ $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $, let: - $ n_k \in \mathbb{Z}^+ $: initial depth below ground (meters), - $ a_k \in \mathbb{Z}_{\geq 0} $: daily climb (meters), - $ b_k \in \mathbb{Z}_{\geq 0} $: nightly fall (meters). **Constraints** 1. $ 1 \leq T \leq 10 $ 2. For each $ k $: - $ 1 \leq n_k \leq 1000 $ - $ 0 \leq a_k \leq 1000 $ - $ 0 \leq b_k \leq 1000 $ **Objective** For each test case $ k $, compute the minimal number of days $ d_k \in \mathbb{Z}^+ \cup \{-1\} $ such that the snail escapes: - On day $ d $, after climbing, the snail’s position $ \geq 0 $. - Position after $ d-1 $ full days and nights: $ -n_k + (d-1)(a_k - b_k) $ - After climbing on day $ d $: $ -n_k + (d-1)(a_k - b_k) + a_k \geq 0 $ If $ a_k = 0 $: escape impossible unless $ n_k = 0 $ (but $ n_k \geq 1 $), so always impossible. If $ a_k \leq b_k $ and $ n_k > a_k $: impossible (never escapes). Otherwise: solve for minimal $ d_k $ satisfying: $$ -n_k + (d_k - 1)(a_k - b_k) + a_k \geq 0 $$ $$ \Rightarrow d_k \geq 1 + \frac{n_k - a_k}{a_k - b_k} $$ If $ a_k > b_k $, then: $$ d_k = \left\lceil \frac{n_k - a_k}{a_k - b_k} \right\rceil + 1 $$ If $ a_k \leq b_k $ and $ n_k > a_k $, output $ -1 $. If $ n_k \leq a_k $, then $ d_k = 1 $.

API Response (JSON)

{
  "problem": {
    "name": "G. Snails",
    "description": {
      "content": "On Planet E, snails are born in infinitely deep wells! Initially a snail is at $n$ meters below the ground. During the daytime the snail try very hard to climb up, and goes up by $a$ meters. It can e",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10238G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "On Planet E, snails are born in infinitely deep wells!\n\nInitially a snail is at $n$ meters below the ground. During the daytime the snail try very hard to climb up, and goes up by $a$ meters. It can e...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let:  \n- $ n_k \\in \\mathbb{Z}^+ $: initial depth below ground (meters),  \n- $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments