## 1179 Chemical Equation – PAT甲级真题

chemical equation is the symbolic representation of a chemical reaction in the form of symbols and formulae, wherein the reactant entities are given on the left-hand side and the product entities on the right-hand side. For example, CH4​+2O2​=CO2​+2H2​O means that the reactants in this chemical reaction are methane and oxygen: CH4​ and O2​, and the products of this reaction are carbon dioxide and water: CO2​ and H2​O.

Given a set of reactants and products, you are supposed to tell that in which way we can obtain these products, provided that each reactant can be used only once. For the sake of simplicity, we will consider all the entities on the right-hand side of the equation as one single product.

### Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤20), followed by N distinct indices of reactants. The second line gives an integer M (1≤M≤10), followed by M distinct indices of products. The index of an entity is a 2-digit number.

Then a positive integer K (≤50) is given, followed by K lines of equations, in the format:

reactant_1 + reactant_2 + … + reactant_n -> product

where all the reactants are distinct and are in increasing order of their indices.

Note: It is guaranteed that

• one set of reactants will not produce two or more different products, i.e. situation like `01 + 02 -> 03` and `01 + 02 -> 04` is impossible;
• a reactant cannot be its product unless it is the only one on the left-hand side, i.e. `01 -> 01` is always true (no matter the equation is given or not), but `01 + 02 -> 01` is impossible; and
• there are never more than 5 different ways of obtaining a product given in the equations list.

### Output Specification:

For each case, print the equations that use the given reactants to obtain all the given products. Note that each reactant can be used only once.

Each equation occupies a line, in the same format as we see in the inputs. The equations must be print in the same order as the products given in the input. For each product in order, if the solution is not unique, always print the one with the smallest sequence of reactants — A sequence { a1​,⋯,am​ } is said to be smaller than another sequence { b1​,⋯,bn​ } if there exists 1≤imin(m,n) so that aj​=bj​ for all j<i, and ai​<bi​.

It is guaranteed that at least one solution exists.

### Sample Input:

8 09 05 03 04 02 01 16 10
3 08 03 04
6
03 + 09 -> 08
02 + 08 -> 04
02 + 04 -> 03
01 + 05 -> 03
01 + 09 + 16 -> 03
02 + 03 + 05 -> 08

### Sample Output:

02 + 03 + 05 -> 08
01 + 09 + 16 -> 03
04 -> 04

## 1178 File Path – PAT甲级真题

The figure shows the tree view of directories in Windows File Explorer. When a file is selected, there is a file path shown in the above navigation bar. Now given a tree view of directories, your job is to print the file path for any selected file.

### Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤10^3), which is the total number of directories and files. Then N lines follow, each gives the unique 4-digit ID of a file or a directory, starting from the unique root ID `0000`. The format is that the files of depth d will have their IDs indented by d spaces. It is guaranteed that there is no conflict in this tree structure.

Then a positive integer K (≤100) is given, followed by K queries of IDs.

### Output Specification:

For each queried `ID`, print in a line the corresponding path from the root to the file in the format: `0000->ID1->ID2->...->ID`. If the `ID` is not in the tree, print `Error: ID is not found.` instead.

### Sample Input:

14
0000
1234
2234
3234
4234
4235
2333
5234
6234
7234
9999
0001
8234
0002
4 9999 8234 0002 6666

### Sample Output:

0000->1234->2234->6234->7234->9999
0000->1234->0001->8234
0000->0002

## 1177 Subsequence in Substring – PAT甲级真题

substring is a continuous part of a string. A subsequence is the part of a string that might be continuous or not but the order of the elements is maintained. For example, given the string `atpaaabpabtt``pabt` is a substring, while `pat` is a subsequence.

Now given a string S and a subsequence P, you are supposed to find the shortest substring of S that contains P. If such a solution is not unique, output the left most one.

### Input Specification:

Each input file contains one test case which consists of two lines. The first line contains S and the second line PS is non-empty and consists of no more than 104 lower English letters. P is guaranteed to be a non-empty subsequence of S.

### Output Specification:

For each case, print the shortest substring of S that contains P. If such a solution is not unique, output the left most one.

atpaaabpabttpcat
pat

pabt

## 1176 The Closest Fibonacci Number – PAT甲级真题

The Fibonacci sequence Fn​ is defined by Fn+2​=Fn+1​+Fn​ for n≥0, with F0​=0 and F1​=1. The closest Fibonacci number is defined as the Fibonacci number with the smallest absolute difference with the given integer N.

Your job is to find the closest Fibonacci number for any given N.

### Input Specification:

Each input file contains one test case, which gives a positive integer N (≤10^8).

### Output Specification:

For each case, print the closest Fibonacci number. If the solution is not unique, output the smallest one.

305

233

### Hint:

Since part of the sequence is { 0, 1, 1, 2, 3, 5, 8, 12, 21, 34, 55, 89, 144, 233, 377, 610, … }, there are two solutions: 233 and 377, both have the smallest distance 72 to 305. The smaller one must be printed out.

atpaaabpabttpcat
pat

pabt

305

233