No.295 hel__world
Problem Statement
The number of connected components of a string $S$ is defined as the length of the string after performing the following operation as many times as possible.
Operation: if there is a place where the same character appears 2 or more times in a row, remove 1 character from it.
For example, the number of connected components of "helloworld" is $9$, and that of "aababbaaa" is $5$.
The $T$-count of $S$ is defined as the number of subsequences $T$ contained in the string $S$.
For example, let $S$ be helloworld and $T$ be helworld. Since helloworld has the 2 subsequences hel__world and he_l_world, the helworld-count of helloworld is $2$.
You are given the number of characters of each letter in the string $S$, and the string $T$.
Find the maximum $T$-count over strings $S$ satisfying the following 2 conditions.
・The number of characters $alpha$ contained in $S$ is at most $S_{alpha}$
・The number of connected components of $S$ equals the number of connected components of $T$
Note that the answer can be very large, so if it is $2^{62}$ or greater, output "hel" instead.
Also, if no $S$ satisfying the 2 conditions exists, output $0$.
Input
$S_a$ $S_b$ $S_c$ $S_d$ $S_e$ $S_f$ $S_g$ $S_h$ $S_i$ $S_j$ $S_k$ $S_l$ $S_m$ $S_n$ $S_o$ $S_p$ $S_q$ $S_r$ $S_s$ $S_t$ $S_u$ $S_v$ $S_w$ $S_x$ $S_y$ $S_z$ $T$
$0 \le S_{alpha} \le 10^{18}$ ( $alpha \in \{a,\cdots, z\}$)
$1 \le |T| \le 10^6$
$S_{alpha}$ means that the string $S$ contains $S_{alpha}$ characters $alpha$.
The strings $S$,$T$ consist only of the characters $a,b,\cdots,z$ (lowercase letters).
Output
Output on one line the maximum $T$-count obtainable by rearranging $S$, or "hel".
Print a newline at the end.
Sample
Sample 1
Input
0 0 0 1 1 0 0 1 0 0 0 3 0 0 2 0 0 1 0 0 0 0 1 0 0 0 helworld
Output
4
In this case, $S$ is a string obtained by rearranging helloworld.
If $S$ is hellwoorld, the helworld-count is 4, which is the maximum.
Sample 2
Input
0 0 0 1 1 0 0 1 0 0 0 3 0 0 2 0 0 1 0 0 0 0 1 0 0 0 hello
Output
6
Considering strings with the same number of connected components as hello, the hello-count of helllooo is not used here; helloo-type arrangement helllo o is not needed: the hello-count of hellloo is 6, which is the maximum.
Sample 3
Input
100 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 abababababababababababababababab
Output
hel
If the answer is huge, output "hel".
Sample 4
Input
9 1 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 iauba
Output
1260
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
shimomire