No.2590 100000 Days of Christmas

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.2590 100000 Days of Christmas

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 74
作問者 :

magurofly / テスター : 👑

p-adic

1 ProblemId : 10373 / 出題時の順位表 / 自分の提出

問題文最終更新日: 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×1
Div. 2×1、ECR×2
Div. 2×1、ECR×2、Petrozavodsk Contest×3
Div. 2×5、ECR×2、Petrozavodsk Contest×3
Div. 2×5、ECR×2、Petrozavodsk Contest×3、yukicoder×5
ABC×6、Div. 2×5、ECR×2、Petrozavodsk Contest×3、yukicoder×5
ABC×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もしくは右上の雲マークをクリックしてアカウントを作成してください。