QOJ.ac

QOJ

Límite de tiempo: 1.0 s Límite de memoria: 32 MB Puntuación total: 80

#16632. POREDAK

Estadísticas

Mirko-wan 刚刚收到了他的历史考试成绩。其中一道题目要求将著名的历史战役按时间顺序排列。正确顺序为:

  1. Blockade of Naboo 2. Battle of Geonosis 3. Battle of Yavin 4. Battle of Hoth 5. Battle of Endor

Mirko-wan 为这次考试做足了(相对而言的)准备,因此他记住了除 Blockade of Naboo 之外所有战役的确切年份。他完全不记得关于这场战役的任何信息,于是他随机地将其排在了最后而不是最前,得到的顺序为:

  1. Battle of Geonosis 2. Battle of Yavin 3. Battle of Hoth 4. Battle of Endor 5. Blockade of Naboo

由于 Mirko-wan 的排序在任何位置上都与正确答案不匹配,因此他在该题上的得分——令他非常失望——是 5 分中的 0 分,尽管他实际上知道五场战役中四场的正确相对顺序!

这引发了关于排序题如何公平评分的问题。上述例子表明,通过计算处于正确绝对位置的元素个数来评分并不公平。有没有更好的方法?

一种可能性是寻找正确排序元素的最长子序列(不一定连续)。但这也不是最好的解决方案:如果一个元素仅比正确顺序偏移了一个位置,它所带来的分数就会降为零,尽管它几乎是正确排序的。

因此,Mirko-wan 向他的历史老师提出了一种新的评分方法(采用 MAWT——不妨试试心理战术(Might As Well Try a Mind Trick)的方法)。对于任意两个元素,如果这两个元素之间的相对顺序正确,学生将获得 1 分。换句话说,得分就是学生排序正确的元素对(pair)的数量。当然,最大可能得分就是总对数,即 $N \times (N - 1) / 2$,其中 $N$ 是总元素个数。

输入格式

输入的第一行包含一个正整数 $N$($2 \le N \le 2500$),表示元素的数量。这些元素是互不相同的单词,由 3 到 15 个小写英文字母组成。

输入的第二行包含 $N$ 个元素,用空格隔开,按正确顺序排列。

输入的第三行包含 $N$ 个元素,用空格隔开,按 Mirko-wan 的排序排列。

输出格式

输出的第一行也是唯一一行必须包含(不含空格):Mirko-wan 使用他的评分方法所能获得的分数、一个斜杠字符 /,以及该题的最大可能得分(同样基于 Mirko-wan 的评分方法)。(这是典型阅卷考试中常见的记分格式。)

样例

输入样例 1

3
alpha beta gamma
alpha gamma beta

输出样例 1

2/3

输入样例 2

5
naboo geonosis yavin hoth endor
geonosis yavin hoth endor naboo

输出样例 2

6/10

说明

样例 1 说明:Mirko-wan 凭借元素对 (alpha, beta)(alpha, gamma) 获得了分数。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.