A. Arpa and a research in Mexican wave

Codeforces

IDCF851A

Time1000ms

Memory256MB

Difficulty—

implementationmath

English · Original

Chinese · Translation

Formal · Original

Arpa is researching the Mexican wave. There are _n_ spectators in the stadium, labeled from 1 to _n_. They start the Mexican wave at time 0. * At time 1, the first spectator stands. * At time 2, the second spectator stands. * ... * At time _k_, the _k_\-th spectator stands. * At time _k_ + 1, the (_k_ + 1)\-th spectator stands and the first spectator sits. * At time _k_ + 2, the (_k_ + 2)\-th spectator stands and the second spectator sits. * ... * At time _n_, the _n_\-th spectator stands and the (_n_ - _k_)\-th spectator sits. * At time _n_ + 1, the (_n_ + 1 - _k_)\-th spectator sits. * ... * At time _n_ + _k_, the _n_\-th spectator sits. Arpa wants to know how many spectators are standing at time _t_. ## Input The first line contains three integers _n_, _k_, _t_ (1 ≤ _n_ ≤ 109, 1 ≤ _k_ ≤ _n_, 1 ≤ _t_ < _n_ + _k_). ## Output Print single integer: how many spectators are standing at time _t_. [samples] ## Note In the following a sitting spectator is represented as _\-_, a standing spectator is represented as _^_. * At _t_ = 0 _\----------_ number of standing spectators = 0. * At _t_ = 1 _^---------_ number of standing spectators = 1. * At _t_ = 2 _^^--------_ number of standing spectators = 2. * At _t_ = 3 _^^^-------_ number of standing spectators = 3. * At _t_ = 4 _^^^^------_ number of standing spectators = 4. * At _t_ = 5 _^^^^^-----_ number of standing spectators = 5. * At _t_ = 6 _\-^^^^^----_ number of standing spectators = 5. * At _t_ = 7 _\--^^^^^---_ number of standing spectators = 5. * At _t_ = 8 _\---^^^^^--_ number of standing spectators = 5. * At _t_ = 9 _\----^^^^^-_ number of standing spectators = 5. * At _t_ = 10 _\-----^^^^^_ number of standing spectators = 5. * At _t_ = 11 _\------^^^^_ number of standing spectators = 4. * At _t_ = 12 _\-------^^^_ number of standing spectators = 3. * At _t_ = 13 _\--------^^_ number of standing spectators = 2. * At _t_ = 14 _\---------^_ number of standing spectators = 1. * At _t_ = 15 _\----------_ number of standing spectators = 0.

Arpa 正在研究墨西哥波浪。体育场中有 #cf_span[n] 名观众，编号从 #cf_span[1] 到 #cf_span[n]。他们在时间 #cf_span[0] 开始表演墨西哥波浪。 Arpa 想知道在时间 #cf_span[t] 时有多少名观众是站立的。第一行包含三个整数 #cf_span[n], #cf_span[k], #cf_span[t]（#cf_span[1 ≤ n ≤ 109], #cf_span[1 ≤ k ≤ n], #cf_span[1 ≤ t < n + k]）。请输出一个整数：在时间 #cf_span[t] 时有多少名观众是站立的。在以下描述中，坐着的观众用 _- _ 表示，站立的观众用 _^_ 表示。 ## Input 第一行包含三个整数 #cf_span[n], #cf_span[k], #cf_span[t]（#cf_span[1 ≤ n ≤ 109], #cf_span[1 ≤ k ≤ n], #cf_span[1 ≤ t < n + k]）。 ## Output 请输出一个整数：在时间 #cf_span[t] 时有多少名观众是站立的。 [samples] ## Note 在以下描述中，坐着的观众用 _- _ 表示，站立的观众用 _^_ 表示。在 #cf_span[t = 0 ] 时 _----------_，站立观众数量 = 0。在 #cf_span[t = 1 ] 时 _^---------_，站立观众数量 = 1。在 #cf_span[t = 2 ] 时 _^^--------_，站立观众数量 = 2。在 #cf_span[t = 3 ] 时 _^^^-------_，站立观众数量 = 3。在 #cf_span[t = 4 ] 时 _^^^^------_，站立观众数量 = 4。在 #cf_span[t = 5 ] 时 _^^^^^-----_，站立观众数量 = 5。在 #cf_span[t = 6 ] 时 _-^^^^^----_，站立观众数量 = 5。在 #cf_span[t = 7 ] 时 _--^^^^^---_，站立观众数量 = 5。在 #cf_span[t = 8 ] 时 _---^^^^^--_，站立观众数量 = 5。在 #cf_span[t = 9 ] 时 _----^^^^^-_，站立观众数量 = 5。在 #cf_span[t = 10] 时 _-----^^^^^_，站立观众数量 = 5。在 #cf_span[t = 11] 时 _------^^^^_，站立观众数量 = 4。在 #cf_span[t = 12] 时 _-------^^^_，站立观众数量 = 3。在 #cf_span[t = 13] 时 _--------^^_，站立观众数量 = 2。在 #cf_span[t = 14] 时 _---------^_，站立观众数量 = 1。在 #cf_span[t = 15] 时 _----------_，站立观众数量 = 0。

**Definitions** Let $ n, k, t \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10^9 $, $ 1 \leq k \leq n $, and $ 1 \leq t < n + k $. The Mexican wave proceeds as follows: - At time $ 0 $, all spectators are seated. - At each integer time $ i \geq 1 $, the $ i $-th spectator stands if $ i \leq n $, and the wave propagates such that: - A spectator stands at time $ \max(1, i - k + 1) $ to $ \min(i, n) $, and remains standing until time $ i + k - 1 $. - More precisely, spectator $ j $ stands during the time interval $ [j, j + k - 1] \cap \mathbb{Z} $, for $ j \in \{1, \dots, n\} $. **Constraints** 1. $ 1 \leq n \leq 10^9 $ 2. $ 1 \leq k \leq n $ 3. $ 1 \leq t < n + k $ **Objective** Compute the number of spectators standing at time $ t $: $$ \left| \left\{ j \in \{1, \dots, n\} \mid j \leq t \leq j + k - 1 \right\} \right| $$

Samples

Input #1

10 5 3

Output #1

Input #2

10 5 7

Output #2

Input #3

10 5 12

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Arpa and a research in Mexican wave",
    "description": {
      "content": "Arpa is researching the Mexican wave. There are _n_ spectators in the stadium, labeled from 1 to _n_. They start the Mexican wave at time 0. *   At time 1, the first spectator stands. *   At time 2,",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF851A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Arpa is researching the Mexican wave.\n\nThere are _n_ spectators in the stadium, labeled from 1 to _n_. They start the Mexican wave at time 0.\n\n*   At time 1, the first spectator stands.\n*   At time 2,...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Arpa 正在研究墨西哥波浪。\n\n体育场中有 #cf_span[n] 名观众，编号从 #cf_span[1] 到 #cf_span[n]。他们在时间 #cf_span[0] 开始表演墨西哥波浪。\n\nArpa 想知道在时间 #cf_span[t] 时有多少名观众是站立的。\n\n第一行包含三个整数 #cf_span[n], #cf_span[k], #cf_span[t]（#cf_span[1 ≤ n ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k, t \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10^9 $, $ 1 \\leq k \\leq n $, and $ 1 \\leq t < n + k $.  \n\nThe Mexican wave proceeds as follows:  \n- At time $ 0 $, all spectator...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments