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