A. MaratonIME stacks popcorn buckets

Codeforces

IDCF10137A

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

On a Friday afternoon, some members of MaratonIME decided to watch a movie at CinIME. There were n members who received popcorn buckets numbered from 1 to n. At a certain moment, bucket 1 had one popcorn, bucket 2 had two popcorns and so on until bucket n, which had n popcorns. As good competitive programmers, they always prefer to simplify things, and decided to gather all the popcorn in just one bucket. They proceeded on the following way: In bucket 2, they gather the popcorn from buckets 1 and 2. Then, in bucket 3, those of bucket 2 and 3 and so on until the last bucket. Formally, they perform n - 1 movements, on the i-th movement they join the popcorn from buckets i and i + 1 on bucket i + 1. However, they are known to be clumsy and at each moment they join two buckets, they let a single popcorn fall to the ground, which they promptly throw in the trash. Jiang, the Sharp, realized that maybe the last bucket would be too small to hold all of the popcorn. Therefore, he asked for your help to determine how much popcorn should remain in the last bucket. Given n, the number of members who decided to watch the movie, print the amount of popcorn that would remain in bucket n. Keep in mind that exactly one popcorn is lost at each step. The first line contains the integer n (2 ≤ n ≤ 3 * 109) – the number of members from MaratonIME who decided to watch the movie. An integer: The amount of popcorn the last bucket should have. ## Input The first line contains the integer n (2 ≤ n ≤ 3 * 109) – the number of members from MaratonIME who decided to watch the movie. ## Output An integer: The amount of popcorn the last bucket should have. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 3 \cdot 10^9 $. Let the initial amount of popcorn in bucket $ i $ be $ i $, for $ i = 1, 2, \dots, n $. **Constraints** - Total initial popcorn: $ \sum_{i=1}^n i = \frac{n(n+1)}{2} $ - $ n - 1 $ merging steps occur. - At each step, exactly 1 popcorn is lost. **Objective** Compute the final amount of popcorn in bucket $ n $ after $ n - 1 $ merges, each losing 1 popcorn: $$ \frac{n(n+1)}{2} - (n - 1) $$

API Response (JSON)

{
  "problem": {
    "name": "A. MaratonIME stacks popcorn buckets",
    "description": {
      "content": "On a Friday afternoon, some members of MaratonIME decided to watch a movie at CinIME. There were n members who received popcorn buckets numbered from 1 to n. At a certain moment, bucket 1 had one po",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10137A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "On a Friday afternoon, some members of MaratonIME decided to watch a movie at CinIME.\n\nThere were n members who received popcorn buckets numbered from 1 to n.\n\nAt a certain moment, bucket 1 had one po...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 3 \\cdot 10^9 $.  \nLet the initial amount of popcorn in bucket $ i $ be $ i $, for $ i = 1, 2, \\dots, n $.  \n\n**Constraints**  \n- Total i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments