問題一覧 > 通常問題

No.2947 Sing a Song

レベル : / AI推定難易度 : 650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 125
作問者 : Michirakara / テスター : nouka28 rotti_coder t9unkubj
お気に入りにしたユーザー ProblemId : 11303 / 自分の提出
問題文最終更新日: 2024-10-25 21:32:52
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
yukicoder contest 451 (並木中等プログラミングコンテスト 2024) (順位表) の他の問題:

Problem Statement

Michirakara loves singing songs.

Michirakara has decided to sing a song consisting of $N$ measures, where the $i$-th measure has $A_i$ notes.

However, Michirakara has forgotten the original lyrics, so he has decided to make up lyrics consisting only of his favorite words $S$ and $T$ that sing all the notes, and sing the song with them. (No note may be left blank.)

Singing $S$ requires $|S|$ notes, and singing $T$ requires $|T|$ notes. ($|X|$ denotes the length of the string $X$.)

Also, a measure must not change in the middle of a word of the modified lyrics.

Since Michirakara prefers the word $S$, among the lyrics he might sing when the number of times he sings $S$ is maximized, output any one, separating words by spaces and measures by newlines.

It is guaranteed that lyrics satisfying the conditions exist for the given input.

Input

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

Constraints

  • $1\leq N\leq 2\times 10^5$
  • $1\leq |S|,|T|\leq 2\times 10^5$
  • $S,T$ are strings of lowercase English letters
  • $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)$ are all positive integers
  • It is guaranteed by the input that lyrics satisfying the conditions exist. (Added at 21:32:42)

Output

Output lyrics that Michirakara might sing, separating words by spaces and measures by newlines.

Print a newline at the end.

Sample

Sample 1
Input
4
og yhg
7 5 7 5
Output
og og yhg
og yhg
yhg og og
og yhg

Sample 2
Input
3
abc cde
6 6 6
Output
abc abc
abc abc
abc abc

Sample 3
Input
3
abcd e
7 9 13
Output
abcd e e e
abcd abcd e
abcd abcd abcd e

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