Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Полный перебор

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

19/07/2013 | Лето 2013-13 (A) |

*Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

Mirko-wan has just received the results of his history exam. One of the problems was putting famous
historical battles into chronological order. The correct order was:

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

Mirko-wan has studied (relatively) hard for the exam, so he remembered the exact years of all battles,
except for the Blockade of Naboo. He couldn't remember anything about it, so he randomly placed it
last instead of first, obtaining the 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 doesn't match the correct solution at any index, Mirko-wan's score on that
problem was – to his disappointment – 0 out of 5 points, even though he knew the correct order of
four out of five battles!

This opens the question of fair scoring of an ordering problem. The example given above suggests that
scoring by counting the number of items in the correct absolute position isn't fair. Is there a better way?
One possibility is finding the longest subsequence (not necessarily contiguous) of correctly ordered
items. This isn't the best solution either: if an item is displaced by just one position from the correct
order, the score that it awards drops to zero, even though it was almost correctly ordered.

Mirko-wan has thus suggested (using the MAWT – Might As Well Try approach) the
following scoring method to his history teacher. For every two items, the student will receive 1 point
if the two items are in mutually correct order. In other words, the number of points is the number of
item pairs that the student has correctly ordered. The maximum number of points is then, of course,
the total number of pairs, which equals `N\ \ *\ (N\ \ -\ \ 1)\ /\ 2`, where `N` is the total number of entries.

The first line of input contains the positive integer `N` (`2\ ≤\ N\ ≤\ 2500`), the number of items. The items
are distinct words consisting of 3 to 15 lowercase English letters.

The second line of input contains the `N` items, space-separated, listed in the correct order.

The third line of input contains the `N` items, space-separated, listed in Mirko-wan's order.

The first and only line of output must contain, with no spaces, the following: the number of points that
Mirko-wan would earn using his scoring method, a '`/`' (forward slash) character, and the maximum
possible number of points for that problem (again assuming Mirko-wan's scoring method). (This is the
usual notation found on a typical graded exam.)

Sample Input #1

3 alpha beta gamma alpha gamma beta

Sample Output #1

2/3

Sample Input #2

5 naboo geonosis yavin hoth endor geonosis yavin hoth endor naboo

Sample Output #2

6/10