USACO美國計算機奧賽參賽規則說明

USACO 參賽資格

美國計算機編程算法競賽 USACO (www.usaco.org）歡迎所有人參加。所有的新參賽者都是從(cong) 銅級組開始的，那些在當前組別中得分特別高的人將在未來的比賽中被提升到下一個(ge) 組別（由於(yu) 每個(ge) 比賽都不同，所以提升標準也不同）。隻有非大學生才有資格被選為(wei) 參加USACO訓練營的決(jue) 賽選手，並爭(zheng) 奪美國IOI隊的成員。參加比賽從(cong) 不收取任何費用。

USACO 參賽誠信

USACO采取了嚴(yan) 格的政策來確保競賽的誠信。USACO 明確規定：

• 獨立工作，而不是在團隊環境中工作。
• 禁止與比賽負責人以外的人協商比賽問題。
• 不要提交過去與他人合作編寫的程序。
• 鼓勵參賽者不要使用書本或網站上的代碼，也絕對不能在網上搜索確切的解決方案，或使用在USACO或類似網站上發布的解決方案。如果你必須從書本或網站上查找一些代碼（或更普遍的，任何你沒有從頭開始寫的東西），請在代碼中插入一個注釋，告訴來源。這條規則的目的是允許學生為一些小的代碼查閱一般的參考資料，如如何調用標準庫函數、讀取輸入、格式化輸出等。學生不應該複製不是他們自己寫的大段代碼（例如，整個算法）。
• 不要使用兩個登錄ID，以便參加一個以上的部門。不要使用另一個登錄ID來閱讀問題，以規避比賽的時間限製。
• 不要提交任何對評分機有惡意行為的代碼（即不要試圖打開網絡連接，有意降低評分機的速度，等等）。評判環境會對活動和係統調用進行監控，以防止被禁止的行為。
• 在比賽仍在進行時，不要分享參賽代碼。
• 違反上述任何政策的參賽者將被終身禁止參加所有usaco活動。作弊者，取消將來參賽資格。

USACO 參賽技術要求

• 程序大小必須小於(yu) 100,000字節，並且必須在30秒內(nei) 完成編譯。除非另有說明，你的程序將被限製在256MB左右的總內(nei) 存使用。

• 請勿提交打開與(yu) 競賽任務無關(guan) 的數據文件的程序。隻讀指定的輸入文件，隻寫(xie) 指定的輸出文件。不要使用 "臨(lin) 時 "數據文件。

• 除非另有說明，否則程序必須是確定性的，並且每次在相同的輸入情況下運行都會(hui) 產(chan) 生相同的答案。不具有確定性的程序可能會(hui) 被取消資格。請注意，基於(yu) 隨機數的程序仍然可以參賽--它們(men) 應該使用一個(ge) 固定的種子，以便每次都能得到相同的答案。

• 除非另有規定，否則不保證所有可能的合法數據集都能在規定時間內(nei) 完美解決(jue) （例如，我們(men) 可能會(hui) 提供一個(ge) 任務，期望有接近最優(you) 的解決(jue) 方案，並獲得部分積分）。

• 盡管我們(men) 在設計問題時通常會(hui) 使數字答案適合於(yu) 一個(ge) 標準的32位整數，但這並不保證。如果需要更大的數據類型（如64位整數），我們(men) 通常會(hui) 在問題陳述中加以說明，以方便你使用，但最終你要負責意識到何時需要這些數據。

• 基本上隻包含打印語句的程序將被取消資格。如果在比賽中提供了某些測試案例的反饋，那麽(me) 你就不能重複提交基本上由打印語句組成的程序，以便對輸入進行反向工程。程序必須實際計算所要求的答案，而不是僅(jin) 僅(jin) 打印預先計算好的查找表的結果。

• 程序不能停頓和等待按鍵。例如，如果你在代碼中調用system ("pause")，評分環境可能會(hui) 因等待一個(ge) 不存在的按鍵而超時，返回一個(ge) 類似 "空輸出文件 "的錯誤。

• 過去的USACO競賽中使用的標題（如PROB:和LANG:）不再需要了。相反，在提交代碼時，請務必從(cong) 下拉框中為(wei) 你的程序選擇正確的語言。

• 對於(yu) 已編譯的語言，你不需要刪除所有的編譯器警告。當然，編譯器錯誤會(hui) 使你的提交作品無法被評判。

• 有程序都從(cong) 問題陳述中命名的文件中讀取輸入（例如，"cow.in"）。不要在你的 "打開 "語句中指定一個(ge) 完整的路徑名稱，隻需要 "cow.in"。注意，文件名是區分大小寫(xie) 的。如果問題說 "cow.in"，那麽(me) 你必須使用 "cow.in"，因為(wei)  "CoW.In "和 "COW.IN "將不起作用。所有程序都將其輸出寫(xie) 入問題聲明中命名的文件（例如，`cow.out'）；不要在你的`open'語句中指定路徑名稱，隻需`cow.out'。與(yu) 輸入文件名一樣，輸出文件名也是區分大小寫(xie) 的。寫(xie) 到stdout或stderr的輸出不會(hui) 被分級。

• 幾乎每個(ge) 程序的輸出都是以 "行 "的形式出現。由於(yu) 這是一個(ge) UNIX環境，所有輸入/輸出文件中的行都以單個(ge) 換行符"n "結束，而不是以回車符加換行符"rn "結束（盡管正確設計的程序一般不應關(guan) 心使用哪種慣例）。如果你的輸出在每一行的末尾不包含換行，它可能會(hui) 被評為(wei) 不正確。請注意，輸入文件和輸出文件的最後一行也應該以換行符"n "結尾--這是一個(ge) 常見的錯誤來源；如果你在本地測試你的代碼，請確保你的輸入文件在最後一行的結尾有"n"，特別是如果你在像Python這樣的語言中使用split("n")來分隔各個(ge) 行。這也許是我們(men) 收到的說 "它在我的係統上可以工作，但在比賽服務器上不行 "的郵件的首要原因。

• 對於(yu) 一些輸入量較大的高級問題，參賽者可能會(hui) 從(cong) 使用快速輸入/輸出中受益，從(cong) 而更容易在規定時間內(nei) 通過。對於(yu) C++用戶，如果你使用cin/cout，你可能想在你的主方法的頂部添加 "ioses_base::sync_with_stdio(false); cin.tie(0);" 。對於(yu) Java用戶，你可能想用BufferedReader來代替Scanner。

• 針對Java：我們(men) 最近升級到使用Java 8而不是Java 7。兩(liang) 者之間一個(ge) 明顯的區別是string.split方法在對空字符串""進行分割時的行為(wei) ，例如，如果你想將一個(ge) 字符串分割成單個(ge) 字符。在Java 7中，這將產(chan) 生一個(ge) 數組，其第一個(ge) 元素總是空的，但在Java 8中不是。如果你在2017年1月比賽前或比賽中重新提交你以前提交的Java代碼，你可能會(hui) 因此看到不同的結果，由於(yu) 這一變化。

• 如果隨著時間的推移，你為(wei) 一個(ge) 問題提交了一個(ge) 以上的解決(jue) 方案，那麽(me) 隻有最後提交的那個(ge) 方案才會(hui) 被評分。這意味著如果你在提交後發現了一個(ge) 錯誤，你可以重新提交。重新提交沒有任何懲罰（不過請合理安排重新提交的速度，以減少服務器的負擔）。當然，一旦你的計時器過期，就不能再提交解決(jue) 方案。

• 評委們(men) 保留在評分過程中增加時間限製或增加/刪除測試案例以得出最終結果的權利。

• 評委的決(jue) 定是最終的。

USACO 參賽語言要求

• C/C++程序。程序用gcc/g++ 4.8.2編譯，使用"-O2 "優(you) 化標誌和"-lm "來訪問數學庫，以及"-std=c++0x "來啟用對C++11的支持。Ints大小為(wei) 32位；如果你需要64位的整數，使用"long long"。要用C語言風格的I/O（如scanf、printf）讀取或寫(xie) 入一個(ge) long long變量，請使用"%lld "格式字符串。

• Pascal程序。程序用Free Pascal編譯器2.6.2版編譯時，使用"-O2 "標誌來提供優(you) 化，並使用"-Sd "標誌來指定int應該是32位大小。如果你需要一個(ge) 64位的int，請使用 "int64 "數據類型。

• Java程序。程序用Java 1.8.0_121版編譯，用Oracle Java Runtime Environment執行（注意，這是最近才升級的；2017年1月之前（包括1月的比賽）所有提交的程序都使用了Java 7）。你必須在一個(ge) 文件中提交你的整個(ge) 程序，這個(ge) 文件必須正好有一個(ge) 與(yu) 文件名稱相同的公共類（例如，如果你的文件被稱為(wei)  "MyFile.java"，那麽(me) 它應該包含 "公共類MyFile"）。這個(ge) 類需要有你的公共靜態 void main 函數。文件中的所有其他類都應該在沒有 "public "標簽的情況下進行定義(yi) （例如，定義(yi) 為(wei)  "class MyOtherClass"）。不要在你的源代碼中包含 "package "行。

• Python程序。我們(men) 同時提供Python 2.7.6和Python 3.4.0；請確保在提交時選擇正確的版本，因為(wei) 通常情況下，為(wei) 一個(ge) 版本開發的程序在另一個(ge) 版本中無法正常工作（使用 "python -version "來檢查你本地Python解釋器的版本）。還要注意的是，由於(yu) Python程序的速度較慢，即使給Python提交的程序規定了較長的時間限製，也可能無法解決(jue) 某些問題的最大測試案例--對於(yu) 執行時間很關(guan) 鍵的問題，可以考慮使用更快的語言。執行過程中使用"-O "標誌，以實現一些優(you) 化。

USACO 參賽形式

每場比賽通常有3...4個(ge) 問題，你將提交C、C++、Java 或 Python 語言的解決(jue) 程序。這些問題都是算法性質的，所以要在規定的時間內(nei) 正確解決(jue) 所有測試案例，可能需要巧妙的算法和/或數據結構。

你在每個(ge) 問題上的得分取決(jue) 於(yu) 你的程序能在規定時間內(nei) 解決(jue) 的輸入案例的數量（對於(yu) 大多數比賽，C、C++每個(ge) 輸入案例2秒，Java和Python每個(ge) 輸入案例4秒，盡管每個(ge) 比賽或問題可能使用稍微不同的限製）。所有的問題陳述都是直截了當的，沒有刻意的 "隱藏技巧"（然而，請注意，合法但複雜的數據集是測試的公平遊戲）。問題的目的是具有挑戰性；很少有大量的競爭(zheng) 者獲得接近完美的分數的情況。

比賽通常是3...4個(ge) 小時的連續時間。你可以在你想要的任何時間段參加比賽，隻要你在較大的比賽窗口內(nei) 開始。當你開始比賽時，你的個(ge) 人計時器開始倒計時，你將能夠通過這個(ge) 網站查看比賽問題並提交解決(jue) 方案。當你提交一個(ge) 程序時，它將與(yu) 一些判斷性的測試案例進行比對，對於(yu) 每一個(ge) 案例，你都會(hui) 收到反饋，以彩色方框顯示：綠色表示正確，紅色表示不正確。不正確的提交會(hui) 根據問題的類型進一步區分：X（不正確的答案），T（超過時間限製），！（運行時間錯誤或超過內(nei) 存限製），E（空輸出文件），或M（丟(diu) 失輸出文件）。

如果你的程序編譯失敗，你將會(hui) 看到編譯器的錯誤信息。第一個(ge) 測試案例通常與(yu) 問題陳述中描述的樣本案例相同，你需要正確地解決(jue) 它，然後才會(hui) 得到其餘(yu) 案例的反饋（這些案例在比賽中不會(hui) 被透露，盡管你會(hui) 收到關(guan) 於(yu) 你是否解決(jue) 了這些案例的反饋）。

評委們(men) 保留在比賽結束後增加或刪除測試案例的權利，所以即使你的程序在比賽中通過了所有的案例，仍然值得測試。如果你在競賽期間取得了特別高的分數（通常要求是滿分），你可能有資格獲得 "競賽中 "的晉升；否則，晉升將在競賽結束後授予所有分數高於(yu) 該競賽晉升門檻的參賽者。如果你獲得了競賽中的晉升，你將能夠在更大的競賽窗口內(nei) 的任何時間開始進行下一次競賽，並且有一個(ge) 完整的計時器；也就是說，你在先前的競賽中花費的時間不會(hui) 算在你解決(jue) 下一次競賽的時間中。比賽的官方語言是英語，盡管我們(men) 盡量提供其他幾種語言的問題集的翻譯，以方便我們(men) 的國際競爭(zheng) 者。如果翻譯之間有任何分歧，英語版本應被視為(wei) 官方版本。