亞歷山大將軍準備派遣一支精銳部隊前往攻打鄰國,他麾下有三個種族 – 「人類」、「骷髏族」和「哥布林族」;每個種族各有不同兵種,例如人類有騎士、法師、弓箭手,而哥布林族有勇士、投矛手、吹箭手等等。
為了平衡部隊的組成份子,亞歷山大會從三個種族各選擇一個兵種。此外,他還會考慮這個部隊是否能涵蓋「對空攻擊」、「範圍攻擊」和「遠距攻擊」三種特性。舉例來說,亞歷山大將軍麾下的三個種族各有三個兵種如下:
亞歷山大可以選擇法師、骷髏兵團和勇士這個組合,因為這個組合涵蓋了三個種族和三個特性;但他不能選擇弓箭手、骷髏兵團和投矛手這個組合,因為這個組合未能涵蓋「範圍攻擊」這個特性;他也不能選擇弓箭手、炸彈兵和炸彈塔這個組合,因為這個組合未能涵蓋「哥布林」這個種族。
亞歷山大為這個問題想了很多天,國王感到很不解,這麼簡單的事情怎麼想那麼久。亞歷山大為了向國王解釋,他想要告訴國王總共有多少種可能的組合,請你幫幫他。
第一列為一個正整數 $N (1 \leq N \leq 10000)$,代表亞歷山大麾下有多少種兵種。接下來的 $N$列,每一列有四個正整數 $c_i (c_i \in \{1, 2, 3 \})$、$a_i$、$r_i$ 和 $d_i$ ($a_i, r_i, d_i \in \{0, 1 \}$),彼此間以一個空白隔開,分別代表種族、對空攻擊、範圍攻擊和遠距攻擊。$a_i$、$r_i$ 和 $d_i$ 的值若為 1,代表具有該特性;否則,不具有該特性。
輸出共有多少個兵種組合可以涵蓋三個種族和三個特性。
本題共有二個子題,每一子題可有多筆測試資料:
第一子題的測試資料 $N \leq 100$,全部解出可獲23 分;
第二子題的測試資料 $N \leq 10000$,全部解出可獲77 分。
106學年度高級中學資訊學科能力競賽決賽 程式設計試題第三題
No. | Testdata Range | Score |
---|---|---|
1 | 0~9 | 23 |
2 | 10~19 | 77 |