문제 보기 - Languages (IOI10_languages)

시간 제한메모리 제한제출 횟수제출한 사람 수해결한 사람 수정답률
10000 ms256 MiB19061143228.07%

원문 링크

당신은 위키백과에서 발췌한 문자열들(아래 예시 참고) 중 하나가 순서대로 주어지면, 그 언어를 차례대로 추측하는 대화형 프로그램을 작성하려 한다. 한 번 언어를 추측을 할 때마다 프로그램에 올바른 답이 제공되어, 학습을 통해 갈수록 더 추측을 잘 할 수 있게 한다.

각 언어들은 $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$개 언어의 위키백과에서 발췌한 문자열들을 문자로 나타냈다.

  1. Yshokkie word meestal in Kanada , die noorde van die VSA en in Europa gespeel. Dit is bekend as 'n b
  2. المنتج الحدي Marginal Producer ، وهو المنتج الذي يجعل المنظم لا يكسب ربحا ولا يخسر ويحصل على دخل يكف
  3. "BAKILI" Futbol Klubu 1995-ci ildə Misir Səttаr oğlu Əbilov tərəfindən yаrаdılmış və həvəskаr futbol
  4. Квинт Фулвий Флак (Quintus Fulvius Flaccus; † 205 пр.н.е. ) e политик и генерал на Римската републик
  5. ইন্ডিয়ান ইনস্টিটিউট অফ সোশ্যাল ওয়েলফেয়ার অ্যান্ড বিজনেস ম্যানেজমেন্ট (সংক্ষেপে আইআইএসডব্লিউবিএম )
    1. juni ( lipanj ) ( 5.6. ) je 156. dan godine po gregorijanskom kalendaru (157. u prestupnoj godini
  6. La Caunette és un municipi francès , situat al departament de l' Erau i a la regió de Llenguadoc-Ros
  7. Praha je malé městečko v Texasu , které leží cca 85 km na jihozápad od Austinu . Bylo založeno
  8. Graeme Allen Brown (født 9. april 1979 i Darwin , Northern Territory , Australien ) er en australsk
  9. Der Plattiger Habach ( 3.214 m ü. A. , nach anderen Angaben nur 3.207 m [1] )
  10. Το Νησί Γκρέιτ Μπάρριερ ( Αγγλικά : Great Barrier Island , Μαορί : Motu Aotea ) είναι νησί στα βόρει
  11. Sid Bernstein Presents... is a 2010 feature-length documentary film by directors Jason Ressler and E
  12. El término latino lex loci celebrationis aplicado al derecho internacional privado quiere decir: "le
  13. Apollo 5 oli kosmoselaev , mis sooritas Apollo programmi teise mehitamata lennu. Lennu käigus testit
  14. سیارک ۱۳۵۰ (به انگلیسی : 1350 Rosselia ، نامگذاری :1934TA )‏ هزار و سیصد و پنجاهمین سیارک کشف شده‌اس
  15. V. I. Beretti (myös Vikenty Ivanovitš Beretti , alk. Vincent Beretti ; 1781 Milano Italia – 18. elok
  16. Le 5 e bataillon de parachutistes vietnamiens (ou 5 e BPVN ou encore 5 e Bawouan ) est une unité par
  17. Amina Sarauniyar Zazzau,, wadda ta rayu daga shekarar 1533 zuwa 1610, ɗaya ce daga cikin ‘ya'ya biyu
  18. ב מתמטיקה , השערת רימן היא השערה שהציע בשנת 1859 ה מתמטיקאי ברנרד רימן , מגדולי המתמטיקאים של אותה ע
  19. Sudski proces Doe protiv Boltona je sudski proces iz 1973 . godine kojim je američki Vrhovni sud uki
  20. Owen Cunningham Wilson ( 1968 . november 18. , Dallas , Texas , Egyesült Államok ) amerikai színész
  21. Հայ Կաթողիկե Եկեղեցին պատկանում է Արևելյան Կաթոլիկ Եկեղեցիներին և այսպիսով ենթարկվում է Հռոմի Պապի ա
  22. Dionysios dari Halicarnassus ( Bahasa Yunani : Διονύσιος Ἀλεξάνδρου Ἀλικαρνᾱσσεύς , Dionysios putra
  23. Nnamdi "Zik" Azikiwe , bu onye isi-ala izizi Nijiria nwere. Ochichi ya bidolu na afo 1954 welu ruo n
  24. La Riserva naturale orientata Serre della Pizzuta è un'area protetta del dipartimento Regionale di S
  25. 石橋和義 (いしばし かずよし/まさよし、生没年不詳)は、 �詳。 石橋氏 初代当主。初名氏義。 尾張 三郎を通称とし、官途は、 左近将監 → 三河守 → 左衛門佐 。 足利直義
  26. კორბინ ბლიუ ( ინგლ. Corbin Bleu ; დ. 21 თებერვალი , 1989 , დაბადების ადგილი ბრუკლინი , ნიუ-იორკი , ა
  27. Та́рья Ка́арина Ха́лонен (Tarja Kaarina Halonen)); 24 желтоқсан , 1943 , Каллио , Хельсинки , Финлан
  28. 딜롱 ( Dilong )은 중국 랴오닝(Liaoning) 지방의 익시안층(Yixian Formation)에서 온전한 4구의 화석으로 발견되었다. 이 공룡은 가장 원시적인 초기의 티
  29. Сүймөнкул Чокморов - советтик актёр. Жетинин айынын 9 (ноябрь) 1939-жылы, Фрунзе шаарын жанындагы Чо
  30. D' Mirjam vun Abellin war eng Nonn a Mystikerin , och " Maria vum gekräizegte Jesus " genannt. Si as
  31. Panopea abrupta ( angl. Geoduck ) - jūrinių dvigeldžių moliuskų rūšis, priklausanti Hiatellidae šeim
  32. "Dzimis Latvijā" ir Liepājas dueta Fomins & Kleins 2004 . gada 23. februārī izdotais otrais albu
  33. I Ludwik Lejzer Zamenhof dia dokotera mpijery maso nipetraka any Polonia . Fantantsika izy ankehitri
  34. Седумстотини милиони малечки алвеоли во белите дробови , всушност се шупливи чаури - алвеоли прекрие
  35. Энэхүү шувуу нь Бутан , Хятад , Гонконг , Энэтхэг , Пакистан , Иран , Япон , Казакстан , Солонгос ,
  36. भारतातील महाराष्ट्र राज्याच्या नागपूर पासुन २१६ कि.मी. दूर असलेले एक गाव. ते वैनगंगा नदीच्या काठावर
  37. De Slotervaart was oorspronkelijk de waterweg die sinds de Middeleeuwen het dorp Sloten verbond met
  38. Macierz S (macierz rozpraszania, od ang. scattering matrix ) jest centralnym elementem w mechanice k
  39. A Hora do Rush 3 ( Rush Hour 3 , no original) é o terceiro filme da franquia Rush Hour . Dirigido po
  40. Coordonate : 51°34′0″N 12°3′0″E  /  51.56667 , 12.05 Brachstedt este o comună din landul Saxonia-A
  41. Гробницы императоров династии Мин и Цин — памятник Всемирного наследия ЮНЕСКО , состоящий из несколь
  42. Kovalentni radijus atoma - ponekad se naziva i valentni radijus. Kovalentni radijus je srednje rasto
  43. Koniecpol je mesto v Poľsku v Sliezskom vojvodstve v okrese Powiat częstochowski v rovnomennej gmine
  44. Hoxhë Vokrri vije nga Shqipëria ishte një klerik shqiptar i cili luftonte për Çështjën Kombëtare . A
  45. Гурдијеље је насеље у општини Тутин у Рашком округу . Према попису из 2002. било је 93 становника (п
  46. Underhållsstöd betalas ut av Försäkringskassan (FK) till en förälder som är vårdnadshavare och bor e
  47. இந்தியாவின் தேசிய நெடுஞ்சாலைகள் நடுவண் அரசின் தேசிய நெடுஞ்சாலைத் துறையால் பராமரிக்கப்படுகின்றன. பெரு
  48. Дар он зиндаги .маишат ,фаолияти мехнати,муборизаи ичтимои, русуму омол, хислат ва эхсосоти халк ифо
  49. ไฟทอฟธอรา อินเฟสทันส ( อังกฤษ : Phytophthora infestans ) คือเชื้อ ราโอโอไมซีท หรือ ราน้ำ ที่เป็นสาเห
  50. ABUL FAWARIS BERRANY - 11. asyrda Orta Aziýadaky oguz taýpalarynyň berrany dinastiýasynyň wekili. Ol
  51. Egemenlik ya da hâkimiyet , bir toprak parçası ya da mekan üzerindeki kural koyma gücü ve hukuk yara
  52. Темне фентезі (від англ. Dark Fantasy - темне, похмуре фентезі ) - піджанр літератури, який включає
  53. Paris By Night 84: In Atlanta - Passport to Music & Fashion (Âm nhạc và Thời trang) là chương tr
  54. ISO 3166-2:GU ni akoole ninu ISO 3166-2 , apa opagun ISO 3166 ti International Organization for Stan
  55. 下卡姆斯克 ( 俄文 : Нижнека́мск ; 韃靼語 : Түбән Кама/Tübän Kama )是 俄羅斯 韃靼斯坦共和國 東北部的一個城市,位於 卡馬河 南岸。 2002年 人口22

입력 파일 예시 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는 정확도이다.
문제 출처