Quân mã

View as PDF

Submit solution

Points: 0.58 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Polish OI 3
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một bàn cờ vua có kích thước ~3 \times N~, ~3~ hàng và ~N~ cột, trong đó ~1 \le N \le 100~, và một tập gồm ~Z~ ô. Các dòng được đánh số ~1~ đến ~3~ từ trên xuống dưới, các cột được đánh số ~1~ đến ~N~ từ trái sang phải.

Các quân mã không được đặt trên các ô thuộc tập ~Z~. Không có hai quân mã nào được tấn công lẫn nhau. Giả sử mỗi cột có nhiều nhất một ô thuộc tập ~Z~. Khi đó, tập ~Z~ có thể mô tả bởi dãy ~k_{1}~, ~k_{2}~, ..., ~k_{N}~ với ~k_{i}~ thuộc ~\{0, 1, 2, 3\}~. Nếu ~k_{i} = 0~, không có ô nào trên cột ~i~ thuộc tập ~Z~, trong các trường hợp còn lại, ~k_{i}~ là chỉ số dòng của ô trên cột này thuộc tập ~Z~.

Cho biết số cột ~N~ của bàn cờ và dãy mô tả tập ~Z~, hãy tìm số nhiều nhất quân mã ~M~ có thể đặt sao cho thỏa mãn các điều kiện đã nêu, và ~L~, số cách đặt ~M~ quân mã lên bàn cờ.

Input

  • Dòng đầu tiên chứa số nguyên dương ~N \le 100~, là số cột trên bàn cờ.
  • Mỗi dòng trong số ~N~ dòng tiếp theo chứa một số thuộc tập ~\{0, 1, 2, 3\}~, là dãy mô tả tập ~Z~.

Output

In ra hai số nguyên ~M~ và ~L~ cách nhau bởi khoảng trắng.

Sample Input

2
1
0

Sample Output

4 2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.