維基百科

用戶:小老虎3018/沙盒/編輯備用

< User:小老虎3018 | 沙盒

線上解題系統（英語：Online Judge，縮寫OJ），是一種能完全自動地根據用戶上交的原始碼、二進制可執行檔案或是純文字輸出內容，來即時測試其能否滿足指定任務要求的系統。早在1961年，史丹福大學就已經有了一套成形的利用測試數據檢驗原始碼執行指定任務的系統，但不能明確指出錯誤在哪出現。[1][2]；而世界範圍熟知的第一個線上解題系統，由西班牙Valladolid大學的Ciriaco García de Celis開發的UVa線上解題系統也於1995年誕生[3]；但這一概念在2001年才被首次定義[4]。自2000年開始，線上解題系統的想法開始廣為傳播並實踐，如Codeforces、POJ等一大批不同定位的測試網站也如雨後春筍般地出現。如今的線上測試網站除了提供測試服務外，還會舉行挑戰性編程比賽，並涉及教育培訓、招聘評判等各方面；而組織程式設計比賽的主辦方，也會建立公開的解題系統供選手練習。

可滿足演算法競賽中根據準備好的數據，自動評價選手提交的有特定任務的源程式。[5]

(x)近年來（2016年或更早）亦出現一些針對求職面試的線上解題系統。許多OJ網站會自發組織一些競賽。此外，OJ網站通常會設立用戶排名，以用戶的提交答案通過數多少或某個題目執行時間快慢為排名依據。[6]

歷史

解題系統已有愈半世紀的 （和acm/ioi關係）

構成

一般的線上解題系統除需滿足基本的測試功能外，還需要能清晰顯示任務的具體要求，並給予測試的反饋。解題系統還會提供額外的與測試緊密相關的功能，如Hack。當然，也有部分解題系統着眼於原始碼的編譯環節，並支援多種語言的線上編譯；社區功能也是大多數線上解題系統所擁有的。

測試

嚴格。其中，評定測試中使用的數據一般由網站或出題人預先準備，而無需用戶自行上載，這種測試方法又被稱作黑盒測試。[7]

原理與實現

一般可以認為，測試分為提交代碼、評定測試、計分反饋三個步驟，而這些步驟應該能夠自動化或半自動化完成。

提交代碼時，如果是需要編譯才能執行的原始碼，需由解題系統先編譯生成可執行程式，再使用程式或直接讀取解釋型代碼進行檢測，驗證其能否在測試環境下執行。能正常執行而開始評定測試時，依照指定的輸入輸出形式（一般有標準輸入輸出和檔案輸入輸出），利用指定題目的測試數據檢測程式；只有當其執行時不出現導致程式崩潰的計算等錯誤，過程中不超出時間和空間限制，並且輸出的答案符合題面要求時，某個特定的測試數據對應的測試點才可被認為通過。隨後，根據各測試數據的測試情況和題目要求對用戶的解法評分。[8]

部分題目由於解法不能在短時間內求解等原因，需要根據下發的數據在本地生成輸出，並交由線上解題系統對比，該過程於提交代碼有一定的區別，一般稱為「提交檔案」。

在具體的操作過程中，一般是解題系統通過呼叫連結動態庫

測試反饋

（改） 在提交程式之後，線上解題系統會根據題目的測評情況，返回測試結果。只有返回「Accepted」狀態，才表示題目通過，選手才會獲得成績。不同OJ測試結果略有出入，但常見的測試結果大致分為以下三類。

等待測試 Pending 系統繁忙，用戶的解答程式正在排隊等待。 Pending Rejudge 因為數據更新、比賽後重測或其他原因，系統將重新判定你的答案。
Compiling 對於需要編譯的源程式檔案，正在將其編譯為可執行檔案。 Running & Judging 正在執行提交的程式並與標準數據進行比較。
測試不通過 Wrong Answer WA 答案錯誤。 Runtime Error RE 執行時錯誤，程式崩潰。
Compile Error CE 編譯錯誤。 Time Limit Exceeded TLE 執行超出時間限制。
Memory Limit Exceeded MLE 超出主記憶體限制。 Output Limit Exceeded OLE 輸出的長度超過限制。
Presentation Error PE) 答案正確，但是輸出格式不符合題目要求。在一些要求比較嚴格的比賽中，格式錯也會被視為答案錯誤
測試通過 Accepted AC 程式通過了某個或所有測試點的測試。
括號內代表常用簡稱。參考來源：[7]


在測試過程中，只有未發生以上幾種錯誤的情況下才算做通過。

  • （簡稱AC）：程式通過。

<->挑戰性編程>另外，在整場比賽中通過了所有題目又俗稱「AK」或是「破臺」。

一些比賽的測試點可以給出「部分分」，例如答案正確但不夠優化，或者選手沒有完全完成題目所給的任務等。[7]

題目數據

題目應該有解。演算法正確性。笑嘻嘻數據強度：


安全問題

用戶可能會提交與解決題目無關的代碼讓解題系統執行，甚至多次對設定時限較大的題目提交代碼執行無窮迴圈陳述式，或在編譯時進行標頭檔攻擊，直接讀取機器隨機輸出造成無限編譯，佔用時間；直接輸出過大的檔案，或利用原始碼在編譯時出過大的可執行程式，佔用空間；直接呼叫系統指令或檔案讓系統敏感數據泄露，或使測試機無法再受理其他提交，例如system("shutdown now");。這些攻擊亦可被劃分為為編譯和執行攻擊。[9]

