ACM-ICPC賽制是目前最常見的團體程式競賽模式,每隊由三個隊員組成,隊員需合力在只使用一台電腦的情況下,在五個小時(300分鐘)的比賽中解出盡量多的題目,並且儘早地用盡量少的嘗試次數解決題目。
每個隊伍將會面對至多15道題目,與高中奧林匹亞競賽不同的是,題目是沒有部分分的,也就是每道題目只有「解出」和「未解出」兩種結果,並以每隊有解出的題目數量進行排名,解出愈多題則排名愈前面。
當然,若只考慮解出題數勢必會造成大量的並列,所以ACM-ICPC賽制引入了「罰時」的機制:若一個隊伍在比賽開始後
若兩個隊伍解出的題目數量相同,則罰時愈少者排名愈前面。若兩個隊伍解出題目數量和罰時均相同,則視為並列(注意此處為了簡化問題,規則與實際比賽有所出入)。一個隊伍的名次即是有多少隊伍排名比該隊伍前面加一,例如若所有隊伍並列,則所有隊伍均獲得第一名。
以下用一個隊伍整場比賽的上傳紀錄來做舉例說明:
時間 | 題目 | 是否解出 |
3 | A | 否 |
5 | B | 是 |
6 | A | 是 |
10 | C | 否 |
298 | B | 否 |
299 | B | 是 |
則此隊最終的結果為解出兩題(A、B),並且在題目A的罰時為
團體競賽雖然相當有趣又刺激,但準備一場萬無一失的比賽也相當不容易,一旦測資有疏失,將可能造成許多問題:例如一個隊伍可能上傳了正確的程式碼並未解出那題,也可能上傳了錯誤的程式碼卻意外解出題目,更有可能一開始上傳了正確的程式碼獲得了錯誤的評測結果、不斷修正後猜出主辦單位的錯誤並解出該題,然而卻因此獲得巨量的罰時。
剛踏入資訊競賽圈子的盩僰麌也剛參加了一場這樣的團體競賽。
具體來說,這場比賽共有
然而,這場比賽的每一道題目的測資都有問題,而這也造成盩僰麌的隊伍的比賽成績不盡理想。為了討回演算法的正義(以及豐厚的獎金),盩僰麌搜集了整場比賽的所有上傳紀錄,包括上傳時間、題號、在比賽中是否解出(也就是在測資錯誤的情況下),並且按照上傳時間排列。除此之外,他也以正確的測資評測了每一筆上傳紀錄的程式碼,因此盩僰麌也知道該筆上傳紀錄是否能在測資正確的情況下解出該題。
雖然照理來說主辦方該更新每一題的測資並重新評測每一題,但這個比賽規模之大,主辦方的伺服器只能承受至多重新評測
事關比賽獎金,精打細算的盩僰麌想知道,在最多重新評測
輸入第一行為一個正整數
每組測資以三個非負整數
接著
對於所有的測資,
輸出一個正整數代表在最多重新評測
範例測資一中,最好的方法是重新評測第1題,如此一來第0隊答對2題、罰時4分鐘,第1隊答對0題、罰時0分鐘,第2隊答對1題、罰時4分鐘。
範例測資五中,雖然盩僰麌的隊伍一題都未解出,卻可以透過重新評測第1題使第2隊與自己並列,提高排名。
Problem set by waynetuinfor
建國中學107學年度校隊選拔:初試pA
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~14 | 21 | |
2 | 15~29 | 30 | |
3 | 0~49 | 無額外限制 | 49 |