A. Expression Formatting

Codeforces

IDCF10246A

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Masha is learning programming, but her teacher always says that she is doing wrong, and her code is not pretty enough. For instance, Masha doesn't like spaces, and she never uses spaces inside expression, for example: _(a+b)*c_. The teacher tries to make Masha put the spaces around binary operators, for the expression to look like: _(a + b) * c_. Masha doesn't want to waste time on such stupid things, so she asks you to write a program that is putting spaces for her. The first line contains the expression that needs to be fixed. The expression consists of variable names, binary operators: '_+_', '_-_', '_*_', '_/_', and parentheses: '_(_', '_)_'. The expression doesn't contain any space, and is correct. All variables consist of a single lowercase English letter. The length of the expression string doesn't exceed 200. Print the same expression, adding a single space before and after each binary operator. Testing data for this problem consists of 20 test cases. For solving each test case you are awarded 5 points. Total score is the total sum of points for all test cases. The testing result for each test case is shown. ## Input The first line contains the expression that needs to be fixed. The expression consists of variable names, binary operators: '_+_', '_-_', '_*_', '_/_', and parentheses: '_(_', '_)_'. The expression doesn't contain any space, and is correct. All variables consist of a single lowercase English letter. The length of the expression string doesn't exceed 200. ## Output Print the same expression, adding a single space before and after each binary operator. [samples] ## Scoring Testing data for this problem consists of 20 test cases. For solving each test case you are awarded 5 points. Total score is the total sum of points for all test cases. The testing result for each test case is shown.

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the total number of lights, numbered $ 1 $ to $ N $. Let $ k \in \mathbb{Z}^+ $ be the number of hacker operations. Let $ d_1, d_2, \dots, d_k \in \mathbb{Z}^+ $ be the sequence of divisors used in each operation, where in the $ j $-th operation, all lights at positions $ m \cdot d_j $ (for $ m \in \mathbb{Z}^+ $, $ m \cdot d_j \leq N $) are toggled. Each light $ i \in \{1, \dots, N\} $ starts in state **on** (1), and is toggled once for each divisor $ d_j $ such that $ d_j \mid i $. Let $ s_i \in \{0,1\} $ denote the final state of light $ i $, where $ s_i = 1 $ means **on**, $ s_i = 0 $ means **off**. Let $ f(i) = |\{ j \in \{1, \dots, k\} \mid d_j \mid i \}| $ be the number of times light $ i $ is toggled. Then: $$ s_i = 1 - (f(i) \bmod 2) $$ **Objective** Compute: $$ \max_{t \in \{0,1,\dots,k\}} \left| \left\{ i \in \{1, \dots, N\} \mid \text{state of } i \text{ is off after } t \text{ operations} \right\} \right| $$ That is, track the number of lights off after each of the $ k $ operations (not just the final state), and return the **maximum** number of lights that are simultaneously off at any point during the $ k $ operations.

API Response (JSON)

{
  "problem": {
    "name": "A. Expression Formatting",
    "description": {
      "content": "Masha is learning programming, but her teacher always says that she is doing wrong, and her code is not pretty enough. For instance, Masha doesn't like spaces, and she never uses spaces inside express",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10246A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Masha is learning programming, but her teacher always says that she is doing wrong, and her code is not pretty enough. For instance, Masha doesn't like spaces, and she never uses spaces inside express...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the total number of lights, numbered $ 1 $ to $ N $.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of hacker operations.  \nLet $ d_1, d_2, \\dots, d_k \\in \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments