P9087 "SvR-2" Notes.

> In this problem, “substring” means: > > If there is a segment of **continuous** characters in a string $s$ that forms a string $p$, then $p$ is a substring of $s$. We use a string to represent a sheet music score, and use a character to represent each note. We define an “accent” as the occurrence of two **consecutive** identical characters in the sheet music. For example, there are $4$ “accents” in $\tt eeeee$. Now Sept is going to write a sheet music of length $n$ for Tpes to see. His evaluation rules are as follows: - Each time an “accent” appears in the sheet music, his anger value increases by $a$. - For each substring of length $k$ that contains no “accent”, his anger value increases by $b$. Given $n,k,a,b$, please help Sept construct a sheet music such that Tpes’s anger value $x$ is **minimized**.

**This problem has multiple test cases.** The first line contains an integer $T$, indicating the number of test cases. The next $T$ lines each contain four integers $n,k,a,b$, with meanings as described in the statement.

Output a total of $2 \cdot T$ lines. For each test case, output two lines: - Line 1: Tpes’s minimum anger value $x$. - Line 2: The sheet music you constructed.

#### Constraints and Notes **This problem uses bundled testdata.** | $\bf{Subtask}$ | $\bm{n\le}$ | $\bm{\sum n\le}$ | $\bm{T\le}$ | $\bf{Score}$ | | :-: | :-: | :-: | :-: | :-: | | $\sf 1$ | $6$ | $10$ | $3$ | $\tt 10$ | | $\sf 2$ | $10^3$ | $2\times 10^3$ | No special limit | $\tt 30$ | | $\sf 3$ | No special limit | No special limit | No special limit | $\tt 60$ | For $100\%$ of the testdata, $2\le T\le 100$, $2\le n,k\le 10^5$, $1\le a,b\le 10^9$. Within a single test case, it is guaranteed that $\sum n\le 2\times 10^5$. #### Output Notes Outputting $x$ and constructing the sheet music can be considered as two separate subtasks. If you can only finish one of them, please use **a valid character or number** as a placeholder in the position corresponding to the other subtask. You may output any characters in the sheet music, including digits, uppercase and lowercase letters, etc., but **spaces are not allowed**. #### Special Judge Return Message Explanation This problem uses a Special Judge to determine whether your answer is correct. checker.cpp will return messages in the form $\texttt{Score=}\text A,\texttt{Type=}\text B$. The $\tt Score$ category indicates your scoring status. $\text A$ can take the following values: - $\text A=1$, meaning:\ $\text{Accepted.} \texttt{ Your Ans and SM are both proper.}$\ This means all $T$ answers meet the requirements. - $\text A=2$, meaning:\ $\text{Partially Correct.}\texttt{ All Ans are right.}$\ This means in this test point, all your reported $x$ are correct, and you can get $20\%$ of the score for this test point. - $\text A=3$, meaning:\ $\text{Partially Correct.}\texttt{ You pass 70\% tests!}$\ This means in this test point, the number of test cases you answered correctly is **at least** $\lfloor0.7\times T\rfloor$ (both $x$ and the sheet music meet the requirements), and you can get $10\%$ of the score for this test point. - $\text A=4$, meaning you can only get $0$ points for this test point. The $\tt Type$ category indicates your error type. $\text B$ can take the following values: - $\text B=0$, meaning all your answers are correct, paired with $\text A=1$. - $\text B=1$, meaning:\ $\text{Wrong Answer.}\texttt{ The length of your SM is not right!}$\ This means in one test case, the length of the sheet music you constructed is not $n$. - $\text B=2$, meaning:\ $\text{Wrong Answer.}\texttt{ Your Ans is not right!}$\ This means in one test case, the value of $x$ you output is wrong. - $\text B=3$, meaning:\ $\text{Wrong Answer.}\texttt{ Your Ans and SM are not matched!}$\ This means in one test case, the anger value produced by your constructed sheet music is not $x$. Here, $\text{Ans, SM}$ stand for Answer (the value of $x$) and Sheet Music (the sheet music). Note that $\tt Type$ only reflects the type of the **first error** in this test point. Translated by ChatGPT 5