跳至內容

線上解題系統

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

線上解題系統(英語:Online Judge,縮寫OJ)是一種在演算法競賽競賽中用來測試參賽程式的線上系統,也可以用於平時練習。近年來(2016年或更早)亦出現一些針對求職面試的線上解題系統。許多OJ網站會自發組織一些競賽。此外,OJ網站通常會設立使用者排名,以使用者的提交答案通過數多少或某個題目執行時間快慢為排名依據。[1]

原理

演算法競賽通常採取黑盒測試,事先準備好一些測試資料,然後用它們來測試選手的程式[2]

在線上解題系統中,使用者需要提交原始碼至伺服器,伺服器會編譯使用者的原始碼,然後執行原始碼生成的可執行檔(或用解釋方式執行,或直接執行指令碼檔案),得到其輸出的結果,並與正確結果比較。[3]

為防止攻擊和惡意提交,伺服器必須採取一定的安全措施,例如對使用者提交的原始碼實施過濾、將行程放入沙盒以進行隔離、對代碼進行雜湊以防止抄襲和重複提交等。[3]

Virtual Judge

Virtual Judge是一種特殊的線上解題系統。與其他線上解題系統不同的是,Virtual Judge系統本身並沒有任何測試資料,而是通過在其他線上解題系統中註冊的機器人帳號進行測試並抓取測試結果。因此可以在只有題目而沒有測試資料的前提下建立競賽。[4][5]

題目狀態

在提交程式之後,線上解題系統會根據題目的測評情況,返回測試結果。只有返回「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):答案正確,但是輸出格式不符合題目要求。在一些要求比較嚴格的比賽中,格式錯也會被視為答案錯誤[2]

程式通過

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

  • Accepted(簡稱AC):程式通過。另外,在整場比賽中通過了所有題目又俗稱「AK」或是「破臺」。

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

實例

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

現在較為著名的線上解題系統有洛谷頁面存檔備份,存於網際網路檔案館),西班牙的UVaOJ、俄羅斯的SGU、Timus、Codeforces、波蘭的SPOJ、美國的TopCoder、中國的POJ(北京大學)、ZOJ(浙江大學)、HDOJ頁面存檔備份,存於網際網路檔案館)(杭州電子科技大學)。[2]

不同群體中不同OJ使用的頻率也不同,學生中常會因為教師的要求使用公開/校內OJ,為此,許多公開OJ也提供了個性化服務,如Vijos頁面存檔備份,存於網際網路檔案館)中的「域」服務[7]OpenJudge頁面存檔備份,存於網際網路檔案館)、洛谷頁面存檔備份,存於網際網路檔案館)、Vjudge頁面存檔備份,存於網際網路檔案館)中的團隊服務。

在特定群體中亦有一些流行的線上解題系統,例如中國初中選手中流行的Vijos頁面存檔備份,存於網際網路檔案館)、進階選手使用的BZOJ頁面存檔備份,存於網際網路檔案館)(現稱「耒陽大視野」,註:已無法訪問)、hihocoder頁面存檔備份,存於網際網路檔案館)、美國求職者中流行的LeetCode頁面存檔備份,存於網際網路檔案館)等。

參見

參考文獻

  1. ^ Programming Challenges (Skiena & Revilla)頁面存檔備份,存於網際網路檔案館ISBN 0387001638, ISBN 978-0387001630
  2. ^ 2.0 2.1 2.2 2.3 劉汝佳. 算法競賽入門經典. 清華大學出版社. 2014-06. ISBN 978-7-302-35628-8. 
  3. ^ 3.0 3.1 李定才,瞿紹軍,胡爭,段兵,成幸毅,唐強. 基于Windows的在线评测系统的安全性研究. 電腦技術與發展. 2011-09, (2011年第9期): 204–207. 
  4. ^ Virtual Judge. [2016-09-19]. (原始內容存檔於2016-09-20). (英文)
  5. ^ Welcome to NEUQ Virtual Judge. [2016-01-06]. (原始內容存檔於2016-01-29). (英文)
  6. ^ Revilla M, Manzoor S, Liu RJ. Competitive learning in informatics: the UVa online judge experience (2008,2). Olympiads in Informatics: 131–148. 
  7. ^ 帮助 - Vijos. vijos.org. [2017-06-06]. (原始內容存檔於2017-07-13) (中文(中國大陸)).