時間制限: 1000MS
メモリ制限: 65536K
問題文
Background
トムの先生は2つのマスが取り除かれた42個のチェス盤を取り出してトムに難題を投げかけた。その先生は42個のうちいくつのチェス盤がちょうど31個のドミノで覆えるのか知りたいとのことだった。先生はもしこの問題をちゃんと解くことができたらチョコレートを10個あげるとトムに約束した。トムはチョコレートが大好きだったが、この問題を解くほどの力はなかった。そこでトムは兄のジョンに助けを求めることにした。ジョンは(彼もチョコレートが大好きなので)10個のうち半分のチョコレートを貰い受けることを条件にトムを助けてやることにした。
ジョンは考えるよりもプログラムを書くことの方が得意だったのでプログラムを書くことにした。ジョンを助けてもらえないだろうか？残念ながらあなたはチョコレートを貰えないが、ジョンを助けることでこのコンテストで優勝することができるかもしれない。
Problem
31個のドミノと8*8の大きさのチェス盤が与えられる。チェス盤は異なる2つのマスが取り除かれている。行a列bにあるマスは (a, b) で表される(ただし a, b は {1, ... , 8} の要素である)。
ドミノの大きさは2*1で、ちょうどチェス盤のマス目に合うように縦向きか横向きに置くことができる。すなわち、ひとつのドミノは {(a, b), (a, b+1)} か {(b, a), (b+1, a)}の2つのマスを埋めることができる(ただし a は {1, ... , 8}の要素であり b は {1, ... , 7}の要素である)。目的は、与えられたチェス盤を31個のドミノで全部埋めることができるかを決定することである。
たとえば図1のようにマス (8, 4) と (2, 5) が取り除かれているチェス盤の場合は31個のドミノでこのチェス盤を完全に覆うことができる。
入力
入力の1行目にはシナリオの数 k が書かれている。続く k 行にはそれぞれ4つの整数 a, b, c, d が空白区切りで書かれている。これらの整数はすべて {1, ... , 8}の要素であり、チェス盤から取り除かれたマスが (a, b) と (c, d) であることを示している。(a, b) != (c, d) を仮定してよい。
出力
各シナリオに対する出力は "Scenario #i:" という行から始まる。ここで i はシナリオの番号であり、その番号は1から始まる。次の行には、もしそのシナリオのチェス盤を覆うことができるのなら 1 を、できないのなら 0 が出力される。各シナリオに対する出力は空行で終わる。
入力例
3 8 4 2 5 8 8 1 1 4 4 7 1
出力例
Scenario #1: 1
Scenario #2: 0
Scenario #3: 0
出典
TUD Programming Contest 2005, Darmstadt, Germany