/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
18 行 6 列のマス目が与えられます。それぞれのマスには 0,1,? のいずれかが書かれており、上から i 行目、左から j 列目のマスには s_{i,j} が書かれています。
全ての ? が書かれたマスについて、書かれた文字を 0 か 1 のどちらかに書き換える方法のうち、書き換えを行った後のマス目が下記の条件を満たすようなものはいくつありますか？
条件：各マスに書かれた数は、そのマスと上下左右のマスに書かれた 5 つの数たちの中央値と等しい (マス目の外には 0 と書かれたマスが存在するものとして扱う)
制約
- s_{i,j} は
0、1、?のいずれか
入力
入力は以下の形式で標準入力から与えられる。
s_{1,1} \cdots s_{1,6}
\vdots
s_{18,1} \cdots s_{18,6}
出力
マス目が問題文中の条件を満たすような書き換え方の個数を出力せよ。
入力例 1
??0000 ??0000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
出力例 1
2
- 全ての
?マスに0を書き込んだとき、あるいは全ての?マスに1を書き込んだときのみ問題文中の条件が満たされます。
入力例 2
???000 ???000 ???000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
出力例 2
16
入力例 3
?01000 1101?1 100111 1?11?? ???00? 00011? 1?1??1 000101 100?11 1010?? ?101?? ?1??10 ????10 ?1??0? 1?1??? 110?1? 0000?0 001?10
出力例 3
0
- 条件を満たす書き込み方はありません。
入力例 4
?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ??????
出力例 4
243882696958399859
Score : 6 points
Warning
Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
Given is a grid with 18 rows and 6 columns. Each square has 0, 1, or ? written on it; written on the square at the i-th row from the top and j-th column from the left is s_{i,j}.
How many ways are there to replace each ? written on a square with 0 or 1 so that the grid will satisfy the following condition?
Condition: The number written on each square is equal to the median of the numbers written on the following five squares: the square itself and the squares horizontally or vertically adjacent to the square. (Assume that the area outside the grid is filled by squares with 0 written on them.)
Constraints
- s_{i,j} is
0,1, or?.
Input
Input is given from Standard Input in the following format:
s_{1,1} \cdots s_{1,6}
\vdots
s_{18,1} \cdots s_{18,6}
Output
Print the number of ways to replace the characters so that the grid will satisfy the condition in the statement.
Sample Input 1
??0000 ??0000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
Sample Output 1
2
- The condition is satisfied only if we write
0in every?square or write1in every?square.
Sample Input 2
???000 ???000 ???000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000
Sample Output 2
16
Sample Input 3
?01000 1101?1 100111 1?11?? ???00? 00011? 1?1??1 000101 100?11 1010?? ?101?? ?1??10 ????10 ?1??0? 1?1??? 110?1? 0000?0 001?10
Sample Output 3
0
- There is no way to write numbers that satisfies the condition.
Sample Input 4
?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ?????? ??????
Sample Output 4
243882696958399859