解題系統多會對用戶提交的原始碼實施過濾，但宏定義可有效繞過這種防範方式。將測試行程放入類似Docker的沙盒中以進行隔離，或限制測試行程對無關檔案的訪問，也是一種常用的解決途徑。[10]

將行程、對代碼進行雜湊以防止抄襲和重複提交等。（+）

效率、穩定問題

要注意的是，出於公平考量，對於一道同樣的題目，或是同一比賽、同一平台的測試，應該在相同的測試環境下進行，並能保證測試環境穩定，反饋資訊可靠。[5]

Hack

編譯

社區功能

抄襲和重複提交

（->需要更多資料） 其中，Virtual Judge/Remote Judge是一種特殊的線上解題系統。與其他線上解題系統不同的是，Virtual Judge系統本身並沒有任何測試數據，而是通過在其他線上解題系統中註冊的機械人帳號進行測試並抓取測試結果。因此可以在只有題目而沒有測試數據的前提下建立競賽。[11][12]

分類

時至今日，仍沒有能被廣為接受的針對線上解題系統的分類。


實例

線上解題系統是由西班牙Valladolid大學的Ciriaco García de Celis於1995年開發的，當時用於該校參加ACM/ICPC西南歐區域賽選拔隊員。[3]

現在較為著名的線上解題系統有西班牙的UVaOJ、俄羅斯的SGU、Timus、Codeforces、波蘭的SPOJ、美國的TopCoder、中國的POJ（北京大學）、ZOJ（浙江大學）、HDOJ（杭州電子科技大學）等。[7]

（改） 不同群體中不同OJ使用的頻率也不同，學生中常會因為教師的要求使用公開/校內OJ，為此，許多公開OJ也提供了個性化服務，如Vijos中的「域」服務[13]，OpenJudge、洛谷、Vjudge中的團隊服務。

在特定群體中亦有一些流行的線上解題系統，例如中國初中[來源請求]選手中流行的Vijos、進階選手使用的BZOJ（現稱「大視野線上測試」）、hihocoder、美國求職者中流行的LeetCode等。

Codeforces是近年來比較知名的線上測試網站，它有向全世界用戶提供周期性的比賽，並同時有英文和俄文兩個版本。每次參與完比賽後，用戶的分數便會根據類似於等級分的評判標準變化。[14][15]網站會根據用戶分數劃分為三個層次的比賽，比賽過程中或賽後會提供Hack功能，該功能後來也被其他線上測試網站效仿。

局限性

參見

[16]

參考文獻

  1. ^ doi:10.1.1.31.3506
    {{cite doi}}已停用，請參見{{cite journal}}。
  2. ^ George E. Forsythe, Niklaus Wirth. Automatic grading programs. Communications of the ACM. 1965-05-01, 8 (5): 275–278 [2019-06-25]. doi:10.1145/364914.364937. 
  3. ^ 3.0 3.1 Miguel A. REVILLA; Shahriar MANZOOR; Rujia LIU. Competitive learning in informatics: the UVa online judge experience (PDF) (2008,2). Olympiads in Informatics: 131–148 （英語）. 
  4. ^ Andy Kurnia, Andrew Lim, Brenda Cheang. Online Judge. Computers & Education. 2001-05, 36 (4): 299–315 [2019-06-25]. doi:10.1016/S0360-1315(01)00018-5 （英語）. 
  5. ^ 5.0 5.1 Szymon Wasik, Maciej Antczak, Jan Badura, Artur Laskowski, Tomasz Sternal. A Survey on Online Judge Systems and Their Applications. ACM Computing Surveys. 2018-01-04, 51 (1): 1–34 [2019-06-25]. doi:10.1145/3143560 （英語）. 
  6. ^ Programming Challenges (Skiena & Revilla) ISBN 0387001638, ISBN 978-0387001630
  7. ^ 7.0 7.1 7.2 7.3 劉汝佳. 算法競賽入門經典. 清華大學出版社. 2014-06. ISBN 978-7-302-35628-8. 
  8. ^ 李定才,瞿紹軍,胡爭,段兵,成幸毅,唐強. 基于Windows的在线评测系统的安全性研究. 電腦技術與發展. 2011-09, (2011年第9期): 204–207. 
  9. ^ 阮行止. OJ技术思考：评测安全. 知乎. 2017-05-18 [2019-03-15]. 
  10. ^ 參照錯誤：沒有為名為aq的參考文獻提供內容
  11. ^ Virtual Judge. （原始內容存檔於2016-09-20）. （英文）
  12. ^ Welcome to NEUQ Virtual Judge. （英文）
  13. ^ 帮助 - Vijos. vijos.org. [2017-06-06] （中文（中國大陸））. 
  14. ^ Open Codeforces Rating System [updated on October 2015]. Codeforces. 2015-11-01 [2019-01-18] （英語）. 
  15. ^ Codeforces Rating System. Codeforces. [2019-01-18] （英語）. 
  16. ^ Online Judge系统的优化. [2019-06-25]. doi:10.3969/j.issn.1003-3254.2011.08.025. 


取自 "https://zh.wikipedia.org/w/index.php?title=User:小老虎3018/沙盒/编辑备用&oldid=54960869"