「TPS」與「題目敘述故事」:頁面間的差異
(+level範例 +目的) |
|||
行 1: | 行 1: | ||
使用故事來包裝題目敘述,可以幫助參賽者更容易了解題目,又或是考驗參賽者的閱讀理解能力。 |
|||
TPS(Task Preparation System)是一套可以方便產生題目測試資料以及題本的工具,關於 TPS 可以參考以下的 GitHub Repo: |
|||
* TPS Example:https://github.com/TNFSH-Programming-Contest/TPS-example |
|||
* IOI 2017 TPS:https://github.com/ioi-2017/tps |
|||
== 包裝程度比較 == |
|||
{{Memo|本頁面主要使用 TNFSH-Programming-Contest/cms-environment-testing-problem<ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem</ref> 的 pB<ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/tree/main/pB</ref> 作為範本。|}} |
|||
{{TOJ side box|570|E. 存在X}} |
|||
以下使用的範例為 {{TOJ|570}}(109 學年度資訊學科能⼒競賽臺南⼀中校內複選,E. 存在X)在準備競賽時題目敘述演進過程的真實案例。 |
|||
=== Level 1 === |
|||
[[File:Icon tools.svg|20px]] 以下有此標誌的說明需要 CMS 系統管理員操作,出題者可忽略此說明。 |
|||
{{Quote| |
|||
問是否可以以 <math>1 \times 2</math> 骨牌組成給定的遞增圖形。 |
|||
}} |
|||
由出題者寫出來最原始的題目敘述,通常還需要額外的口頭補充解釋才能讓其他人理解題目,這樣的敘述僅能夠讓命題團隊的其他成員記得題目內容,但不足以在正式競賽中使用。 |
|||
=== Level 2 === |
|||
{{reflist-talk}} |
|||
{{Quote| |
|||
給一個 <math>N \times M</math> 的方格圖,其中每個格子皆有 黑/白 其中一個顏色。<br> |
|||
顏色符合以下條件:<br> |
|||
對於第 <math>i</math> 行,<math>1 \sim a_i</math> 為白色,而 <math>a_i + 1 \sim M</math> 為黑色<br> |
|||
對於 <math>1 \leq a_i \leq N-1</math>,<math>ai \leq a_i+1</math>。<br> |
|||
問是否可以用 <math>1 \times 2</math> 的骨牌將所有白色區塊填滿,使得任一個白色格子恰被一個骨牌覆蓋。 |
|||
}} |
|||
由出題者完善的題目敘述,這樣的敘述能夠讓未看過題目的人在沒有額外口頭補充下理解題目。若沒有能力改寫成 Level 3 的題敘,在正式競賽中使用這種題敘尚可接受。 |
|||
== |
=== Level 3 === |
||
{{Quote| |
|||
=== 根目錄 === |
|||
那是有一個魔法軍隊的戰爭時代,譚雅是帝國軍二〇三航空魔導大隊的大隊長。<br> |
|||
==== .github/workflows ==== |
|||
帝國的國力逐漸變得強大,引起鄰國的不安,想趕在被消滅前先下手為強。<br> |
|||
GitHub 自動化流程設定檔。 |
|||
這天某個國家又跨越邊境前來進犯,譚雅奉命前去驅趕敵人。<br> |
|||
敵軍佔領的區域可以由左至右等距分成 <math>N</math> 格,而從邊境線往內陸也按相同距離切割成數格。<br> |
|||
譚雅發現越靠右方的戰線,離邊境的距離可能與相鄰左方相等或更遠。<br> |
|||
魔導大隊的魔法攻擊可以轟炸 <math>1 \times 2</math> 或 <math>2 \times 1</math>的方格。<br> |
|||
所有敵軍佔領的區域都必須轟炸,但為了節省資源,不想要重複轟炸相同格子,也不想轟炸沒有敵軍佔領的區域。<br> |
|||
請問譚雅是否能達成這個目標呢? |
|||
}} |
|||
經過故事設定的包裝,是正式競賽中常見的題目敘述,能夠讓參賽者充分理解題意。 |
|||
== 目的 == |
|||
題目敘述通常會編寫故事來讓參賽者融入該問題的情境,以更好地了解題目所要問的內容。 |
|||
pA、pB 等{{slink||題目資料夾}}。 |
|||
=== 賦予數值意義 === |
|||
{{TOJ side box|630|D. 花子一口吞}} |
|||
記錄{{slink||題目資料夾}}列表,供 GitHub Actions {{slink||自動建置}}使用,通常不應手動修改。 |
|||
110 學年度資訊學科能力競賽臺南一中校內初選 D. 花子一口吞 |
|||
{{Quote |
|||
|給長度 N 的正整數數列 A,求一區間使「區間和 mod K」最大。 |
|||
|原始題敘(Level 2) |
|||
}} |
|||
{{Quote |
|||
|有容量不同的飼料盆排成一列,要把一個區間的飼料全部吃完,吃的時候會把嘴巴塞滿才吞下去,詢問最後一口剩餘在嘴中的飼料數量。 |
|||
|包裝題敘(Level 3) |
|||
}} |
|||
雖然原始題敘已經充分說明題目,但若僅使用原始題敘,參賽者可能就會有「數列?區間?為什麼要 mod K?」等疑惑,但透過故事包裝,將數列轉換為飼料盆內的飼料量、K 轉換為嘴巴的容量、mod K 轉換為吞下飼料的行為,讓題目變成現實生活中可能發生的情境,先透過故事引導參賽者融入情境,這時候再提出問題,便很容易理解問題是什麼。一些演算法原本就能解決現實生活中的問題,因此以實際會遇到的情境去包裝題目問題就能讓題目變得很易懂。 |
|||
==== Makefile ==== |
|||
[[File:Icon tools.svg|20px]] 匯入 CMS 的指令 |
|||
=== 合理化題目 === |
|||
{{TOJ side box|556|B. 舞會}} |
|||
主要在 GitHub 頁面上提供常用連結。 |
|||
{{Quote| |
|||
有 <math>N</math> 個人要爬 <math>K</math> 層樓梯。<br> |
|||
每個人一開始都在第 <math>0</math> 層,且第 <math>i</math> 個人會每秒上升 <math>a_i</math> 層。<br> |
|||
現在有 <math>M</math> 罐運動飲料,每一瓶可以讓第 <math>i</math> 個人瞬間上升 <math>b_i</math> 層。一個人可以喝多瓶,也可以完全不喝。<br> |
|||
請問在最優的分配下,最快幾秒可以讓所有人可以上升到樓梯頂部 ( 層數 <math>\ge K</math> 即視為在樓梯頂部 )。 |
|||
|未採用題敘(Level 3) |
|||
}} |
|||
{{Quote| |
|||
雪乃和伊呂波在準備畢業舞會,準備工作非常繁雜,有 <math>N</math> 項工作需要完成。<br> |
|||
為了好好管理進度,雪乃將每項工作都等分成 <math>K</math> 份。<br> |
|||
而雪乃和伊呂波一起工作的話,對於第 <math>i</math> 項工作,每天可以完成那項工作的 <math>a_i</math> 份(每項工作每天都會做,且恰好完成 <math>a_i</math> 份,無法把時間挪用給其他工作,就算有一些項目的工作已經完成,也不會增加其他工作的效率)。<br> |
|||
但是怕工作做不完,恰好又有 <math>M</math> 筆經費,所以決定把部份工作外包。<br> |
|||
每筆經費對於第 <math>i</math> 項工作,可以將那項工作的 <math>b_i</math> 份外包,外包的部分可不計入花費時間直接視為完成。<br> |
|||
請問在最佳分配經費的情況下,最少幾天就能完成所有工作(不足一天以一天計)。 |
|||
|正式題敘(Level 3) |
|||
}} |
|||
雖然未採用題敘直接在正式競賽中使用並沒有什麼問題……但運動飲料可以讓人「瞬間」上升怎麼想都不合理,而且運動飲料不是增加每個人的體能而是讓人直接上升,所以對不同人的效果為何有不同效果(<math>b_i</math>)也缺乏合理解釋。改成工作外包後,不同工作在同樣經費下能外包的工作量本來就不同,而且外包也能作為工作量直接消失的理由。 |
|||
=== 測驗閱讀理解 === |
|||
2008 網際網路程式設計全國大賽高中組決賽 B. 幼稚國王去旅行 |
|||
題本封面。 |
|||
{{Quote |
|||
|輸出 1 就是答案。 |
|||
|根本是答案(Level 1) |
|||
}} |
|||
{{Quote |
|||
|參見 [https://contest.cc.ntu.edu.tw/npsc2008/2008sen_final.pdf 題本]。 |
|||
|包裝題敘(Level 3) |
|||
}} |
|||
一個反例是將簡單的題目包裝起來,測驗參賽者的閱讀理解能力。另外對於 Hello World 或是 A+B 等題目,包裝一點故事才不會讓題敘過短。 |
|||
=== 總結 === |
|||
範例:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/cover.tex |
|||
總結,使用故事來包裝題目敘述可以: |
|||
# 更容易理解題目。 |
|||
# 純粹測試閱讀能力。 |
|||
# 讓題目有趣一些。 |
|||
# 讓不會解題的參賽者在競賽中不至於那麼無聊。 |
|||
# 讓出題者對喜愛的作品置入性行銷。 |
|||
== 題本架構 == |
|||
題本內文模板,通常無需修改。 |
|||
=== |
=== 一般 === |
||
{{TOJ side box |
|||
==== attachments ==== |
|||
|629|C. GAMAGAMA |
|||
放在此處的所有檔案將會上傳到 CMS 上,供參賽者在題目敘述頁的「附件」,通常僅會在 pA 的附件放置{{slink||合併題本}}。 |
|||
|630|D. 花子一口吞 |
|||
|637|D. 本田小狼 |
|||
}} |
|||
能使用故事來包裝的題目,題目本文的架構通常如下: |
|||
一開始用少數幾句話介紹世界觀,通常與所參考的作品相同,這邊的介紹對解題通常沒有幫助,例如: |
|||
[[File:Crystal Clear action run.png|20px]] 本目錄內容通常由程式自動產生。 |
|||
* {{TOJ|629}} ─ GAMAGAMA 水族館面臨即將停業的危機 |
|||
* {{TOJ|630}} ─ 自稱為半龍人的貪吃少女 — 花子,實際上卻是魔界四大公爵-龍族法夫納家的下任家主! |
|||
* {{TOJ|637}} ─ 今天小熊騎著本田小狼 50 兜風 |
|||
進一步介紹故事劇情,這裡就會提到測資中會出現的設定,例如城市與道路的數量,例如: |
|||
範例:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/tree/main/pA/attachments |
|||
* {{TOJ|629}} ─ GAMAGAMA 水族館有兩條觀察大型水族箱的海底隧道... |
|||
* {{TOJ|630}} ─ 她會選定某盆飼料開始一顆顆往嘴巴裡吃,一但到達嘴巴能裝的最多數量 K,就會一口吞下! |
|||
* {{TOJ|637}} ─ 如果將所有的景點、店家等等都當作是一個節點,並且依序將節點從 1~n 編號,制高點編號為 1 |
|||
最後提出題目真正要詢問的問題,例如: |
|||
==== gen ==== |
|||
* {{TOJ|629}} ─ 為了控制不要讓積分過度膨脹,必須先進行模擬 |
|||
放置{{slink||產測資}}相關的所有檔案。 |
|||
* {{TOJ|630}} ─ 請幫助花子找到留下最多飼料當作點心的方法 |
|||
* {{TOJ|637}} ─ 請問小熊可以選擇的地點有多少個? |
|||
{{TOJ side box |
|||
範例:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/tree/main/pB/gen |
|||
|507|A. 二分圖匹配(說明圖片位於第 2 頁最上方) |
|||
|570|E. 存在X(說明圖片位於本文尾端) |
|||
}} |
|||
如果題意需要圖片輔助說明,可放在本文尾端(較短的本文)或其他合適地方(較長的本文),如果題目沒有[[#插圖|插圖]],亦可放置在插圖處。 |
|||
{{clear}} |
|||
=== 無法包裝的題目 === |
|||
但還是有一些題目實在不會在現實生活中遇到,這時候只好勉為其難使用爛招,也就是在題目敘述寫一些無關緊要的描述,最後再直白的亮出問題。 |
|||
{{See also|#手產測資檔}} |
|||
==== Hello World ==== |
|||
範例:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/tree/main/pB/gen/manual |
|||
{{TOJ side box |
|||
|547|0. Hello World |
|||
|618|A. 比賽須知 |
|||
|633|G. 簡單易懂的現代魔法 |
|||
}} |
|||
對於直接輸出 Hello World 的題目,實在沒有什麼劇情可言,通常做法是隨便介紹一下 Hello World 的由來,然後在輸出說明要求輸出 Hello World 而已。 |
|||
{{clear}} |
|||
==== |
==== 數學題目 ==== |
||
{{Quote |
|||
{{See also|#產測資指令}} |
|||
|題目:請用「XX」造句。 |
|||
答案:「今天老師出了一個題目,讓我們用XX造句。」 |
|||
==== scripts ==== |
|||
|造句的爛招 |
|||
[[File:Crystal Clear action run.png|20px]] 本目錄保存 TPS scripts,不需修改。 |
|||
}} |
|||
{{TOJ side box |
|||
範例:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/tree/main/pB/scripts |
|||
|571|F. 大家來找碴 |
|||
|638|E. 遞迴呀遞迴 |
|||
}} |
|||
如同以上造句的通用解答,實際上對於所有題目也可以使用以下的通用敘述: |
|||
{{Quote |
|||
==== solution ==== |
|||
|...(毫無意義的故事,通常與教室、老師有關)... |
|||
{{See also|#標程}} |
|||
老師問了一個問題,請解出 XXXXX(題目本身)。 |
|||
==== statement ==== |
|||
|數學題目的題目本文 |
|||
題本相關檔案,包含原始碼、圖片、{{slink||建置題本}}產生的 PDF。 |
|||
}} |
|||
== 插圖 == |
|||
題目插圖通常與題目本文中使用的故事相關,來提高參賽者解題興趣,例如使用動畫設定作為背景故事則會使用該動畫的截圖。無論有無插圖都不影響題意理解,故插圖不是必須的。插圖通常放置於標題下方、本文的最上方。 |
|||
{{See also|#題目敘述}} |
|||
若使用[[TPS]]題本格式<ref>https://github.com/TNFSH-Programming-Contest/tps-task-templates/blob/main/default/statement/index.md</ref>,可使用以下語法: |
|||
<syntaxhighlight lang="text"> |
|||
\begin{figure}[h] |
|||
==== tests ==== |
|||
\centering |
|||
{{slink||產測資}}後的檔案會存放於此,參見{{slink||建置測資}}。 |
|||
\includegraphics[width=12cm]{FILENAME.jpg} |
|||
\caption{圖片說明,出自動畫《動畫名稱》} |
|||
[[File:Crystal Clear action run.png|20px]] 本目錄內容由程式自動產生,不應手動編輯。 |
|||
\end{figure} |
|||
範例:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/tree/main/pB/tests |
|||
==== validator ==== |
|||
{{See also|#驗測資程式}} |
|||
==== problem.json ==== |
|||
題目的相關設定,參見{{slink||競賽名稱|題目名稱|題目英文名稱|題目編號|記憶體限制|時間限制}}。 |
|||
範例:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/problem.json |
|||
==== solutions-check.txt ==== |
|||
所有標程的執行結果報告。 |
|||
[[File:Crystal Clear action run.png|20px]] 本檔案由程式自動產生,不應手動編輯。 |
|||
範例:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/solutions-check.txt |
|||
==== solutions.json ==== |
|||
列出所有{{slink||標程}}及其 verdict,標記為 model_solution 的標程會用於{{slink||產測資}}。 |
|||
範例:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/solutions.json |
|||
==== subtasks.json ==== |
|||
列出所有的{{slink||子任務}},及每個子任務所使用的{{slink||驗測資程式}}。 |
|||
範例:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/subtasks.json |
|||
== 準備GitHub Repo == |
|||
=== 建立GitHub Repo === |
|||
# 進入 tps-starter。<ref>https://github.com/TNFSH-Programming-Contest/tps-starter</ref> |
|||
# 點擊 Use this template。<ref>直接連結:https://github.com/TNFSH-Programming-Contest/tps-starter/generate</ref> |
|||
# 填寫Repo資訊 |
|||
#* Repository name 填入競賽英文名,例如「cms-environment-testing-problem」。 |
|||
#* Description 填入競賽中文名,例如「CMS環境測試題目通用版」。 |
|||
#* [[File:OOjs UI icon alert-destructive.svg|20px]] '''注意:'''可見度必須選擇 '''Private'''。 |
|||
#* 點擊 Create repository from template。 |
|||
# (可選)若要將 GitHub Repo 更新傳送到 Discord,請參考 [https://support.discord.com/hc/en-us/articles/228383668-Intro-to-Webhooks Intro to Webhooks – Discord] 操作。 |
|||
{{reflist-talk}} |
|||
=== 建立題目資料夾 === |
|||
此操作在每個競賽通常僅需執行 1 次。 |
|||
# 進入由 tps-starter 建立的 GitHub repo。 |
|||
# 點擊 Actions。 |
|||
# 在 Workflows 段落,點擊 New problem。<ref>參考連結:https://github.com/TNFSH-Programming-Contest/TPS-example/actions/workflows/new-problem.yml</ref> |
|||
# 點擊 Run workflow,在 How many problems in this contest? 輸入要建立的題目數量。 |
|||
#* 如果已有 3 題,要再新增 1 題,直接輸入 4 即可,已建立的目錄會直接被略過。 |
|||
# 點擊藍色 Run workflow 按鈕。 |
|||
# 等待題目資料夾建立完成,約 1 分鐘。 |
|||
{{reflist-talk}} |
|||
=== 刪除題目資料夾 === |
|||
雖然這通常不會發生,但如果誤建過多題目等情況,需要刪除題目資料夾時,請務必完成以下所有操作: |
|||
# 刪除{{slink||題目資料夾}}。 |
|||
# 從{{slink||.problems.json}}刪除題目編號。 |
|||
# 從{{slink||Makefile}}刪除對應題目的匯入指令。 |
|||
# 從{{slink||README.md}}刪除對應題目的連結。 |
|||
== 準備TPS資料 == |
|||
=== 競賽名稱 === |
|||
競賽名稱使用於: |
|||
# CMS 參賽介面左上角。 |
|||
# 題本封面第一行。 |
|||
# 題本內文各頁的左上角。 |
|||
需寫入於:(範例為「CMS環境測試題目通用版 v1.1」) |
|||
# {{slink||cover.tex}}。 |
|||
# 各題目{{slink||problem.json}}的 contest_name 欄位。 |
|||
# [[File:Icon tools.svg|20px]] CMS 管理系統的 Description 欄位。 |
|||
=== 題目名稱 === |
|||
題目名稱(problem title)使用於: |
|||
# CMS 競賽概況的題目列表。 |
|||
# CMS 題目敘述頁面。 |
|||
# 題目標題(第一頁第一行)。 |
|||
# 該題目各頁右上角。 |
|||
需寫入於{{slink||problem.json}}的 title 欄位,範例為「Piñata」。 |
|||
=== 題目英文名稱 === |
|||
題目英文名稱(problem name)應足以讓所有命題人員識別個別題目即可,通常取自於中文題目名稱,並盡量僅使用一個英文詞,首字大寫,若需要兩個英文詞以上,則使用[[zhwiki:駝峰式大小寫|PascalCase]]。使用於: |
|||
# CMS 競賽概況的題目列表。 |
|||
# CMS 題目敘述。 |
|||
# CMS 系統內部用來識別題目的 [[zhwiki:主鍵|Primary key]]。 |
|||
#* [[File:Icon tools.svg|20px]] 由於同一 CMS 系統上的名稱無法重複,若與其他競賽題目衝突<ref>https://github.com/cms-dev/cms/issues/765</ref>,建議加上競賽名稱的英文縮寫作為前綴(例如「2022P-」)。 |
|||
# 可能作為 GitHub repo 內的題目資料夾名稱。 |
|||
需寫入於{{slink||problem.json}}的 name 欄位,範例為「Pinata」。 |
|||
{{reflist-talk}} |
|||
=== 題目編號 === |
|||
題目編號(problem label)為 A, B, C... 的流水號,在決定題目順序後才會確定,使用於:(範例為「B」) |
|||
# CMS 競賽概況的題目列表。 |
|||
# 題目標題(第一頁第一行)。 |
|||
# 該題目各頁右上角。 |
|||
# 該題目各頁頁碼處。 |
|||
=== 記憶體限制 === |
|||
需寫入於{{slink||problem.json}}的 memory_limit 欄位,單位為MB,範例為「512」MB。 |
|||
=== 時間限制 === |
|||
需寫入於{{slink||problem.json}}的 time_limit 欄位,單位為秒,範例為「1.0」秒。 |
|||
=== 標程 === |
|||
AC code(又稱官方解法、標程等)需放置在{{slink||solution}}資料夾內,檔名無限制。同時將該檔名寫入{{slink||solutions.json}},格式請參照範本,verdict 必須標記為 model_solution,範例檔名為「ac.cpp」<ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/tree/main/pB/solution/ac.cpp</ref>。 |
|||
其他 AC code 亦按照前述方式操作,verdict 必須標記為 correct。 |
|||
其他類型的錯誤解法亦按照前述方式操作,verdict 標記方式請參考官方說明<ref>https://github.com/ioi-2017/tps/tree/master/docs#solutionsjson</ref>及 tps script<ref>https://github.com/TNFSH-Programming-Contest/tps-task-templates/blob/93cff7e64a43f57450b26568194432e7b662be38/default/scripts/internal/invoke.py#L18</ref>。 |
|||
{{reflist-talk}} |
|||
=== 產測資 === |
|||
TPS 產測資方式與 Codeforces polygon 相同。測資可以使用手產測資檔案,亦可由程式亂數產生,亦可混合兩者。 |
|||
==== 手產測資檔 ==== |
|||
{{Memo|'''最佳實踐:''' |
|||
# 僅在範例測資和 [[:zhwiki:en:Edge case|edge case]] 使用手產測資檔,其他使用產測程式。 |
|||
# 在 gen/manual 保存與題本相同的範例測資。 |
|||
|}} |
|||
手產測資檔應放置在{{slink||gen/manual}}資料夾內,檔名無限制,但建議副檔名為 .in。 |
|||
本範例包含一個固定測資檔 sample-01.in<ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/gen/manual/sample-01.in</ref> 作為範例測資。 |
|||
{{reflist-talk}} |
|||
==== 產測資程式 ==== |
|||
{{Memo|'''重要:'''產測資程式必須 |
|||
# 使用命令列參數讀入測資組及測資點<ref>[https://en.cppreference.com/w/cpp/language/main_function Main function - cppreference.com]</ref><ref>[https://stackoverflow.com/questions/3024197/what-does-int-argc-char-argv-mean c++ - What does int argc, char *argv[] mean? - Stack Overflow]</ref>。 |
|||
# 使用[[zhwiki:stdout|標準輸出(stdout)]],不可直接寫入檔案。 |
|||
# 執行一次僅輸出一筆測資。 |
|||
# 使用 testlib.h<ref>[https://codeforces.com/blog/entry/18291 Generators with testlib.h]</ref> 等設定亂數種子的方式,使得每次產生的測資都是相同的。 |
|||
|inline:notice}} |
|||
產測資程式(generator)應放置在{{slink||gen}}資料夾內,檔名無限制。 |
|||
以下說明請配合範例檔案 gen/gen.cpp<ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/gen/gen.cpp</ref>。 |
|||
使用 <syntaxhighlight lang="c++" inline>#include "testlib.h"</syntaxhighlight> 引入 testlib 函式庫。 |
|||
main 函數務必寫成 <syntaxhighlight lang="c++" inline>int main(int argc, char* argv[])</syntaxhighlight> 來接收命令列參數。 |
|||
在 main 函數的第一行使用 <syntaxhighlight lang="c++" inline>registerGen(argc, argv, 1);</syntaxhighlight> 將命令列參數作為亂數種子。 |
|||
命令列參數會保存在 <syntaxhighlight lang="c++" inline>argv</syntaxhighlight> 內,可將其保存在 string 內: <syntaxhighlight lang="c++" inline>string task = argv[1];</syntaxhighlight>,或是使用 atoi<ref>https://en.cppreference.com/w/cpp/string/byte/atoi</ref> 等函數轉換為整數。例如範例中第一個參數用來判斷是第幾組測資,將其轉換為 <syntaxhighlight lang="c++" inline>int taskN</syntaxhighlight> 用於判斷。若為第一筆測資,測資範圍則為 87,若為其他測資,測資範圍則為 10^9。 |
|||
使用 <syntaxhighlight lang="c++" inline>rnd.next(-maxN, maxN)</syntaxhighlight> 來隨機產生範圍在 -maxN 到 maxN 之間的整數,保存在變數上用於之後輸出。 |
|||
最後將產生的測資輸出。 |
|||
{{Memo}} 由於 cout 中執行順序屬未定義行為,請勿將多個 rnd.next 合併在一個 cout 中使用,請分開 cout 或事先保存在變數上。 |
|||
{| class="wikitable" |
|||
|- |
|||
| <syntaxhighlight lang="c++"> |
|||
cout << rnd.next (1, n) << endl; |
|||
</syntaxhighlight> |
</syntaxhighlight> |
||
| {{Y}} |
|||
|- |
|||
| <syntaxhighlight lang="c++"> |
|||
cout << rnd.next (1, n) << " " << rnd.next (1, n) << endl; |
|||
</syntaxhighlight> |
|||
| {{N}} 未定義行為 |
|||
|- |
|||
| <syntaxhighlight lang="c++"> |
|||
cout << rnd.next (1, n) << " "; |
|||
cout << rnd.next (1, n) << endl; |
|||
</syntaxhighlight> |
|||
| {{Y}} |
|||
|- |
|||
| <syntaxhighlight lang="c++"> |
|||
int a = rnd.next (1, n), b = rnd.next (1, n); |
|||
cout << a << " " << b << endl; |
|||
</syntaxhighlight> |
|||
| {{Y}} |
|||
|} |
|||
{{TOJ side box|571|F. 大家來找碴}} |
|||
完成產測資程式後,編譯成檔名為 gen 的執行檔(在 Windows 上的 gen.exe),在命令列使用: |
|||
建議可使用有[[zhwiki:創用CC授權條款|創用CC]]等授權條款,或其他明確向公眾授權的圖片,例如吉卜力工作室的動畫劇照<ref>https://www.ghibli.jp/info/013409/</ref>等。 |
|||
* <code>gen 1</code> 會隨機產生 4 個 -87 ~ 87 之間的數字(格式參見題目敘述) |
|||
{{clear}} |
|||
* <code>gen 2</code> 會隨機產生 4 個 -10^9 ~ 10^9 之間的數字 |
|||
{{ |
{{Legal}} |
||
引用受著作權保護的圖片將依著作權法<ref>https://law.moj.gov.tw/LawClass/LawAll.aspx?PCode=J0070017</ref>第 52 條<ref>https://law.moj.gov.tw/LawClass/LawSingle.aspx?pcode=J0070017&flno=52</ref>以教學為目的主張[[zhwiki:合理使用|合理使用]]。唯應依同法第 64 條<ref>https://law.moj.gov.tw/LawClass/LawSingle.aspx?pcode=J0070017&flno=64</ref>標明出處,在圖片說明以「出自動畫《動畫名稱》」等字樣標示。另根據同法第 65 條<ref name="copyright-act-65">https://law.moj.gov.tw/LawClass/LawSingle.aspx?pcode=J0070017&flno=65</ref>第 2 款第 3 項,縮小圖片解析度,建議在 12cm 的顯示效果下將圖片寬度壓縮至 640 px(16:9 的圖片高度為 360px)。 |
|||
==== 產測資指令 ==== |
|||
產測資指令應放置在{{slink||gen/data}},以下說明請配合範例。 |
|||
<div style="float: right;"> |
|||
每一個測資點以 @subtask 接測資點代號為開頭,這個測資點代號亦會使用在{{slink||子任務}}。 |
|||
{{TOJ side box |
|||
|330|A. Piñata |
|||
接下來每個測資點可以有多筆測資,每筆測資可以使用手產測資檔,也可使用產測資程式。 |
|||
|331|B. 尼莫西妮 |
|||
* 使用手產測資檔則為 manual 接續放在{{slink||gen/manual}}資料夾內的測資檔名。 |
|||
|332|C. 棋盤 |
|||
* 使用產測資程式則為呼叫在命令列中的指令。 |
|||
|333|D. 畢業 |
|||
|334|E. 蛋糕 |
|||
範例中第一行為 @subtask samples 為範例測資(samples 為固定名稱不可更改),包含一個手動測資檔 sample-01.in<ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/gen/manual/sample-01.in</ref>。 |
|||
|335|F. 參訪者們 |
|||
{{Memo|'''重要:'''將範例測資作為配分為 0 的第一筆測資點,名稱為 samples。|}} |
|||
|336|G. 禮物 |
|||
}} |
|||
範例中除了範例測資外,共有 2 個測資點,名稱分別為 small 跟 all。兩個測資點都包含 5 筆自動測資。 |
|||
</div> |
|||
<div style="float: right;"> |
|||
{{Memo}} 如果呼叫產測程式,但在指令中輸入了兩行一模一樣的內容,那麼這兩個測資就會相同(在設定亂數種子的情況下)。 |
|||
[[檔案:Request permission for K.R.T. Girls.png|200px|縮圖|左|取得授權範例,第四屆大臺南高一生程式設計排名賽]] |
|||
</div> |
|||
{| class="wikitable" |
|||
如果可行,應嘗試向著作權人取得授權(如右圖),依著作權法第 65 條<ref name="copyright-act-65"/>第 3 項確認合理使用範圍,例如第四屆大臺南高一生程式設計排名賽所使用的圖片。 |
|||
|- |
|||
{{clear}} |
|||
| <syntaxhighlight lang="text"> |
|||
@subtask small |
|||
gen 1 |
|||
gen 1 |
|||
gen 1 |
|||
</syntaxhighlight> |
|||
| {{N}} 會產生 3 筆相同測資 |
|||
|- |
|||
| <syntaxhighlight lang="text"> |
|||
@subtask small |
|||
gen 1 1 |
|||
gen 1 2 |
|||
gen 1 3 |
|||
</syntaxhighlight> |
|||
| {{Y}} |
|||
|- |
|||
| <syntaxhighlight lang="text"> |
|||
@subtask small |
|||
gen 1 pewfw |
|||
gen 1 qrewx |
|||
gen 1 xckxk |
|||
</syntaxhighlight> |
|||
| {{Y}} |
|||
|} |
|||
因此通常會在後面放上隨機文字作為亂數種子的一部分,亦可透過更換亂數種子來重新產生測資,隨機文字可使用線上工具<ref>例如 [https://www.random.org/strings/ Random String Generator]</ref>產生。 |
|||
{{Memo|'''小技巧:''' |
|||
# 透過命令列參數直接控制測資範圍,就不需要在產測資程式碼內判斷測資點。 |
|||
# 發現不良的測資時,透過修改命令列參數的隨機文字來得到一筆新的隨機測資。 |
|||
# 若需要 edge case,使用手產測資檔。 |
|||
|}} |
|||
{{reflist-talk}} |
{{reflist-talk}} |
||
== 資料結構與故事設定 == |
|||
=== 求餘數 === |
|||
{{Quote |
|||
{{TOJ side box |
|||
| 如果你寫了一個程式解題的問題,並準備好了測試資料,那麼你將可能會遇到一個恐怖的經驗:測試資料是無效的!(即測試資料並未符合題目所規定的限制),例如超過了範圍上限、你的圖實際上沒有連通、或是你的圖不是一棵樹……你很可能會有這種經驗,就算是有經驗的出題者也可能有時會出錯(知名案例像是 ACM ICPC World final 2007)。 |
|||
|630|D. 花子一口吞 |
|||
| 翻譯自 [https://codeforces.com/blog/entry/18426 Codeforces 上對於 Validator 的引言]。 |
|||
}} |
}} |
||
除法的求餘數可以轉換成多次的減法,例如: |
|||
{{Memo|'''最佳實踐:'''撰寫驗測資程式來自動檢查測資範圍及其他條件是否有符合題目的規定,避免測資範圍錯誤。|}} |
|||
# 使用容量為 K 的水瓢從水缸舀水直到無法盛滿水瓢,問最後剩餘的水量。 |
|||
若僅是答案過大而需要取餘數輸出,可以直接寫在輸出說明,不一定要作為題敘的一部分。 |
|||
驗測資程式(validator)應該放置在{{slink||validator}}資料夾內,檔名無限制,並將檔名寫入{{slink||subtasks.json}}的 global_validators 或 subtasks 的 validators。 |
|||
本範例包含 2 個 validator。 |
|||
validator.cpp <ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/validator/validator.cpp</ref> 用來驗證所有測資的範圍是否在 -10^9 ~ 10^9 內,故在{{slink||subtasks.json}}中設為 global_validators。 |
|||
validator-small.cpp<ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/validator/validator-small.cpp</ref> 僅用來測試第 2 筆測資(index = 1)範圍是否在 -87 ~ 87,在{{slink||subtasks.json}}中設定為測資 small 的 validators。 |
|||
除了檢查範圍以外,readInt 等函數會回傳其數值,可以保存到變數上作進一步檢查,例如檢查陣列數值皆相異,檢查是否是圖、樹或其他資料結構。 |
|||
更多資訊請參見 Codeforces 上的說明<ref>[https://codeforces.com/blog/entry/18426 Validators with testlib.h - Codeforces]</ref>。 |
|||
{{Memo|'''小提示:'''驗測資程式僅檢查與解法無關的輸入資料限制,檢查是否 TLE、得部分分數屬於{{slink||標程}}的範圍。|}} |
|||
{{reflist-talk}} |
|||
=== 子任務 === |
|||
子任務(subtask)設定於{{slink||subtasks.json}},包含各子任務的配分、文字描述、{{slink||驗測資程式}}。以下說明請參考範例。 |
|||
subtasks.json 最外層包含兩個 key: |
|||
* global_validators:在所有測資使用的{{slink||驗測資程式}}。 |
|||
* subtasks:包含所有測資點。 |
|||
subtasks 是一個 key-value pairs,key 與{{slink||產測資指令}}中設定的相同。value 包含以下 key-value pairs: |
|||
* index:流水號,出現在題本內的順序,從 0 開始;samples 必為 0。 |
|||
* score:子任務分數;samples 必為 0。 |
|||
* text:子任務描述,使用在題目描述內。 |
|||
* validators:僅在該子任務使用的{{slink||驗測資程式}}。 |
|||
{{reflist-talk}} |
|||
=== 題目敘述 === |
|||
題目敘述(statement)的檔案放置於{{slink||statement/index.md}}。使用 [[zhwiki:Markdown|Markdown]] 及 [[zhwiki:XeTeX|XeTeX]] 語法。 |
|||
結構由上到下依序為: |
|||
# {{slink||題目圖片}} |
|||
# {{slink||題目本文}} |
|||
# 輸入(說明),參見{{slink||輸入及輸出說明}} |
|||
# 輸出(說明),參見{{slink||輸入及輸出說明}} |
|||
# {{slink||輸入限制}} |
|||
# {{slink||子任務}}說明 |
|||
# 範例輸入,參見{{slink||範例輸入及輸出}} |
|||
# 範例輸出,參見{{slink||範例輸入及輸出}} |
|||
# {{slink||提示}} |
|||
==== 題目圖片 ==== |
|||
參見{{slink|題目敘述故事|插圖}}。 |
|||
==== 題目本文 ==== |
|||
參見[[題目敘述故事]]。 |
|||
==== 輸入及輸出說明 ==== |
|||
輸入輸出說明必須明確說明參賽者要遵守的格式。 |
|||
應該以一行敘述測資中的一行所代表的資料,例如: |
|||
* 第一行有 1 個整數,代表接下來的測資數量。 |
|||
* 第一行有 2 個整數,代表初始座標。 |
|||
如果需要在其他地方(輸入說明的其他行、輸入限制、題目本文等)提到該變數,應賦予變數代號,例如: |
|||
* 第一行有 2 個整數 <math>V, E</math>,<math>V</math> 代表點的數量,<math>E</math> 代表邊的數量。 |
|||
* 第一行有 1 個整數 <math>N</math>,代表有 <math>N</math> 個人。...(換行)...接下來有 <math>N</math> 行,每一行有 1 個整數代表該人的分數。 |
|||
{{Memo|'''注意:'''同一個變數代號必須在該題目的任何地方皆相同,大小寫也必須相同。|}} |
|||
==== 輸入限制 ==== |
|||
輸入限制用來告知參賽者測資的數值範圍限制, |
|||
{| class="wikitable" |
|||
|- |
|||
! 原始碼 !! 顯示結果 |
|||
|- |
|||
| <syntaxhighlight lang="markdown"> |
|||
- $1 \leq N \leq 100$ |
|||
- $1 \leq M \leq N$ |
|||
- $Y - X$ 必定為 2 個倍數 |
|||
- 若 $A = 1$,則 $B > 0$ |
|||
</syntaxhighlight> |
|||
| |
|||
* <math>1 \leq N \leq 100</math> |
|||
* <math>1 \leq M \leq N</math> |
|||
* <math>Y - X</math> 必定為 2 個倍數 |
|||
* 若 <math>A = 1</math>,則 <math>B > 0</math> |
|||
|} |
|||
==== 子任務說明 ==== |
|||
參見{{slink||子任務}}的操作,即會自動顯示於題本中。 |
|||
==== 範例輸入及輸出 ==== |
|||
範例輸入輸出必須與{{slink||產測資}}中設定的範例測資相同。 |
|||
=== 圖 === |
|||
{{TOJ side box |
{{TOJ side box |
||
|568|C. ChamJam |
|||
|628|B. 國中會考分 |
|||
}} |
}} |
||
圖論問題通常可以轉換為: |
|||
如果有多筆範例測資,標題應改命名為「範例輸入1、範例輸出1、範例輸入2、範例輸出2」等。 |
|||
# 城市與相連的道路。 |
|||
{{clear}} |
|||
# 車站與相連的鐵路。 |
|||
==== 有向無環圖 ==== |
|||
{{TOJ side box |
{{TOJ side box |
||
|569|D. 露營 |
|||
|631|E. 蓋歐格(單個範例附說明) |
|||
|632|F. 最小生成數(多個範例,僅有 1 個範例有說明) |
|||
|637|D. 本田小狼(有圖片的範例說明) |
|||
}} |
}} |
||
有向無環圖可拆成「有向」和「無環」兩個性質。「有向」可簡單地描述為單向道即可。「無環」則可以在題目中暗示說不會走到重複的點。 |
|||
如果有需要說明測資,可加上「範例說明」章節,詳細說明範例測資中的意義,亦可附圖說明。 |
|||
=== 樹 === |
|||
{| class="wikitable" |
|||
|- |
|||
| style="vertical-align: top" | |
|||
* 範例輸入 |
|||
* 範例輸出 |
|||
| style="vertical-align: top" | |
|||
* 範例輸入1 |
|||
* 範例輸出1 |
|||
* 範例輸入2 |
|||
* 範例輸出2 |
|||
| style="vertical-align: top" | |
|||
* 範例輸入1 |
|||
* 範例輸出1 |
|||
* 範例說明1 |
|||
* 範例輸入2 |
|||
* 範例輸出2 |
|||
|} |
|||
==== 提示 ==== |
|||
{{TOJ side box |
{{TOJ side box |
||
|563|C. 車站 |
|||
|335|F. 參訪者們 |
|||
|509|C. Puyo |
|||
}} |
}} |
||
樹仍可以轉換為道路或鐵路,但加上「因為資源有限,所以能讓任兩個城市或車站連通即可」的設定。 |
|||
如有需要,可以提供一些額外提示。如果內容為解題必須的,不應撰寫於提示,應寫於本文中。 |
|||
{{clear}} |
|||
==== 最小生成樹 ==== |
|||
最小生成樹通常用於要建立道路相連多個城市,使得所有城市連通,權重為該條道路的建設成本,目標為總建設成本最低。 |
|||
=== 有根樹 === |
|||
{{TOJ side box |
{{TOJ side box |
||
|637|D. 本田小狼 |
|||
|330|A. Piñata |
|||
|331|B. 尼莫西妮 |
|||
|473|A. 好哈快捷鍵 |
|||
}} |
}} |
||
有根樹可以轉換為根節點位於山頂,邊為往山下的道路。 |
|||
亦可撰寫與解題毫無幫助,但與題目故事相關的小知識。 |
|||
{{clear}} |
|||
== 故事題材 == |
|||
== [[zhwiki:組建自動化|自動建置]] == |
|||
故事通常是由編寫者挑選自己熟悉的作品,內容包含日本動畫、遊戲、VTuber等等題材。並且可以在題敘中進行置入性行銷,推薦自己喜愛的作品。 |
|||
tps-starter<ref>https://github.com/TNFSH-Programming-Contest/tps-starter</ref> 使用了 GitHub Actions<ref>https://github.com/features/actions</ref>,對於建置題本和測資提供了簡易介面來執行構建,並包含自動建置、自動化測試等功能。 |
|||
=== 使用日本動畫的題目 === |
|||
{{reflist-talk}} |
|||
{| class="wikitable sortable" |
|||
|- |
|||
! 動畫季別 !!動畫名稱 !! 題目 !! 備註 |
|||
|- |
|||
<!-- |
|||
{{story-anime-row||||||}} |
|||
--> |
|||
{{story-anime-row|2017|7|Princess Principal|400|B. 羅馬數字|2018臺南一中資訊社寒訓練習賽}} |
|||
{{story-anime-row|2018|1|庫洛魔法使:透明牌篇|401|C. 封印解除|2018臺南一中資訊社寒訓練習賽}} |
|||
{{story-anime-row|2018|1|爆肝工程師的異世界狂想曲|402|D. 咒文詠唱|2018臺南一中資訊社寒訓練習賽}} |
|||
{{story-anime-row|2017|10|少女終末旅行|403|E. 旅行問題|2018臺南一中資訊社寒訓練習賽}} |
|||
{{story-anime-row|2020|1|戀愛中的小行星|507|A. 二分圖匹配|2020臺南一中校內程式設計大賽}} |
|||
{{story-anime-row|2020|1|戀愛中的小行星|508|B. 完美河道|2020臺南一中校內程式設計大賽}} |
|||
{{story-anime-row|2020|1|戀愛中的小行星|509|C. Puyo|2020臺南一中校內程式設計大賽}} |
|||
{{story-anime-row|2019|9|HELLO WORLD|547|0. Hello World|第七屆國中生程設營練習賽}} |
|||
{{story-anime-row|2020|7|魔王學院的不適任者~史上最強的魔王始祖,轉生就讀子孫們的學校~|548|A. 阿諾斯·波魯迪戈烏多|第七屆國中生程設營練習賽}} |
|||
{{story-anime-row|2016|1|為美好的世界獻上祝福!|553|F. 更改咒語|第七屆國中生程設營練習賽}} |
|||
{{story-anime-row|2020|4|輝夜姬想讓人告白~天才們的戀愛頭腦戰~|anime=輝夜姬想讓人告白~天才們的戀愛頭腦戰~第2季|554|G. 石上真男人|第七屆國中生程設營練習賽}} |
|||
{{story-anime-row|2020|2|哥布林殺手|anime=哥布林殺手:GOBLIN'S CROWN|555|A. 哥布林|109學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2020|7|果然我的青春戀愛喜劇搞錯了。 (動畫)|anime=果然我的青春戀愛喜劇搞錯了。完|556|B. 舞會|109學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2020|1|怕痛的我,把防禦力點滿就對了|564|D. 大楓樹|109學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2020|1||anime=緣結熊本|565|E. 熊本|109學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2020|10|熊熊勇闖異世界|566|A. 熊熊|109學年度資訊學科能力競賽臺南一中校內複選}} |
|||
{{story-anime-row|2020|7|Lapis Re:LiGHTs|567|B. LiGHTs|109學年度資訊學科能力競賽臺南一中校內複選}} |
|||
{{story-anime-row|2020|1|神推偶像登上武道館我就死而無憾|568|C. ChamJam|109學年度資訊學科能力競賽臺南一中校內複選}} |
|||
{{story-anime-row|2020|1|搖曳露營△|anime=房間露營△|569|D. 露營|109學年度資訊學科能力競賽臺南一中校內複選}} |
|||
{{story-anime-row|2017|1|幼女戰記|570|E. 存在X|109學年度資訊學科能力競賽臺南一中校內複選}} |
|||
{{story-anime-row|2021|1|轉生成蜘蛛又怎樣!|579|pA - 蜘蛛|SCIST 第一屆 演算法季後賽}} |
|||
{{story-anime-row|2021|4||anime=壽司大相撲|581|pB - 壽司|SCIST 第一屆 演算法季後賽}} |
|||
{{story-anime-row|2021|4|Vivy -Fluorite Eye's Song-|582|pC - Vivy|SCIST 第一屆 演算法季後賽}} |
|||
{{story-anime-row|2021|4|持續狩獵史萊姆三百年,不知不覺就練到LV MAX|583|pD - Slime|SCIST 第一屆 演算法季後賽}} |
|||
{{story-anime-row|2021|4|關於我轉生變成史萊姆這檔事|anime=轉生史萊姆日記 關於我轉生變成史萊姆這檔事|584|pE - 種田|SCIST 第一屆 演算法季後賽}} |
|||
{{story-anime-row|2021|7|陰晴不定的體操哥哥|627|A. ABC體操|110學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2020|7|果然我的青春戀愛喜劇搞錯了。 (動畫)|anime=果然我的青春戀愛喜劇搞錯了。完|628|B. 國中會考分發|110學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2021|7|白沙的Aquatope|629|C. GAMAGAMA|110學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2019|10|萌獸寵物店|630|D. 花子一口吞|110學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2021|7|關於我轉生變成史萊姆這檔事|anime=關於我轉生變成史萊姆這檔事第2期第2部分|631|E. 蓋歐格|110學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2021|7|Love Live! Superstar!!|632|F. 最小生成數|110學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2009|7|簡單易懂的現代魔法|633|G. 簡單易懂的現代魔法|110學年度資訊學科能力競賽臺南一中校內初選}} |
|||
{{story-anime-row|2018|10|JoJo的奇妙冒險_(電視動畫)|anime=JoJo的奇妙冒險·第四部·不滅鑽石|634|A. 吉良吉影想平靜地過日子|110學年度資訊學科能力競賽臺南一中校內複選}} |
|||
{{story-anime-row|2021|7|我們的重製人生|635|B. 學測分發|110學年度資訊學科能力競賽臺南一中校內複選}} |
|||
{{story-anime-row|2019|8|為美好的世界獻上祝福!紅傳說|636|C. 為美好的地牢獻上爆擊|110學年度資訊學科能力競賽臺南一中校內複選}} |
|||
{{story-anime-row|2021|4|本田小狼與我|637|D. 本田小狼|110學年度資訊學科能力競賽臺南一中校內複選}} |
|||
{{story-anime-row|1996|4|玩偶遊戲|638|E. 遞迴呀遞迴|110學年度資訊學科能力競賽臺南一中校內複選}} |
|||
|} |
|||
=== 使用《{{zhwiki|愛麗絲與藏六}}》的題目 === |
|||
=== 建置題本 === |
|||
* 106學年度台南一中資訊學科能力競賽校內初選 |
|||
若要將題本編譯成 PDF,按照以下步驟操作: |
|||
** {{TOJ|373}} - A.實驗場 |
|||
# 進入 GitHub repo。 |
|||
** {{TOJ|374}} - B.飢餓的Sana |
|||
# 點擊 Actions。 |
|||
** {{TOJ|375}} - C.餐桌禮儀 |
|||
# 在 Workflows 段落,點擊 Build pdf。<ref>參考連結:https://github.com/TNFSH-Programming-Contest/TPS-example/actions/workflows/build-pdf.yml</ref> |
|||
** {{TOJ|376}} - D.綁架 |
|||
# 點擊 Run workflow,在 Problem labels to build 輸入{{slink||題目編號}},例如「B」。 |
|||
** {{TOJ|377}} - E.奪回作戰 |
|||
# 點擊藍色 Run workflow 按鈕。 |
|||
** {{TOJ|378}} - F.避難 |
|||
# 等待 PDF 題本建置完成,約 2 分鐘。 |
|||
# 可在對應題目的 statement/index.pdf 找到建置的 PDF。<ref>參考連結:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/statement/index.pdf</ref> |
|||
=== 使用《{{zhwiki|高捷少女}}》的題目 === |
|||
{{reflist-talk}} |
|||
* 第四屆大臺南高一生程式設計排名賽 |
|||
** {{TOJ|330}} - A. Piñata |
|||
** {{TOJ|331}} - B. 尼莫西妮 |
|||
** {{TOJ|332}} - C. 棋盤 |
|||
** {{TOJ|333}} - D. 畢業 |
|||
** {{TOJ|334}} - E. 蛋糕 |
|||
** {{TOJ|335}} - F. 參訪者們 |
|||
** {{TOJ|336}} - G. 禮物 |
|||
* {{TOJ|399}} - A. 大數運算(2018臺南一中資訊社寒訓練習賽) |
|||
=== |
=== 使用《{{zhwiki|海綿寶寶}}》的題目 === |
||
* 107學年度國際資訊奧林匹亞研習營初選臺南一中校內選拔 |
|||
若題本已定稿,可開啟自動建置功能,之後對於相關檔案的修改都會觸發自動建置。刪除 statement/DISABLE_AUTO_BUILD<ref>https://github.com/TNFSH-Programming-Contest/tps-task-templates/blob/main/default/statement/DISABLE_AUTO_BUILD</ref> 即可開啟自動建置題本。 |
|||
** {{TOJ|461}} - A. 海綿寶寶的時鐘 |
|||
** {{TOJ|462}} - B. 海綿寶寶捉水母 |
|||
修改以下檔案將會觸發自動建置: |
|||
** {{TOJ|463}} - C. 我的酸黃瓜呢 |
|||
* scripts/statement.sh<ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/scripts/statement.sh</ref> |
|||
** {{TOJ|464}} - D. 找樂子就是要燒掉整個城製造出大大的炸彈 |
|||
* statement/*.jpg<ref>例如:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/statement/cover.jpg</ref> |
|||
** {{TOJ|465}} - E. 打屁屁大隊 |
|||
* statement/index.md<ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pB/statement/index.md</ref> |
|||
** {{TOJ|466}} - F. 升天電梯 |
|||
* template.tex<ref>https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/template.tex</ref> |
|||
* 2020臺南一中校內程式設計大賽 |
|||
* {{slink||cover.tex}}僅會構建 pA 的題本 |
|||
** {{TOJ|510}} - D. 公平洗牌 |
|||
* {{slink||problem.json}}的 |
|||
** {{TOJ|511}} - E. 野海熊防護圈 |
|||
** contest_name:{{slink||競賽名稱}} |
|||
** {{TOJ|512}} - F. 樓層交換 |
|||
** problem_label:{{slink||題目編號}} |
|||
** name:{{slink||題目英文名稱}} |
|||
** title:{{slink||題目名稱}} |
|||
** memory_limit:{{slink||記憶體限制}} |
|||
** time_limit:{{slink||時間限制}} |
|||
* {{slink||subtasks.json}}的 index、score、text ,參見{{slink||子任務}}。 |
|||
{{reflist-talk}} |
|||
=== 合併題本 === |
|||
在所有題目的題本皆完成,才進行合併題本,參考{{slink||建置題本}}的操作,在第 4 步驟的 Problem labels to build 輸入「+」,即會合併題本輸出於 pA/attachments/problems.pdf。<ref>參考連結:https://github.com/TNFSH-Programming-Contest/cms-environment-testing-problem/blob/main/pA/attachments/problems.pdf</ref> |
|||
{{reflist-talk}} |
|||
=== 建置測資 === |
|||
若要自動產生測資 input、output、進行標程比較: |
|||
# 進入 GitHub repo。 |
|||
# 點擊 Actions。 |
|||
# 在 Workflows 段落,點擊 Build tests。<ref>參考連結:https://github.com/TNFSH-Programming-Contest/TPS-example/actions/workflows/build-tests.yml</ref> |
|||
# 點擊 Run workflow。 |
|||
#* 若修改了{{slink||產測資}}程式,在 Problem labels to build inputs 輸入{{slink||題目編號}},例如「B」,其他欄位不需重複輸入題號。將會自動建置輸入及輸出,若測資有變動,亦會自動測試標程。 |
|||
#* 若僅修改了{{slink||標程}},導致僅有輸出會變動,在 Problem labels to build outputs 輸入{{slink||題目編號}},其他欄位不需重複輸入題號。將會自動建置輸出,若測資有變動,亦會自動測試標程。 |
|||
#* 若僅要重新執行標程測試,在 Problem labels to run solutions 輸入{{slink||題目編號}}。 |
|||
# 點擊藍色 Run workflow 按鈕。 |
|||
# 等待測資建置完成。 |
|||
# 可在對應題目的{{slink||tests}}資料夾找到建置的測資。標程測試則在{{slink||solutions-check.txt}}。 |
|||
{{reflist-talk}} |
|||
=== 自動建置測資 === |
|||
若產測資程式和標程皆已定稿,可開啟自動建置功能,之後對於相關檔案的修改都會觸發自動建置。刪除 tests/DISABLE_AUTO_BUILD<ref>https://github.com/TNFSH-Programming-Contest/tps-task-templates/blob/main/default/tests/DISABLE_AUTO_BUILD</ref> 即可開啟自動建置測資。 |
|||
修改以下檔案將會觸發自動建置 input: |
|||
* {{slink||gen}}內的所有檔案 |
|||
修改以下檔案將會觸發自動建置 output: |
|||
* 在{{slink||solutions.json}}內設定的 model_solution 對應檔案。請注意:若變更 model_solution 的目標檔案可能不會觸發自動建置。 |
|||
修改以下檔案將會觸發自動建置 solutions: |
|||
* {{slink||solution}}內的所有檔案 |
|||
* {{slink||solutions.json}} |
|||
{{reflist-talk}} |
於 2022年8月28日 (日) 01:07 的修訂
使用故事來包裝題目敘述,可以幫助參賽者更容易了解題目,又或是考驗參賽者的閱讀理解能力。
包裝程度比較
可參考 TOJ 的題目 | |
|
以下使用的範例為 TOJ 570(109 學年度資訊學科能⼒競賽臺南⼀中校內複選,E. 存在X)在準備競賽時題目敘述演進過程的真實案例。
Level 1
問是否可以以 骨牌組成給定的遞增圖形。
由出題者寫出來最原始的題目敘述,通常還需要額外的口頭補充解釋才能讓其他人理解題目,這樣的敘述僅能夠讓命題團隊的其他成員記得題目內容,但不足以在正式競賽中使用。
Level 2
給一個 的方格圖,其中每個格子皆有 黑/白 其中一個顏色。
顏色符合以下條件:
對於第 行, 為白色,而 為黑色
對於 ,。
問是否可以用 的骨牌將所有白色區塊填滿,使得任一個白色格子恰被一個骨牌覆蓋。
由出題者完善的題目敘述,這樣的敘述能夠讓未看過題目的人在沒有額外口頭補充下理解題目。若沒有能力改寫成 Level 3 的題敘,在正式競賽中使用這種題敘尚可接受。
Level 3
那是有一個魔法軍隊的戰爭時代,譚雅是帝國軍二〇三航空魔導大隊的大隊長。
帝國的國力逐漸變得強大,引起鄰國的不安,想趕在被消滅前先下手為強。
這天某個國家又跨越邊境前來進犯,譚雅奉命前去驅趕敵人。
敵軍佔領的區域可以由左至右等距分成 格,而從邊境線往內陸也按相同距離切割成數格。
譚雅發現越靠右方的戰線,離邊境的距離可能與相鄰左方相等或更遠。
魔導大隊的魔法攻擊可以轟炸 或 的方格。
所有敵軍佔領的區域都必須轟炸,但為了節省資源,不想要重複轟炸相同格子,也不想轟炸沒有敵軍佔領的區域。
請問譚雅是否能達成這個目標呢?
經過故事設定的包裝,是正式競賽中常見的題目敘述,能夠讓參賽者充分理解題意。
目的
題目敘述通常會編寫故事來讓參賽者融入該問題的情境,以更好地了解題目所要問的內容。
賦予數值意義
可參考 TOJ 的題目 | |
|
110 學年度資訊學科能力競賽臺南一中校內初選 D. 花子一口吞
給長度 N 的正整數數列 A,求一區間使「區間和 mod K」最大。
——原始題敘(Level 2)
有容量不同的飼料盆排成一列,要把一個區間的飼料全部吃完,吃的時候會把嘴巴塞滿才吞下去,詢問最後一口剩餘在嘴中的飼料數量。
——包裝題敘(Level 3)
雖然原始題敘已經充分說明題目,但若僅使用原始題敘,參賽者可能就會有「數列?區間?為什麼要 mod K?」等疑惑,但透過故事包裝,將數列轉換為飼料盆內的飼料量、K 轉換為嘴巴的容量、mod K 轉換為吞下飼料的行為,讓題目變成現實生活中可能發生的情境,先透過故事引導參賽者融入情境,這時候再提出問題,便很容易理解問題是什麼。一些演算法原本就能解決現實生活中的問題,因此以實際會遇到的情境去包裝題目問題就能讓題目變得很易懂。
合理化題目
可參考 TOJ 的題目 | |
|
有 個人要爬 層樓梯。
每個人一開始都在第 層,且第 個人會每秒上升 層。
現在有 罐運動飲料,每一瓶可以讓第 個人瞬間上升 層。一個人可以喝多瓶,也可以完全不喝。
請問在最優的分配下,最快幾秒可以讓所有人可以上升到樓梯頂部 ( 層數 即視為在樓梯頂部 )。——未採用題敘(Level 3)
雪乃和伊呂波在準備畢業舞會,準備工作非常繁雜,有 項工作需要完成。
為了好好管理進度,雪乃將每項工作都等分成 份。
而雪乃和伊呂波一起工作的話,對於第 項工作,每天可以完成那項工作的 份(每項工作每天都會做,且恰好完成 份,無法把時間挪用給其他工作,就算有一些項目的工作已經完成,也不會增加其他工作的效率)。
但是怕工作做不完,恰好又有 筆經費,所以決定把部份工作外包。
每筆經費對於第 項工作,可以將那項工作的 份外包,外包的部分可不計入花費時間直接視為完成。
請問在最佳分配經費的情況下,最少幾天就能完成所有工作(不足一天以一天計)。——正式題敘(Level 3)
雖然未採用題敘直接在正式競賽中使用並沒有什麼問題……但運動飲料可以讓人「瞬間」上升怎麼想都不合理,而且運動飲料不是增加每個人的體能而是讓人直接上升,所以對不同人的效果為何有不同效果()也缺乏合理解釋。改成工作外包後,不同工作在同樣經費下能外包的工作量本來就不同,而且外包也能作為工作量直接消失的理由。
測驗閱讀理解
2008 網際網路程式設計全國大賽高中組決賽 B. 幼稚國王去旅行
輸出 1 就是答案。
——根本是答案(Level 1)
參見 題本。
——包裝題敘(Level 3)
一個反例是將簡單的題目包裝起來,測驗參賽者的閱讀理解能力。另外對於 Hello World 或是 A+B 等題目,包裝一點故事才不會讓題敘過短。
總結
總結,使用故事來包裝題目敘述可以:
- 更容易理解題目。
- 純粹測試閱讀能力。
- 讓題目有趣一些。
- 讓不會解題的參賽者在競賽中不至於那麼無聊。
- 讓出題者對喜愛的作品置入性行銷。
題本架構
一般
可參考 TOJ 的題目 | |
能使用故事來包裝的題目,題目本文的架構通常如下:
一開始用少數幾句話介紹世界觀,通常與所參考的作品相同,這邊的介紹對解題通常沒有幫助,例如:
- TOJ 629 ─ GAMAGAMA 水族館面臨即將停業的危機
- TOJ 630 ─ 自稱為半龍人的貪吃少女 — 花子,實際上卻是魔界四大公爵-龍族法夫納家的下任家主!
- TOJ 637 ─ 今天小熊騎著本田小狼 50 兜風
進一步介紹故事劇情,這裡就會提到測資中會出現的設定,例如城市與道路的數量,例如:
- TOJ 629 ─ GAMAGAMA 水族館有兩條觀察大型水族箱的海底隧道...
- TOJ 630 ─ 她會選定某盆飼料開始一顆顆往嘴巴裡吃,一但到達嘴巴能裝的最多數量 K,就會一口吞下!
- TOJ 637 ─ 如果將所有的景點、店家等等都當作是一個節點,並且依序將節點從 1~n 編號,制高點編號為 1
最後提出題目真正要詢問的問題,例如:
可參考 TOJ 的題目 | |
如果題意需要圖片輔助說明,可放在本文尾端(較短的本文)或其他合適地方(較長的本文),如果題目沒有插圖,亦可放置在插圖處。
無法包裝的題目
但還是有一些題目實在不會在現實生活中遇到,這時候只好勉為其難使用爛招,也就是在題目敘述寫一些無關緊要的描述,最後再直白的亮出問題。
Hello World
可參考 TOJ 的題目 | |
對於直接輸出 Hello World 的題目,實在沒有什麼劇情可言,通常做法是隨便介紹一下 Hello World 的由來,然後在輸出說明要求輸出 Hello World 而已。
數學題目
題目:請用「XX」造句。
答案:「今天老師出了一個題目,讓我們用XX造句。」
——造句的爛招
可參考 TOJ 的題目 | |
如同以上造句的通用解答,實際上對於所有題目也可以使用以下的通用敘述:
...(毫無意義的故事,通常與教室、老師有關)...
老師問了一個問題,請解出 XXXXX(題目本身)。
——數學題目的題目本文
插圖
題目插圖通常與題目本文中使用的故事相關,來提高參賽者解題興趣,例如使用動畫設定作為背景故事則會使用該動畫的截圖。無論有無插圖都不影響題意理解,故插圖不是必須的。插圖通常放置於標題下方、本文的最上方。
\begin{figure}[h]
\centering
\includegraphics[width=12cm]{FILENAME.jpg}
\caption{圖片說明,出自動畫《動畫名稱》}
\end{figure}
可參考 TOJ 的題目 | |
|
建議可使用有創用CC等授權條款,或其他明確向公眾授權的圖片,例如吉卜力工作室的動畫劇照[2]等。
引用受著作權保護的圖片將依著作權法[3]第 52 條[4]以教學為目的主張合理使用。唯應依同法第 64 條[5]標明出處,在圖片說明以「出自動畫《動畫名稱》」等字樣標示。另根據同法第 65 條[6]第 2 款第 3 項,縮小圖片解析度,建議在 12cm 的顯示效果下將圖片寬度壓縮至 640 px(16:9 的圖片高度為 360px)。
如果可行,應嘗試向著作權人取得授權(如右圖),依著作權法第 65 條[6]第 3 項確認合理使用範圍,例如第四屆大臺南高一生程式設計排名賽所使用的圖片。
參考資料
- ↑ https://github.com/TNFSH-Programming-Contest/tps-task-templates/blob/main/default/statement/index.md
- ↑ https://www.ghibli.jp/info/013409/
- ↑ https://law.moj.gov.tw/LawClass/LawAll.aspx?PCode=J0070017
- ↑ https://law.moj.gov.tw/LawClass/LawSingle.aspx?pcode=J0070017&flno=52
- ↑ https://law.moj.gov.tw/LawClass/LawSingle.aspx?pcode=J0070017&flno=64
- ↑ 6.0 6.1 https://law.moj.gov.tw/LawClass/LawSingle.aspx?pcode=J0070017&flno=65
資料結構與故事設定
求餘數
可參考 TOJ 的題目 | |
|
除法的求餘數可以轉換成多次的減法,例如:
- 使用容量為 K 的水瓢從水缸舀水直到無法盛滿水瓢,問最後剩餘的水量。
若僅是答案過大而需要取餘數輸出,可以直接寫在輸出說明,不一定要作為題敘的一部分。
圖
可參考 TOJ 的題目 | |
|
圖論問題通常可以轉換為:
- 城市與相連的道路。
- 車站與相連的鐵路。
有向無環圖
可參考 TOJ 的題目 | |
|
有向無環圖可拆成「有向」和「無環」兩個性質。「有向」可簡單地描述為單向道即可。「無環」則可以在題目中暗示說不會走到重複的點。
樹
可參考 TOJ 的題目 | |
|
樹仍可以轉換為道路或鐵路,但加上「因為資源有限,所以能讓任兩個城市或車站連通即可」的設定。
最小生成樹
最小生成樹通常用於要建立道路相連多個城市,使得所有城市連通,權重為該條道路的建設成本,目標為總建設成本最低。
有根樹
可參考 TOJ 的題目 | |
|
有根樹可以轉換為根節點位於山頂,邊為往山下的道路。
故事題材
故事通常是由編寫者挑選自己熟悉的作品,內容包含日本動畫、遊戲、VTuber等等題材。並且可以在題敘中進行置入性行銷,推薦自己喜愛的作品。
使用日本動畫的題目
動畫季別 | 動畫名稱 | 題目 | 備註 |
---|---|---|---|
2017年7月 | Princess Principal | TOJ 400 - B. 羅馬數字 | 2018臺南一中資訊社寒訓練習賽 |
2018年1月 | 庫洛魔法使:透明牌篇 | TOJ 401 - C. 封印解除 | 2018臺南一中資訊社寒訓練習賽 |
2018年1月 | 爆肝工程師的異世界狂想曲 | TOJ 402 - D. 咒文詠唱 | 2018臺南一中資訊社寒訓練習賽 |
2017年10月 | 少女終末旅行 | TOJ 403 - E. 旅行問題 | 2018臺南一中資訊社寒訓練習賽 |
2020年1月 | 戀愛中的小行星 | TOJ 507 - A. 二分圖匹配 | 2020臺南一中校內程式設計大賽 |
2020年1月 | 戀愛中的小行星 | TOJ 508 - B. 完美河道 | 2020臺南一中校內程式設計大賽 |
2020年1月 | 戀愛中的小行星 | TOJ 509 - C. Puyo | 2020臺南一中校內程式設計大賽 |
2019年9月 | HELLO WORLD | TOJ 547 - 0. Hello World | 第七屆國中生程設營練習賽 |
2020年7月 | 魔王學院的不適任者~史上最強的魔王始祖,轉生就讀子孫們的學校~ | TOJ 548 - A. 阿諾斯·波魯迪戈烏多 | 第七屆國中生程設營練習賽 |
2016年1月 | 為美好的世界獻上祝福! | TOJ 553 - F. 更改咒語 | 第七屆國中生程設營練習賽 |
2020年4月 | 輝夜姬想讓人告白~天才們的戀愛頭腦戰~第2季 | TOJ 554 - G. 石上真男人 | 第七屆國中生程設營練習賽 |
2020年2月 | 哥布林殺手:GOBLIN'S CROWN | TOJ 555 - A. 哥布林 | 109學年度資訊學科能力競賽臺南一中校內初選 |
2020年7月 | 果然我的青春戀愛喜劇搞錯了。完 | TOJ 556 - B. 舞會 | 109學年度資訊學科能力競賽臺南一中校內初選 |
2020年1月 | 怕痛的我,把防禦力點滿就對了 | TOJ 564 - D. 大楓樹 | 109學年度資訊學科能力競賽臺南一中校內初選 |
2020年1月 | 緣結熊本 | TOJ 565 - E. 熊本 | 109學年度資訊學科能力競賽臺南一中校內初選 |
2020年10月 | 熊熊勇闖異世界 | TOJ 566 - A. 熊熊 | 109學年度資訊學科能力競賽臺南一中校內複選 |
2020年7月 | Lapis Re:LiGHTs | TOJ 567 - B. LiGHTs | 109學年度資訊學科能力競賽臺南一中校內複選 |
2020年1月 | 神推偶像登上武道館我就死而無憾 | TOJ 568 - C. ChamJam | 109學年度資訊學科能力競賽臺南一中校內複選 |
2020年1月 | 房間露營△ | TOJ 569 - D. 露營 | 109學年度資訊學科能力競賽臺南一中校內複選 |
2017年1月 | 幼女戰記 | TOJ 570 - E. 存在X | 109學年度資訊學科能力競賽臺南一中校內複選 |
2021年1月 | 轉生成蜘蛛又怎樣! | TOJ 579 - pA - 蜘蛛 | SCIST 第一屆 演算法季後賽 |
2021年4月 | 壽司大相撲 | TOJ 581 - pB - 壽司 | SCIST 第一屆 演算法季後賽 |
2021年4月 | Vivy -Fluorite Eye's Song- | TOJ 582 - pC - Vivy | SCIST 第一屆 演算法季後賽 |
2021年4月 | 持續狩獵史萊姆三百年,不知不覺就練到LV MAX | TOJ 583 - pD - Slime | SCIST 第一屆 演算法季後賽 |
2021年4月 | 轉生史萊姆日記 關於我轉生變成史萊姆這檔事 | TOJ 584 - pE - 種田 | SCIST 第一屆 演算法季後賽 |
2021年7月 | 陰晴不定的體操哥哥 | TOJ 627 - A. ABC體操 | 110學年度資訊學科能力競賽臺南一中校內初選 |
2020年7月 | 果然我的青春戀愛喜劇搞錯了。完 | TOJ 628 - B. 國中會考分發 | 110學年度資訊學科能力競賽臺南一中校內初選 |
2021年7月 | 白沙的Aquatope | TOJ 629 - C. GAMAGAMA | 110學年度資訊學科能力競賽臺南一中校內初選 |
2019年10月 | 萌獸寵物店 | TOJ 630 - D. 花子一口吞 | 110學年度資訊學科能力競賽臺南一中校內初選 |
2021年7月 | 關於我轉生變成史萊姆這檔事第2期第2部分 | TOJ 631 - E. 蓋歐格 | 110學年度資訊學科能力競賽臺南一中校內初選 |
2021年7月 | Love Live! Superstar!! | TOJ 632 - F. 最小生成數 | 110學年度資訊學科能力競賽臺南一中校內初選 |
2009年7月 | 簡單易懂的現代魔法 | TOJ 633 - G. 簡單易懂的現代魔法 | 110學年度資訊學科能力競賽臺南一中校內初選 |
2018年10月 | JoJo的奇妙冒險·第四部·不滅鑽石 | TOJ 634 - A. 吉良吉影想平靜地過日子 | 110學年度資訊學科能力競賽臺南一中校內複選 |
2021年7月 | 我們的重製人生 | TOJ 635 - B. 學測分發 | 110學年度資訊學科能力競賽臺南一中校內複選 |
2019年8月 | 為美好的世界獻上祝福!紅傳說 | TOJ 636 - C. 為美好的地牢獻上爆擊 | 110學年度資訊學科能力競賽臺南一中校內複選 |
2021年4月 | 本田小狼與我 | TOJ 637 - D. 本田小狼 | 110學年度資訊學科能力競賽臺南一中校內複選 |
1996年4月 | 玩偶遊戲 | TOJ 638 - E. 遞迴呀遞迴 | 110學年度資訊學科能力競賽臺南一中校內複選 |
使用《愛麗絲與藏六》的題目
- 106學年度台南一中資訊學科能力競賽校內初選
使用《高捷少女》的題目
- 第四屆大臺南高一生程式設計排名賽
- TOJ 399 - A. 大數運算(2018臺南一中資訊社寒訓練習賽)