K Cakes

AtCoder

IDcodefestival_2016_qualC_b

Time1000ms

Memory256MB

Difficulty—

There are $K$ pieces of cakes. Mr. Takahashi would like to eat one cake per day, taking $K$ days to eat them all. There are $T$ types of cake, and the number of the cakes of type $i$ ($1 ≤ i ≤ T$) is $a_i$. Eating the same type of cake two days in a row would be no fun, so Mr. Takahashi would like to decide the order for eating cakes that minimizes the number of days on which he has to eat the same type of cake as the day before. Compute the minimum number of days on which the same type of cake as the previous day will be eaten. ## Constraints * $1 ≤ K ≤ 10000$ * $1 ≤ T ≤ 100$ * $1 ≤ a_i ≤ 100$ * $a_1 + a_2 + ... + a_T = K$ ## Input The input is given from Standard Input in the following format: $K$ $T$ $a_1$ $a_2$ $...$ $a_T$ [samples]

Samples

Input #1

7 3
3 2 2

Output #1

0

For example, if Mr. Takahashi eats cakes in the order of $2, 1, 2, 3, 1, 3, 1$, he can avoid eating the same type of cake as the previous day.

Input #2

6 3
1 4 1

Output #2

1

There are $6$ cakes. For example, if Mr. Takahashi eats cakes in the order of $2, 3, 2, 2, 1, 2$, he has to eat the same type of cake (i.e., type $2$) as the previous day only on the fourth day. Since this is the minimum number, the answer is $1$.

Input #3

100 1
100

Output #3

99

Since Mr. Takahashi has only one type of cake, he has no choice but to eat the same type of cake as the previous day from the second day and after.

API Response (JSON)

{
  "problem": {
    "name": "K Cakes",
    "description": {
      "content": "There are $K$ pieces of cakes. Mr. Takahashi would like to eat one cake per day, taking $K$ days to eat them all. There are $T$ types of cake, and the number of the cakes of type $i$ ($1 ≤ i ≤ T$) is ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "codefestival_2016_qualC_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $K$ pieces of cakes. Mr. Takahashi would like to eat one cake per day, taking $K$ days to eat them all.\nThere are $T$ types of cake, and the number of the cakes of type $i$ ($1 ≤ i ≤ T$) is ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments