D. Robot Vacuum Cleaner

Codeforces

IDCF922D

Time1000ms

Memory256MB

Difficulty—

greedysortings

English · Original

Chinese · Translation

Formal · Original

Pushok the dog has been chasing Imp for a few hours already. <center>![image](https://espresso.codeforces.com/8349588abe648162884b78b5b42f99880b695f4e.png)</center>Fortunately, Imp knows that Pushok is afraid of a robot vacuum cleaner. While moving, the robot generates a string _t_ consisting of letters '_s_' and '_h_', that produces a lot of noise. We define _noise_ of string _t_ as the number of occurrences of string "_sh_" as a **subsequence** in it, in other words, the number of such pairs (_i_, _j_), that _i_ < _j_ and and . The robot is off at the moment. Imp knows that it has a sequence of strings _t__i_ in its memory, and he can arbitrary change their order. When the robot is started, it generates the string _t_ as a concatenation of these strings in the given order. The noise of the resulting string equals the noise of this concatenation. Help Imp to find the maximum noise he can achieve by changing the order of the strings. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 105) — the number of strings in robot's memory. Next _n_ lines contain the strings _t_1, _t_2, ..., _t__n_, one per line. It is guaranteed that the strings are non-empty, contain only English letters '_s_' and '_h_' and their total length does not exceed 105. ## Output Print a single integer — the maxumum possible _noise_ Imp can achieve by changing the order of the strings. [samples] ## Note The optimal concatenation in the first sample is _ssshhshhhs_.

Pushok 这只狗已经追了 Imp 几个小时了。幸运的是，Imp 知道 Pushok 害怕机器人吸尘器。在移动过程中，机器人会生成一个由字母 '_s_' 和 '_h_' 组成的字符串 #cf_span[t]，产生大量噪音。我们定义字符串 #cf_span[t] 的 _噪音_ 为子序列 "_sh_" 的出现次数，换句话说，是满足 #cf_span[i < j] 且 #cf_span[t[i] = 's'] 和 #cf_span[t[j] = 'h'] 的所有有序对 #cf_span[(i, j)] 的数量。机器人目前处于关闭状态。Imp 知道机器人内存中有一组字符串 #cf_span[ti]，他可以任意改变它们的顺序。当机器人启动时，它会按给定顺序将这些字符串拼接成一个字符串 #cf_span[t]。所得字符串的噪音等于该拼接结果的噪音。请帮助 Imp 找出通过改变字符串顺序所能获得的最大噪音。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 机器人内存中字符串的数量。接下来 #cf_span[n] 行，每行包含一个字符串 #cf_span[t1, t2, ..., tn]。保证所有字符串非空，仅包含英文字符 '_s_' 和 '_h_'，且总长度不超过 #cf_span[105]。请输出一个整数 —— Imp 通过重新排列字符串所能获得的最大可能噪音。第一个样例的最优拼接结果为 #cf_span[ssshhshhhs]。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 机器人内存中字符串的数量。接下来 #cf_span[n] 行，每行包含一个字符串 #cf_span[t1, t2, ..., tn]。保证所有字符串非空，仅包含英文字符 '_s_' 和 '_h_'，且总长度不超过 #cf_span[105]。 ## Output 请输出一个整数 —— Imp 通过重新排列字符串所能获得的最大可能噪音。 [samples] ## Note 第一个样例的最优拼接结果为 #cf_span[ssshhshhhs]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of strings. Let $ T = \{t_1, t_2, \dots, t_n\} $ be a multiset of non-empty strings over the alphabet $ \{s, h\} $. For a string $ t $, define: - $ s(t) $: number of `'s'` characters in $ t $, - $ h(t) $: number of `'h'` characters in $ t $, - $ sh(t) $: number of occurrences of `'sh'` as a subsequence in $ t $. For a concatenation $ t = t_{\sigma(1)} t_{\sigma(2)} \cdots t_{\sigma(n)} $ induced by permutation $ \sigma \in S_n $, the total noise is: $$ \text{noise}(t) = \sum_{i=1}^n sh(t_{\sigma(i)}) + \sum_{1 \le i < j \le n} s(t_{\sigma(i)}) \cdot h(t_{\sigma(j)}) $$ **Constraints** 1. $ 1 \le n \le 10^5 $ 2. Each $ t_i $ is non-empty and contains only characters `'s'` and `'h'` 3. $ \sum_{i=1}^n |t_i| \le 10^5 $ **Objective** Maximize $ \text{noise}(t) $ over all permutations $ \sigma \in S_n $: $$ \max_{\sigma \in S_n} \left( \sum_{i=1}^n sh(t_{\sigma(i)}) + \sum_{1 \le i < j \le n} s(t_{\sigma(i)}) \cdot h(t_{\sigma(j)}) \right) $$

Samples

Input #1

4
ssh
hs
s
hhhs

Output #1

Input #2

2
h
s

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Robot Vacuum Cleaner",
    "description": {
      "content": "Pushok the dog has been chasing Imp for a few hours already. <center>![image](https://espresso.codeforces.com/8349588abe648162884b78b5b42f99880b695f4e.png)</center>Fortunately, Imp knows that Pushok ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF922D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Pushok the dog has been chasing Imp for a few hours already.\n\n<center>![image](https://espresso.codeforces.com/8349588abe648162884b78b5b42f99880b695f4e.png)</center>Fortunately, Imp knows that Pushok ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Pushok 这只狗已经追了 Imp 几个小时了。\n\n幸运的是，Imp 知道 Pushok 害怕机器人吸尘器。\n\n在移动过程中，机器人会生成一个由字母 '_s_' 和 '_h_' 组成的字符串 #cf_span[t]，产生大量噪音。我们定义字符串 #cf_span[t] 的 _噪音_ 为子序列 \"_sh_\" 的出现次数，换句话说，是满足 #cf_span[i < j] 且 #cf_span[t[i...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of strings.  \nLet $ T = \\{t_1, t_2, \\dots, t_n\\} $ be a multiset of non-empty strings over the alphabet $ \\{s, h\\} $.  \nFor a string $ t $, d...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments