問題一覧 > 通常問題

No.2947 Sing a Song

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 89
作問者 : MichirakaraMichirakara / テスター : nouka28nouka28 rotti_coderrotti_coder t9unkubjt9unkubj
0 ProblemId : 11303 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-25 21:32:52

問題文

みちらから君は歌を歌うのが大好きです。

みちらから君は $N$ 小節からなり、$i$ 小節目に $A_i$ 個の音がある歌を歌うことにしました。

しかし、みちらから君は元の歌詞を忘れてしまったので、彼の好きな単語である $S$ と $T$ だけからなり、全ての音を歌う歌詞を作って歌を歌うことにしました。(音が空白になってはいけません)

$S$ を歌うには $|S|$ 個の音、 $T$ を歌うには $|T|$ 個の音が必要です。 ($|X|$ は文字列 $X$ の長さを表します。)

また、変更した歌詞の単語の途中で小節が変わってはいけません。

みちらから君は単語 $S$ の方が好きなので、$S$ を歌う回数を最大化した場合にみちらから君が歌う可能性のある歌詞のうち一つを各単語ごとに空白、各小節ごとに改行で区切って出力してください。

なお、与えられる入力について、条件を満たす歌詞が存在することは保証されています。

入力

$N$
$S$ $T$
$A_1$ $A_2$ $\dots$ $A_N$

制約

  • $1\leq N\leq 2\times 10^5$
  • $1\leq |S|,|T|\leq 2\times 10^5$
  • $S,T$ は英小文字列
  • $1\leq A_i\ (1\leq i \leq N)$
  • $1\leq \sum_{i=1}^{N}{A_i}\leq 2\times 10^5$
  • $N,A_i\ (1\leq i \leq N)$ は全て正整数
  • 条件を満たす歌詞が存在することは入力から保証される。(21:32:42 追記)

出力

みちらから君の歌う可能性のある歌詞を各単語を空白、各小節を改行で区切って出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4
og yhg
7 5 7 5
出力
og og yhg
og yhg
yhg og og
og yhg

サンプル2
入力
3
abc cde
6 6 6
出力
abc abc
abc abc
abc abc

サンプル3
入力
3
abcd e
7 9 13
出力
abcd e e e
abcd abcd e
abcd abcd abcd e

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