시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 32 MB 1 1 (100%) 1
문제
밀코-완은 자신의 역사시험의 결과를 받았다. 문제들 중 하나는 유명한 역사적 전투들을 연대순으로 나열하는것이다. 올바른 정답은 : ``` 1. 나부 봉쇄 2. 지오노시스 전투 3. 야빈 전투 4. 호스 전투 5. 엔돌 전투 ``` 밀코-완은 열심히 시험공부를 했고, 나부 봉쇄를 제외한 모든 전투들의 정확한 년도를 기억했다. 그는 이것에 대해서는 아무것도 기억하지 못했고, 임의로 끼워넣어서 이것을 처음 대신에 마지막으로 끼워넣었다. ``` 1. 지오노시스 전투 2. 야빈 전투 3. 호스 전투 4. 엔돌 전투 5. 나부 봉쇄 ``` 밀코-완의 순서는 올바른 정답과 어떤 위치도 맞지 않았고, 밀코-완의 이 문제에서의 점수는 - 그를 실망시켰다 - 그가 다섯 전투들 중 네개를 정확히 알고있었음에도 불구하고, 5점중에 0점을 맞았다! 이것은 순서배열 문제에서 공평한 배점방법이 무엇인지에 대한 질문을 하게만들었다. 위의 예시에서 주어진 것처럼 정확한 절대 위치에 올바른 답을 썼는지 숫자를 세서 점수를 주는것은 공평하지 않다. 더 좋은 방법이 있을까? 한가지 방법은 실제 올바른 순서와 가장 긴 부분수열(연속적일 필요는 없음)이다. 이것이 가장 좋은 해결책은 아니다: 만약 하나의 항목이 올바른 순서에서 단 하나의 위치만 잘못되는 경우, 순서가 거의 맞았음에도 불구하고 이것의 점수는 0이된다. 밀코-완은 그래서 (심리트릭을 이용하여 시도하였다) 그의 역사 선생에게 아래의 점수 채점방법을 제안하였다. 모든 두 항목쌍에 대해서, 두 항목이 올바른 순서로 되어있으면 1점을 얻는다. 다른말로 하면, 점수는 학생이 순서를 올바르게 배치한 항목쌍의 갯수와 같다. 최대 점수는, 당연히, 전체 쌍의 종류수이며, 이는 N을 항목들의 총 갯수라 했을 때 N*(N-1)/2이다.
입력
첫번째 줄에 양의정수 N (2<=N<=2500), 항목갯수가 주어진다. 각 항목들은 3에서 10자의 영어 소문자로 이루어진 서로다른 단어들이다. 두번째 줄에는 정답 순서인 N개의 항목 목록이 공백으로 구분되어 주어진다. 세번째 줄에는 밀코-완의 순서인 N개의 항목 목록이 공백으로 구분되어 주어진다.
출력
첫번째 줄에 단 하나의 줄에 공백없이 밀코-완이 그의 채점방식으로 얻은 점수와, 하나의 / (사선) 문자, 그리고 이 문제에서 가능한 최대 점수를 출력한다. (다시 밀코-완의 채점방식을 가정했을때이다.) (이것은 전형적인 채점 시험에서 일반적인 표기법이다.)
힌트
입력예제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 ``` 첫번째 예제 설명 : 밀코 완은 (alpha, beta)와 (alpha, gamma)의 쌍에서 점수를 얻는다.