問題一覧 > 通常問題

No.2590 100000 Days of Christmas

レベル : / AI推定難易度 : 550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 76
作問者 : 👑 magurofly / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10373 / 自分の提出
問題文最終更新日: 2023-11-24 19:43:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2023 (順位表) の他の問題:

Problem Statement

For $N$ days starting from Christmas of $2023$, magurofly gives presents to p-shin Daisuki bot every day. The presents given on day $i$ are $i$ copies of $S_i$ and, when $i \ge 2$, additionally all of the presents given on day $i-1$.

Find how many of each present p-shin Daisuki bot receives in the end.

Input

$N\\S_1\\S_2\\\vdots\\S_N$
  • $N$ is an integer.
  • $1 \le N \le 10^5$
  • $S_i$ is a string consisting of characters whose ASCII codes are between 0x20 and 0x7e, inclusive.
  • The last character of $S_i$ is not a space.
  • $1 \le |S_i| \le 100$
  • $\sum_i |S_i| \le 10^6$

If you use C++, note that reading a string with cin >> stops at a space.

Output

If $K$ kinds of presents are given in total, print $K$ lines.

When the names of the presents are arranged in lexicographical (ascending) order, let $P_k$ be the $k$-th name. Also, let $C_k$ be the number of $P_k$ received as presents.

What is lexicographical order?

For strings $s, t$, the lexicographical order between them can be determined as follows.

  1. If there exists a minimum $i \in [1, \min\{|s|, |t|\}]$ such that $s_i \ne t_i$ in terms of ASCII codes, the order between $s$ and $t$ is the same as the order between $s_i$ and $t_i$.
  2. If no such $i$ exists, the order is the same as the order between $|s|$ and $|t|$.

Note that many major programming languages provide functions for sorting strings in lexicographical order. See the reference for each language for details.

For $k = 1, 2, \ldots, K$, print $C_k$ and $P_k$ separated by a space on the $k$-th line.

Sample

Sample 1
Input
7
Div. 2
ECR
Petrozavodsk Contest
Div. 2
yukicoder
ABC
joyacon
Output
12 ABC
23 Div. 2
12 ECR
15 Petrozavodsk Contest
7 joyacon
15 yukicoder

The presents received on each day are as follows:

  1. Div. 2×1
  2. Div. 2×1, ECR×2
  3. Div. 2×1, ECR×2, Petrozavodsk Contest×3
  4. Div. 2×5, ECR×2, Petrozavodsk Contest×3
  5. Div. 2×5, ECR×2, Petrozavodsk Contest×3, yukicoder×5
  6. ABC×6, Div. 2×5, ECR×2, Petrozavodsk Contest×3, yukicoder×5
  7. ABC×6, Div. 2×5, ECR×2, Petrozavodsk Contest×3, joyacon×7, yukicoder×5
Sample 2
Input
12
partridge in a pear tree
turtle dove
french hen
calling bird
golden ring
goose a-laying
swan a-swimming
maid a-milking
lady dancing
lord a-leaping
piper piping
drummer drumming
Output
36 calling bird
12 drummer drumming
30 french hen
40 golden ring
42 goose a-laying
36 lady dancing
30 lord a-leaping
40 maid a-milking
12 partridge in a pear tree
22 piper piping
42 swan a-swimming
22 turtle dove

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。