AT_ahc047_a [AHC047A] Lovely Language Model

Takahashi has $ N $ favorite strings. The $ i $ -th string is denoted by $ S_i $ , and its preference is $ P_i $ . Each $ S_i $ consists only of lowercase English letters from `a` to `f`. Recently, Takahashi has become interested in probabilistic models for generating strings. He wants to design a generation model, called the **Lovely Language Model (LLM)**, that generates the strings he likes with high probability. This model consists of $ M $ states. Assign a single lowercase letter $ C_i $ from `a` to `f` to each state $ i $ ( $ 0 \leq i < M $ ). Additionally, for each pair of states $ (i, j) $ , define the transition probability from state $ i $ to state $ j $ as an integer $ A_{i,j} $ , which represents a percentage value. These values must satisfy the following condition for all $ i $ : \\\[ \\sum\_{j=0}^{M-1} A\_{i,j} = 100 \\\] The model starts from state $ 0 $ and stops after generating a string of length $ L $ . The first character of the generated string is the character assigned to state $ 0 $ , namely $ C_0 $ . Then, the model performs state transitions according to the transition probabilities, outputting the character assigned to each newly transitioned state in order. For each string $ S_i $ , if it appears **at least once** as a contiguous substring in the generated string, Takahashi gains its corresponding preference $ P_i $ . Your task is to design the character assignment $ C_0, C_1, \dots, C_{M-1} $ and transition matrix $ A $ to maximize the expected total preference.

Input is given from Standard Input in the following format: > $ N $ $ M $ $ L $ $ S_0 $ $ P_0 $ $ S_1 $ $ P_1 $ $ \vdots $ $ S_{N-1} $ $ P_{N-1} $ - $ N $ is the number of strings. It is fixed at $ N = 36 $ in all test cases. - $ M $ is the number of states in the model. It is fixed at $ M = 12 $ . - $ L $ is the length of the string to be generated. It is fixed at $ L = 10^6 $ . - Each $ S_i $ is a string consisting of lowercase English letters from `a` to `f`, with length satisfying $ 6 \leq |S_i| \leq 12 $ . - Each preference $ P_i $ is a positive integer satisfying $ 1 \leq P_i \leq 17000 $ . - All $ S_i $ are distinct.

In the designed model, let $ C_i $ be the character assigned to state $ i $ , and $ A_{i,j} $ be the transition probability from state $ i $ to state $ j $ . Then, output to Standard Output in the following format: > $ C_0 $ $ A_{0,0} $ $ \cdots $ $ A_{0,M-1} $ $ \vdots $ $ C_{M-1} $ $ A_{M-1,0} $ $ \cdots $ $ A_{M-1,M-1} $ - Each $ C_i $ must be one of the lowercase letters from `a` to `f`. - Each $ A_{i,j} $ must be an integer satisfying $ 0 \leq A_{i,j} \leq 100 $ , and for every $ i $ , the following condition must hold: \\\[ \\sum\_{j=0}^{M-1} A\_{i,j} = 100 \\\] Your program may output multiple solutions. If multiple solutions are output, only the last one is used for scoring. You can compare multiple solutions using the web version of the visualizer. [Show example](https://img.atcoder.jp/ahc047/cHmFekjC.html?lang=en&seed=0&output=sample)

### Scoring Let $ Q_i $ be the probability that the generated string of length $ L $ contains the string $ S_i $ **at least once** as a contiguous substring. Then, your score is calculated as follows: \\\[ \\mathrm{round}\\left(\\sum\_{i=0}^{N-1} P\_i \\cdot Q\_i\\right) \\\] There are $ 150 $ test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time. ### Input Generation $ \mathrm{rand}(L, U) $ : Generates a uniformly random integer between $ L $ and $ U $ , inclusive. #### Generation of Strings $ S_i $ For each $ S_i $ , determine its length $ \ell_i $ using $ \ell_i = \mathrm{rand}(6, 12) $ , then generate a string of length $ \ell_i $ as follows: - Randomly select $ \ell_i $ characters from the letters `a` to `f` and concatenate them. - The same character may appear multiple times. If the generated string $ S_i $ is identical to any previously generated string, restart the generation from the length selection step. #### Generation of Preferences $ P_i $ For each string $ S_i $ , generate its corresponding preference $ P_i $ as follows: - Compute the upper bound $ U_i = \left\lfloor 1.5^{2 \cdot \ell_i} \right\rfloor $ . - Generate $ P_i = \mathrm{rand}(1, U_i) $ uniformly at random. Repeat this process independently to generate $ N = 36 $ pairs of $ (S_i, P_i) $ . ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc047/cHmFekjC.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc047/cHmFekjC.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc047/cHmFekjC_windows.zip): If you are not familiar with the Rust language environment, please use this instead. Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.