C. Death Report

Codeforces

IDCF10073C

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Even though he is the head of the Shitalian Mafia, Shi doesn't like bloodshed and punishes his subordinates if they kill innocent people. That is why the death report is always written in the following way: #cf_span(class=[tex-font-style-underline], body=["We killed x% of the innocent people"]). Shi wants to know the smallest number of innocent people that must have been in that place so that *exactly* x% of the innocent people have died. For instance, if we have x = 35%. In this case we had 20 people, and 7 were victims, because 35% of 20 is 7. That is the minimum possible. There is a single number 0 ≤ x ≤ 100 with at most 15 decimal places. Print the number sought by Shi. ## Input There is a single number 0 ≤ x ≤ 100 with at most 15 decimal places. ## Output Print the number sought by Shi. [samples]

**Definitions** Let $ n, d \in \mathbb{Z}^+ $, with $ 1 \leq n \leq 10^5 $, $ 1 \leq d \leq 10^9 $. Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the initial rating vector of $ n $ users. Let $ \sigma: \{1, \dots, n\} \to \{1, \dots, n\} $ be a permutation such that $ a_{\sigma(1)} > a_{\sigma(2)} > \dots > a_{\sigma(n)} $ (i.e., users sorted in descending order of initial ratings). Let $ x_i \in \mathbb{Z} $ denote the net number of contests (positive for increases, negative for decreases) applied to user $ i $. Each contest changes a user’s rating by $ \pm d $, so the final rating of user $ i $ is $ a_i + x_i \cdot d $. **Constraints** 1. All final ratings must be distinct: $$ a_i + x_i d \neq a_j + x_j d \quad \forall i \neq j $$ 2. After contests, user $ i $ must have the $ i $-th greatest rating (i.e., the final ratings must be strictly decreasing with user index): $$ a_1 + x_1 d > a_2 + x_2 d > \dots > a_n + x_n d $$ 3. Each $ x_i \in \mathbb{Z} $, and the total number of contests is $ \sum_{i=1}^n |x_i| $ (each contest affects exactly one user). **Objective** Minimize $ \sum_{i=1}^n |x_i| $, subject to the above constraints.

API Response (JSON)

{
  "problem": {
    "name": "C. Death Report",
    "description": {
      "content": "Even though he is the head of the Shitalian Mafia, Shi doesn't like bloodshed and punishes his subordinates if they kill innocent people. That is why the death report is always written in the followin",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10073C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Even though he is the head of the Shitalian Mafia, Shi doesn't like bloodshed and punishes his subordinates if they kill innocent people. That is why the death report is always written in the followin...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, d \\in \\mathbb{Z}^+ $, with $ 1 \\leq n \\leq 10^5 $, $ 1 \\leq d \\leq 10^9 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the initial rating vector of $ n $ users....",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments