E. Loppinha, the boy who likes sopinha

Codeforces

IDCF10187E

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Loppinha loves to go to the gym with his friends. He takes his training sessions very seriously, and he always follows his schedule very strictly. He just created a new plan where he has set exactly what he is going to do at every single one of the N minutes of the session. Loppinha loves having a sopinha (small soup) before training. The soup contains K grams of protein. As you can imagine, he needs that protein to be able to endure his very tough exercises. He is burning protein at every minute he is working out, and the amount of protein he burns in a minute depends on how many minutes he has been working out without a minute of rest. If he has trained for p minutes without resting, in the (p + 1)-th minute of workout he is going to burn p + 1 grams of protein. Of course, if he doesn't have enough protein at any moment he dies. For example, if he has 3 grams of protein at a moment and at that minute his workout requires 4, if he does the workout he dies. Given his schedule and the amount of protein K he has before starting the training session, Loppinha, who is willing to change some minutes of his workout, wants to know what is the minimum amount of minutes he has to change from working out to resting so he does not die. The first line of the input contains two integers N (1 ≤ N ≤ 450) and K (1 ≤ K ≤ 107), indicating the number of minutes in Loppinha's training session and the amount of proteins in his soup. The next line contains a string with N characters, either 0 or 1, where 0 indicates a minute of rest and a 1 indicates a minute of workout. Output a single integer - the minimum number of minutes Loppinha has to switch from workout to rest so that he can finish his exercises without dying. In the first test case, if he changes the second minute to rest, he will consume exactly 2 grams of protein. Notice that if he changes the last minute to rest instead, he would need 3 grams of protein to complete his workout session without dying. ## Input The first line of the input contains two integers N (1 ≤ N ≤ 450) and K (1 ≤ K ≤ 107), indicating the number of minutes in Loppinha's training session and the amount of proteins in his soup. The next line contains a string with N characters, either 0 or 1, where 0 indicates a minute of rest and a 1 indicates a minute of workout. ## Output Output a single integer - the minimum number of minutes Loppinha has to switch from workout to rest so that he can finish his exercises without dying. [samples] ## Note In the first test case, if he changes the second minute to rest, he will consume exactly 2 grams of protein. Notice that if he changes the last minute to rest instead, he would need 3 grams of protein to complete his workout session without dying.

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of students. **Constraints** $ N \geq 1 $ **Objective** Compute the number of distinct non-empty subsets of the set of $ N $ students with size at least 2: $$ \sum_{k=2}^{N} \binom{N}{k} $$

API Response (JSON)

{
  "problem": {
    "name": "E. Loppinha, the boy who likes sopinha",
    "description": {
      "content": "Loppinha loves to go to the gym with his friends. He takes his training sessions very seriously, and he always follows his schedule very strictly. He just created a new plan where he has set exactly w",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10187E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Loppinha loves to go to the gym with his friends. He takes his training sessions very seriously, and he always follows his schedule very strictly. He just created a new plan where he has set exactly w...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of students.\n\n**Constraints**  \n$ N \\geq 1 $\n\n**Objective**  \nCompute the number of distinct non-empty subsets of the set of $ N $ students w...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments