Sözlər üzərində fal açmaq

Fal açan aparatlar pul atanlara hekayələr uydurması ilə məşhurdur. Bəzən bu proqnozlar həqiqətən də həyata keçir.

"Mocrosoft–Fortune" şirkəti yeni bir fal açan aparat hazırlayır. İstifadəçilər iki söz, $A$ və $B$ verirlər və aparat bu fürsət nəticəsində üçüncü bir söz $C$ hazırlayır. Bu söz $A$ və $B$-nin hərflərindən ibarət olur və həmin hərflərin aparat tərəfindən düzülüşü onların orijinal sözlərdəki sırasını qoruyur. Aparat bu hərfləri $C$-də mümkün qədər səliqəli düzür ki, nəticədə ardıcıl hərf cütlərinin əlifba sırasına tərs düşməsi (yəni, azalan sıralı olması) minimum olsun. "Mocrosoft–Fortune" proqramçılarına bu işdə kömək edin.

Sizə yalnız böyük latın hərflərindən (\{\mathbf{A}, \mathbf{B}, \ldots, \mathbf{Z}\}) ibarət iki söz $A$ və $B$ verilir. Sizin vəzifəniz $B$ sözünün hərflərini $A$-nın hərfləri arasına, $B$-dəki sıralanını pozmadan yerləşdirməkdir. Məqsəd, nəticədə alınan $C$ sözündə ardıcıl iki hərfin azalan əlifba sırasına düşdüyü cütlərin sayını mümkün qədər azaltmaqdır.

\mathbf{Nümunə:} Tutaq ki, A = \mathbf{opq} və B = \mathbf{leti}. Ən yaxşı fal proqnozu C = \mathbf{LopqETI} olardı. Burada $\mathbf{lopq}$ və $\mathbf{et}$ azalmayan əlifba sırası ilədir, ancaq $\mathbf{qe}$ və $\mathbf{ti}$ azalan ardıcıl cüt təşkil edir, yəni iki azalan cüt var.