Sáng Tác Bài Hát

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một xâu mẫu $P$ và độ dài $N$ . Hãy xây dựng xâu $S$ độ dài $N$ chỉ gồm $K$ ký tự đầu của bảng chữ cái tiếng Anh (tức các ký tự từ a đến ký tự thứ $K$ ), sao cho $P$ xuất hiện trong $S$ tại đúng các vị trí được chỉ định.

Cụ thể, cho xâu nhị phân $T$ độ dài $N - | P | + 1$ . Với mỗi $i$ từ $1$ đến $| T |$ :

Nếu $T_{i} = 1$ thì $P$ phải xuất hiện trong $S$ bắt đầu từ vị trí $i$ (tức $S_{i} S_{i + 1} \dots S_{i + | P | - 1} = P$ ).
Nếu $T_{i} = 0$ thì $P$ không được xuất hiện trong $S$ bắt đầu từ vị trí $i$ .

Lưu ý rằng các lần xuất hiện của $P$ có thể chồng lấn nhau.

Dữ liệu vào

Dòng $1$ : hai số nguyên $N$ và $K$ ( $1 \leq N \leq 100$ , $2 \leq K \leq 26$ ).
Dòng $2$ : xâu $P$ gồm các chữ cái thường trong $K$ ký tự đầu tiên của bảng chữ cái, $1 \leq | P | \leq N$ .
Dòng $3$ : xâu nhị phân $T$ độ dài $N - | P | + 1$ .

Dữ liệu ra

In ra xâu $S$ thỏa mãn yêu cầu. Nếu có nhiều đáp án, in ra một đáp án bất kỳ. Nếu không tồn tại, in ra No solution.

Ràng buộc

$1 \leq N \leq 100$
$2 \leq K \leq 26$
$1 \leq | P | \leq N$

Ví dụ

Input	Output	Giải thích
5 2 a 10001	abbba	$P =$ "a" phải xuất hiện tại vị trí $1$ và $5$ , không xuất hiện tại các vị trí khác. Xâu "abbba" thỏa mãn vì $S_{1} = S_{5} =$ a, còn $S_{2} = S_{3} = S_{4} =$ b.
5 2 aba 101	ababa	Hai lần xuất hiện chồng lấn tại vị trí $1$ và $3$ : $S_{1 . .3} =$ "aba" và $S_{3 . .5} =$ "aba" cùng dùng chung ký tự $S_{3} =$ a.
6 2 abba 101	No solution	Hai lần xuất hiện tại vị trí $1$ và $3$ buộc $S_{3}$ phải đồng thời bằng b (từ "abba" bắt đầu tại $1$ ) và bằng a (từ "abba" bắt đầu tại $3$ ), mâu thuẫn.

Bình luận

Không có bình luận tại thời điểm này.