TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (18/18)

Submission's AC Ratio

71.4% (20/28)

Description

亞歷山大將軍準備派遣一支精銳部隊前往攻打鄰國,他麾下有三個種族 – 「人類」、「骷髏族」和「哥布林族」;每個種族各有不同兵種,例如人類有騎士、法師、弓箭手,而哥布林族有勇士、投矛手、吹箭手等等。
為了平衡部隊的組成份子,亞歷山大會從三個種族各選擇一個兵種。此外,他還會考慮這個部隊是否能涵蓋「對空攻擊」、「範圍攻擊」和「遠距攻擊」三種特性。舉例來說,亞歷山大將軍麾下的三個種族各有三個兵種如下:

亞歷山大可以選擇法師、骷髏兵團和勇士這個組合,因為這個組合涵蓋了三個種族和三個特性;但他不能選擇弓箭手、骷髏兵團和投矛手這個組合,因為這個組合未能涵蓋「範圍攻擊」這個特性;他也不能選擇弓箭手、炸彈兵和炸彈塔這個組合,因為這個組合未能涵蓋「哥布林」這個種族。
亞歷山大為這個問題想了很多天,國王感到很不解,這麼簡單的事情怎麼想那麼久。亞歷山大為了向國王解釋,他想要告訴國王總共有多少種可能的組合,請你幫幫他。

Input Format

第一列為一個正整數 $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,代表具有該特性;否則,不具有該特性。

Output Format

輸出共有多少個兵種組合可以涵蓋三個種族和三個特性。

Sample Input

Sample Input #1
3
3 1 0 0
1 0 0 1
2 0 1 0

Sample Input #2
9
1 0 0 0
1 1 1 1
2 0 1 1
1 1 0 1
2 0 0 0
3 0 0 0
3 1 0 1
3 0 1 1
2 0 1 1

Sample Output

Sample Output #1
1

Sample Output #2
18

Hints

本題共有二個子題,每一子題可有多筆測試資料:
第一子題的測試資料 $N \leq 100$,全部解出可獲23 分;
第二子題的測試資料 $N \leq 10000$,全部解出可獲77 分。

Problem Source

106學年度高級中學資訊學科能力競賽決賽 程式設計試題第三題

Subtasks

For Testdata: 0 ~ 9, Score: 23
For Testdata: 10 ~ 19, Score: 77
No. Time Limit (ms) Memory Limit (KiB)
0 500 524288
1 500 524288
2 500 524288
3 500 524288
4 500 524288
5 500 524288
6 500 524288
7 500 524288
8 500 524288
9 500 524288
10 500 524288
11 500 524288
12 500 524288
13 500 524288
14 500 524288
15 500 524288
16 500 524288
17 500 524288
18 500 524288
19 500 524288