線上解題系統(英語:Online Judge,縮寫OJ)是一種在演算法競賽競賽中用來測試參賽程式的線上系統,也可以用於平時練習。近年來(2016年或更早)亦出現一些針對求職面試的線上解題系統。許多OJ網站會自發組織一些競賽。此外,OJ網站通常會設立用戶排名,以用戶的提交答案通過數多少或某個題目執行時間快慢為排名依據。[1]
原理
演算法競賽通常採取黑盒測試,事先準備好一些測試數據,然後用它們來測試選手的程式[2]。
在線上解題系統中,用戶需要提交原始碼至伺服器,伺服器會編譯用戶的原始碼,然後執行原始碼生成的可執行檔案(或用解釋方式執行,或直接執行指令碼檔案),得到其輸出的結果,並與正確結果比較。[3]
為防止攻擊和惡意提交,伺服器必須採取一定的安全措施,例如對用戶提交的原始碼實施過濾、將行程放入沙盒以進行隔離、對代碼進行雜湊以防止抄襲和重複提交等。[3]
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(頁面存檔備份,存於互聯網檔案館)等。
參見
參考文獻
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.