D1. Hyperspace Jump (easy)

Codeforces

IDCF958D1

Time5000ms

Memory256MB

Difficulty—

expression parsingmath

English · Original

Chinese · Translation

Formal · Original

The Rebel fleet is on the run. It consists of _m_ ships currently gathered around a single planet. Just a few seconds ago, the vastly more powerful Empire fleet has appeared in the same solar system, and the Rebels will need to escape into hyperspace. In order to spread the fleet, the captain of each ship has independently come up with the coordinate to which that ship will jump. In the obsolete navigation system used by the Rebels, this coordinate is given as the value of an arithmetic expression of the form . To plan the future of the resistance movement, Princess Heidi needs to know, for each ship, how many ships are going to end up at the same coordinate after the jump. You are her only hope! ## Input The first line of the input contains a single integer _m_ (1 ≤ _m_ ≤ 200 000) – the number of ships. The next _m_ lines describe one jump coordinate each, given as an arithmetic expression. An expression has the form _(a+b)/c_. Namely, it consists of: an opening parenthesis _(_, a positive integer _a_ of up to two decimal digits, a plus sign _+_, a positive integer _b_ of up to two decimal digits, a closing parenthesis _)_, a slash _/_, and a positive integer _c_ of up to two decimal digits. ## Output Print a single line consisting of _m_ space-separated integers. The _i_\-th integer should be equal to the number of ships whose coordinate is equal to that of the _i_\-th ship (including the _i_\-th ship itself). [samples] ## Note In the sample testcase, the second and the third ship will both end up at the coordinate 3. Note that this problem has only two versions – easy and hard.

叛军舰队正在逃亡。目前，共有 #cf_span[m] 艘飞船聚集在一颗行星周围。就在几秒钟前，实力远为强大的帝国舰队出现在同一星系中，叛军必须跃迁进入超空间。为了分散舰队，每艘飞船的船长独立地确定了该飞船将跃迁至的坐标。在叛军使用的过时导航系统中，该坐标以如下形式的算术表达式的值给出。为了规划抵抗运动的未来，海迪公主需要知道，每艘飞船跃迁后，有多少艘飞船会落在相同的坐标上。你是她唯一的希望！输入的第一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 200 000]) —— 飞船的数量。接下来的 #cf_span[m] 行每行描述一个跃迁坐标，以算术表达式形式给出。表达式的形式为 _(a+b)/c_。具体而言，它由以下部分组成：一个左括号 _(_，一个最多两位十进制数字的正整数 #cf_span[a]，一个加号 _+_，一个最多两位十进制数字的正整数 #cf_span[b]，一个右括号 _)_，一个斜杠 _/_，以及一个最多两位十进制数字的正整数 #cf_span[c]。请输出一行，包含 #cf_span[m] 个用空格分隔的整数。第 #cf_span[i] 个整数应等于与第 #cf_span[i] 艘飞船坐标相同的飞船数量（包括第 #cf_span[i] 艘飞船自身）。在样例测试用例中，第二艘和第三艘飞船都将最终到达坐标 #cf_span[3]。注意：本题仅有两个版本——简单版和困难版。 ## Input 输入的第一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 200 000]) —— 飞船的数量。接下来的 #cf_span[m] 行每行描述一个跃迁坐标，以算术表达式形式给出。表达式的形式为 _(a+b)/c_。具体而言，它由以下部分组成：一个左括号 _(_，一个最多两位十进制数字的正整数 #cf_span[a]，一个加号 _+_，一个最多两位十进制数字的正整数 #cf_span[b]，一个右括号 _)_，一个斜杠 _/_，以及一个最多两位十进制数字的正整数 #cf_span[c]。 ## Output 请输出一行，包含 #cf_span[m] 个用空格分隔的整数。第 #cf_span[i] 个整数应等于与第 #cf_span[i] 艘飞船坐标相同的飞船数量（包括第 #cf_span[i] 艘飞船自身）。 [samples] ## Note 在样例测试用例中，第二艘和第三艘飞船都将最终到达坐标 #cf_span[3]。注意：本题仅有两个版本——简单版和困难版。

**Definitions** Let $ m \in \mathbb{Z} $ be the number of ships. For each ship $ i \in \{1, \dots, m\} $, its jump coordinate is given by an expression of the form $ \frac{a_i + b_i}{c_i} $, where: - $ a_i, b_i, c_i \in \mathbb{Z} $, - $ 1 \leq a_i, b_i, c_i \leq 99 $. Define the coordinate function: $$ f(i) = \frac{a_i + b_i}{c_i} $$ Let $ C = \{ f(i) \mid i \in \{1, \dots, m\} \} $ be the multiset of coordinates. **Constraints** 1. $ 1 \leq m \leq 200{,}000 $ 2. For all $ i \in \{1, \dots, m\} $: - $ 1 \leq a_i, b_i, c_i \leq 99 $ - $ c_i \neq 0 $ (implied by positivity) **Objective** For each ship $ i \in \{1, \dots, m\} $, compute: $$ \text{count}(i) = \left| \left\{ j \in \{1, \dots, m\} \mid f(j) = f(i) \right\} \right| $$ Output the sequence $ \left( \text{count}(1), \text{count}(2), \dots, \text{count}(m) \right) $.

Samples

Input #1

4
(99+98)/97
(26+4)/10
(12+33)/15
(5+1)/7

Output #1

1 2 2 1

API Response (JSON)

{
  "problem": {
    "name": "D1. Hyperspace Jump (easy)",
    "description": {
      "content": "The Rebel fleet is on the run. It consists of _m_ ships currently gathered around a single planet. Just a few seconds ago, the vastly more powerful Empire fleet has appeared in the same solar system, ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF958D1"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Rebel fleet is on the run. It consists of _m_ ships currently gathered around a single planet. Just a few seconds ago, the vastly more powerful Empire fleet has appeared in the same solar system, ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "叛军舰队正在逃亡。目前，共有 #cf_span[m] 艘飞船聚集在一颗行星周围。就在几秒钟前，实力远为强大的帝国舰队出现在同一星系中，叛军必须跃迁进入超空间。为了分散舰队，每艘飞船的船长独立地确定了该飞船将跃迁至的坐标。在叛军使用的过时导航系统中，该坐标以如下形式的算术表达式的值给出。\n\n为了规划抵抗运动的未来，海迪公主需要知道，每艘飞船跃迁后，有多少艘飞船会落在相同的坐标上。你是她唯一的希望！\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ m \\in \\mathbb{Z} $ be the number of ships.  \nFor each ship $ i \\in \\{1, \\dots, m\\} $, its jump coordinate is given by an expression of the form $ \\frac{a_i + b_i}{c_i} $, where...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments