TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (84/84)

Submission's AC Ratio

69.5% (116/167)

Tags

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 1

3
3 1 0 0
1 0 0 1
2 0 1 0

Sample Output 1

1

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 2

18

Hints

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0~9 23
2 10~19 77

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 500 524288 262144 1
1 500 524288 262144 1
2 500 524288 262144 1
3 500 524288 262144 1
4 500 524288 262144 1
5 500 524288 262144 1
6 500 524288 262144 1
7 500 524288 262144 1
8 500 524288 262144 1
9 500 524288 262144 1
10 500 524288 262144 2
11 500 524288 262144 2
12 500 524288 262144 2
13 500 524288 262144 2
14 500 524288 262144 2
15 500 524288 262144 2
16 500 524288 262144 2
17 500 524288 262144 2
18 500 524288 262144 2
19 500 524288 262144 2