Languages Interactive 컴파일 명령
| 시간 제한 | 메모리 제한 | 제출 횟수 | 통과한 사람 수 | 비율 |
|---|---|---|---|---|
| 10000 ms | 256 MiB | 1605 | 31 | 1.93% |
당신은 위키백과에서 발췌한 문자열들(아래 예시 참고) 중 하나가 순서대로 주어지면, 그 언어를 차례대로 추측하는 대화형 프로그램을 작성하려 한다. 한 번 언어를 추측을 할 때마다 프로그램에 올바른 답이 제공되어, 학습을 통해 갈수록 더 추측을 잘 할 수 있게 한다.
각 언어들은 $0$부터 $55$사이의 정수인 $L$로 표현된다. 각 문자열들은 정확히 $100$개의 문자로 이루어져 있으며, $1$부터 $65535$사이의 정수 $100$개로 이루어진 배열 $E$로 표현된다. 이 $1$부터 $65535$사이의 정수들은 임의로 배정된 것으로, 어떤 표준 인코딩에도 부합하지 않는다.
당신은 함수 excerpt(E)를 구현해야 하는데, E는 위에 설명된 바와 같이 위키백과에서 발췌한 한 문자열을 나타내는 $100$개의 정수로 이루어진 배열이다. 당신이 구현한 함수는 반드시 language(L)을 정확히 한 번 호출해야 하는데, $L$은 $E$가 발췌된 위키백과의 언어를 당신이 추측한 것이다. language(L)은 채점 서버에 구현되어 있으며, 당신의 추측에 대해 점수를 매기고, 올바른 답을 리턴한다. 즉, language(L)$ = L$인 경우 추측이 맞은 것이다.
채점 서버는 입력 파일에 있는 각 문자열에 대해 한 번씩, 총 $10,000$번 excerpt(E)를 호출한다. 당신이 구현한 함수의 정확도는 excerpt(E)가 언어를 올바르게 추측한 비율이다.
당신은 이 문제를 풀 때 그 어떤 방법도 사용할 수 있다. Rocchio’s method는 약 $0.4$의 정확도를 내는 접근법이다. Rocchio’s method는 지금까지 등장한 각 언어들 $L$에 대해 $E$와의 유사도를 계산하여, 가장 유사한 언어를 찾는다. 유사도란 $E$의 문자들 중 언어 $L$의 이전 문자열들에서 등장하는 서로 다른 문자들의 개수로 정의된다.
유의할 점은, 입력 자료는 실제 위키백과 글들에서 다운로드되었고, 따라서 기형 문자들이나 문장 파편들이 종종 있을 수 있다. 이는 당연한 것으로, 이 문제의 일부분이다.
예시
단지 실례를 위해, $56$개 언어의 위키백과에서 발췌한 문자열들을 문자로 나타냈다. (원문 참고)
입력 파일 예시 grader.in.1은 이런 예들을 $10,000$개 담고 있다. $56$개 언어들은 IOI 2010 등록 데이터에 “모국어”로 기입된 것들이다. 각 문자열에 대해 이 $56$개 언어들 중 하나가 임의로 선택되었고, 각 문자열들은 해당 위키백과에서 임의로 선택된 글의 첫 문단에서 발췌되었다. 파일의 각 줄은 다음 내용들을 담고 있다.
- 위키백과 언어를 나타내는 두 문자의 ISO 코드
- 글의 첫 문단의 첫 $100$문자를 나타내는 $1$부터 $65535$사이의 정수 $100$개
- 해당 $100$문자를 텍스트 에디터나 Firefox 웹 브라우저에서 읽을 수 있게 한 문자 표현. 이는 단지 편의를 위한 것이며, 프로그램의 입력으로 쓰이기 위한 것이 아니다.
공식 채점기는 같은 $56$개 언어의 위키백과에서 같은 방식으로 선택된 서로 다른 $10,000$개의 문자열을 사용한다. 하지만, 채점기는 각 언어를 기존과 다른 $0$부터 $55$사이의 정수로 나타내고, 각 문자를 기존과 다른 $1$부터 $65535$사이의 정수로 나타낸다.
부분문제
부분문제 1 [30점]
당신의 제출은 반드시 채점 서버에서 $0.3$ 혹은 더 좋은 정확도롤 내야한다.
부분문제 2 [80점까지]
당신의 제출이 낸 정확도를 $\alpha$라고 할 때, 점수는 $114(\alpha-0.3)$을 반올림 한 것이다.
구현 세부사항
- 당신이 작성할 파일 :
lang.c혹은lang.cpp - 참가자 인터페이스 :
lang.h - 채점기 인터페이스 :
grader.h - 채점기 예시 :
grader.c혹은grader.cpp - 채점기 입력 예시 :
grader.in.1 - 예상되는 채점기 출력 예시 : 각 $10,000$개의 예제에 대해 모두 위에서 설명된 바와 같이
language를 호출했다면, 예시 채점기 출력은 OK alpha 와 같은 형식인데, 이 때 alpha는 정확도이다.