P7755 [COCI 2012/2013 #3] POREDAK

Mirko-wan has just received his history exam results. One of the questions was to arrange famous historical events in chronological order. The correct order is: 1. _Blockade of Naboo_ 2. _Battle of Geonosis_ 3. _Battle of Yavin_ 4. _Battle of Hoth_ 5. _Battle of Endor_ Mirko-wan studied relatively hard, so except for _Blockade of Naboo_, he remembers the exact year of every event. He does not remember anything about _Blockade of Naboo_, so he randomly put it last instead of first, getting the following order: 1. _Battle of Geonosis_ 2. _Battle of Yavin_ 3. _Battle of Hoth_ 4. _Battle of Endor_ 5. _Blockade of Naboo_ Since Mirko-wan’s order does not match the correct solution by any measure, even though he knows four-fifths of the correct order, to his disappointment he got $0$ points out of $5$ on this question! This raises the issue of fair grading.

The example above shows that scoring by counting how many items are in the correct absolute positions is unfair. Is there a better way? One possibility is to find the longest subsequence (not necessarily consecutive) of items that are in the correct relative order. This is still not the best solution: if one item is moved by only one position from the correct order, then even though the ordering is almost correct, the score may drop to zero. Therefore, Mirko-wan suggested the following grading method to his history teacher: For every pair of items among the $n$ items, if the relative order of the two items is correct, the student gets $1$ point. In other words, the score is the number of item pairs that the student ordered correctly. Of course, the maximum score is the total number of pairs, which is $\dfrac{n(n-1)}{2}$. Using this method, given the correct order of $n$ items and the order provided by Mirko-wan, compute the score Mirko-wan receives.

The input consists of three lines. The first line contains an integer $n$, the number of items. The second line contains $n$ strings, the correct order of the $n$ items. The third line contains $n$ strings, the order of the $n$ items given by Mirko-wan.

Output in the format `a/b`, where: - $a$ is the score Mirko-wan receives according to the given order and the new scoring method. - $b$ is the maximum possible score under the new scoring method. Note that in this problem, **do not reduce the fraction**.

**Sample 1 Explanation** For sample $1$, the item pairs that give Mirko-wan points are $(\texttt{alpha},\texttt{beta})$ and $(\texttt{alpha},\texttt{gamma})$. **Constraints** For all testdata, $2\leqslant n\leqslant 2500$. The string length is in $[3,15]$, consisting only of lowercase English letters, and all items are distinct. **Source** This problem is from **_[COCI 2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 3](https://hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf) T2 POREDAK_**. With the original testdata configuration, the full score is $80$ points. Translated and整理 (zhengli) provided by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5