P7396 Automatic Exchange Machine (2021 CoE-I D)

The metro company of Mca City has decided to adopt a new measure: no need to buy tickets, just insert coins and board. It is rumored that this is to reduce the time passengers spend queuing to buy tickets. The metro operator contacted the city's Association for Computing Machinery (ACM), specifically the Automated Checkout Machine (ACM) company under it, and asked them to develop an Automatic exChange Machine (ACM) to meet passengers' needs. They hired you as the chief programmer to write the program for this machine. Inside the automatic exchange machine, there are coins of various denominations. When a passenger inserts a banknote into the machine, the machine will automatically exchange it into coins of equal value according to the coin denominations currently available. Of course, passengers do not want to carry a large pile of coins to squeeze into the metro, so the fewer coins, the better. If the existing coin denominations cannot complete the exchange, you should output one line of information telling the passenger to seek service at a manual counter.

**The input contains multiple test cases**. The first line contains an integer $T$, indicating the number of test cases. Each test case is one line: the first is an integer $c$, indicating the number of coin denomination types, followed by $c$ integers, where each integer $d_i（1 \leq i \leq c）$ denotes a coin denomination in cents, and finally a real number $m$, denoting the total value of the banknote to be exchanged, in dollars.

For each input line, output one line. If no exchange scheme exists, output `No solution.`. Otherwise, output an exchange scheme with the minimum number of coins in the following format: first output the total number of coins in the scheme, then a space, and then print the exchange sequence in the format shown in the samples, i.e., in increasing order of denomination, output each denomination used in the scheme and its corresponding number of coins. If there are multiple schemes with the minimum number of coins, output the scheme with the smallest lexicographical order (i.e., according to **[ASCII](https://baike.baidu.com/item/ASCII)** order).

#### Sample Explanation In the first test case, there are $6$ coin denominations: $1$ cent, $2$ cents, $5$ cents, $10$ cents, $20$ cents, and $50$ cents. You need to exchange $25.31$ dollars ($2531$ cents). The scheme with the minimum number of coins is: $50$ coins, $1$ coin of $1$ cent, $1$ coin of $10$ cents, $1$ coin of $20$ cents, and $50$ coins of $50$ cents. In the second test case, there are $5$ coin types, but only $4$ distinct denominations: $1$ cent, $2$ cents, $5$ cents, and $10$ cents. You need to exchange $0.18$ dollars ($18$ cents). The scheme with the minimum number of coins is: $4$ coins, $1$ coin of $1$ cent, $1$ coin of $2$ cents, $1$ coin of $5$ cents, and $1$ coin of $10$ cents. In the third test case, there are $5$ coin denominations: $1$ cent, $2$ cents, $5$ cents, $9$ cents, and $10$ cents. You need to exchange $0.18$ dollars ($18$ cents). The scheme with the minimum number of coins is: $2$ coins, $2$ coins of $9$ cents. In the fourth test case, there is no exchange scheme that meets the requirements. Output: `No solution.`. In the fifth test case, the minimum number of coins is $14$, and there are the following three exchange schemes: ```cpp 14 112*2+151*1+385*11 14 167*1+179*2+235*1+385*10 14 173*2+179*1+235*1+385*10 ``` According to the statement, the following is the lexicographically smallest scheme: ```cpp 14 112*2+151*1+385*11 ``` In the sixth test case, the minimum number of coins is $4$, and there are the following seven exchange schemes: ```cpp 4 52*2+189*1+362*1 4 82*1+122*1+166*1+285*1 4 95*2+180*1+285*1 4 95*2+205*1+260*1 4 95*1+166*1+189*1+205*1 4 122*1+164*2+205*1 4 122*1+164*1+180*1+189*1 ``` According to the statement, the following is the lexicographically smallest scheme: ```cpp 4 122*1+164*1+180*1+189*1 ``` ------------ #### Constraints and Conventions For $100\%$ of the testdata, $1 \leq T \leq 400，1 \leq c \leq 100$，$1 \leq d_i \leq 400$，$0 \lt m \leq 100$. The real number $m$ representing the total value of the banknote to be exchanged has three cases: no decimal point (an integer), one digit after the decimal point, or two digits after the decimal point. When outputting the exchange sequence, the same coin denomination should be merged. For example, suppose the correct output is: ```cpp 4 111*2+222*2 ``` Then the following outputs do not meet the requirements: ```cpp 4 111*1+111*1+222*2 4 111*2+222*1+222*1 4 111*1+111*1+222*1+222*1 ``` Translated by ChatGPT 5