No.2590 100000 Days of Christmas
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 69
作問者 :
magurofly
/ テスター :
👑 
p-adic
タグ : / 解いたユーザー数 69
作問者 :
magurofly
/ テスター :
👑 p-adic
問題文最終更新日: 2023-11-24 19:43:02
問題文
maguroflyくんは $2023$ 年のクリスマスからはじまる $N$ 日間、毎日p進大好きbotさんにプレゼントを贈ります。 $i$ 日目に贈るプレゼントは、 $S_i$ が $i$ 個と、 $i \ge 2$ のときはそれに加えて $i-1$ 日目に贈ったプレゼントすべてです。
最終的に、p進大好きbotさんはそれぞれのプレゼントをいくつもらえるか答えてください。
入力
$N\\S_1\\S_2\\\vdots\\S_N$
- $N$ は整数
- $1 \le N \le 10^5$
- $S_i$ は ASCII コードが
0x20以上0x7e以下の文字からなる文字列 - $S_i$ の末尾の文字は空白ではない
- $1 \le |S_i| \le 100$
- $\sum_i |S_i| \le 10^6$
C++ をご利用の方は、 cin >> で文字列を入力すると空白で途切れてしまうことにご注意ください。
出力
贈られたプレゼントが全部で $K$ 種類あるとき、 $K$ 行出力せよ。
プレゼントの名前を辞書順（昇順）に並べたとき、 $k$ 番目の名前を $P_k$ とする。また、プレゼントとして $P_k$ をもらった個数を $C_k$ とする。
辞書順とは？
文字列 $s, t$ に対して、辞書順での大小関係は以下のとおり判定することが可能です。
- ASCII コードにおいて $s_i \ne t_i$ となる最小の $i \in [1, \min\{|s|, |t|\}]$ が存在する場合、 $s$ と $t$ の大小関係は $s_i$ と $t_i$ の大小関係と等しい。
- そのような $i$ が存在しない場合、 $|s|$ と $|t|$ の大小関係と等しい。
なお、主要なプログラミング言語の多くでは、文字列の辞書順による並び替えの関数が存在します。詳しくは各言語のリファレンスをご参照ください。
$k = 1, 2, \ldots, K$ について、 $k$ 行目には $C_k$ と $P_k$ を空白区切りで出力せよ。
サンプル
サンプル1
入力
7 Div. 2 ECR Petrozavodsk Contest Div. 2 yukicoder ABC joyacon
出力
12 ABC 23 Div. 2 12 ECR 15 Petrozavodsk Contest 7 joyacon 15 yukicoder
それぞれの日にもらったプレゼントは以下のとおりです:
Div. 2×1Div. 2×1、ECR×2Div. 2×1、ECR×2、Petrozavodsk Contest×3Div. 2×5、ECR×2、Petrozavodsk Contest×3Div. 2×5、ECR×2、Petrozavodsk Contest×3、yukicoder×5ABC×6、Div. 2×5、ECR×2、Petrozavodsk Contest×3、yukicoder×5ABC×6、Div. 2×5、ECR×2、Petrozavodsk Contest×3、joyacon×7、yukicoder×5
サンプル2
入力
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
出力
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もしくは右上の雲マークをクリックしてアカウントを作成してください。