読者です 読者をやめる 読者になる 読者になる

Qualification Round 1 問題A 日本語訳

現在開催中のGoogle Code Jamですが、
拙い英語力で日本語訳してみました。
日本時間の5月9日(日)午前8時までに登録・解答すれば、
なんと99点満点中33点獲得するだけで次の大会に進めますので、
お気軽にトライしてみることをお勧めします。


問題A
http://code.google.com/codejam/contest/dashboard?c=433101#s=p0

スナッパーという機械があり、これには入力端子と出力端子が1つずつあります。
出力端子は「他のスナッパーの入力端子」か「電灯」のいずれかにつながれます。

スナッパーが「ON」の状態でかつ電力が供給されている場合、
そのスナッパーは出力端子に電力を供給します。
スナッパーは指でカチッとスイッチを切り替えることができ、
「ON」と「OFF」の2つの状態を取り得ます。

今、N個のスナッパーがあり、
1つ目のスナッパーの入力端子はコンセント(電力供給元)につながれています。
2つ目のスナッパーの入力端子は1つ目のスナッパーの出力端子につながれ、
3つ目のスナッパーの入力端子は2つ目のスナッパーの出力端子につながれ、
という具合に直列につながれています。
N個目のスナッパーの出力端子には電灯がつながれています。

最初は全てのスナッパーが「OFF」の状態になっており、
すなわち電灯は消えている状態です。
1つ目のスナッパーのスイッチを切り替えると、
1つ目のスナッパーがONに切り替わり、
2つ目のスナッパーに電力が供給されるようになります。
再び1つ目のスナッパーのスイッチを切り替えると、
1つ目のスナッパーがOFFに切り替わるので
2つ目のスナッパーに電力が供給されなくなりますが、
2つ目のスナッパーはONになったままとなります。
そして再び1つ目のスナッパーのスイッチを切り替えると、
1つ目がONになり、2つ目もONになります。
ここでもし電灯が2つ目のスナッパーにつながれていれば、電灯は点灯します。

このようにして、1つ目のスナッパーのスイッチをK回切り替えたとき、
電灯は点いているでしょうか? 電灯につながれているスナッパーが
電灯に電力を供給していれば、電灯は点きます。

■ 入力

1行目にテストケースの数Tが記され、その後T行が続きます。
T行は2つの整数値、NとKを含みます。

■ 出力

全てのテストケースにおいて、 "Case #x: y" という出力をして下さい。
ただし x は1から始まるテストケースIDで、y は "ON" か "OFF" のいずれかです。

■ 制限

1 ≦ T ≦ 10,000

■ Small dataset

1 ≦ N ≦ 10
0 ≦ K ≦ 100

■ Large dataset

1 ≦ N ≦ 30
0 ≦ K ≦ 100,000,000

入力例:

4
1 0
1 1
4 0
4 47

出力例:

Case #1: OFF
Case #2: ON
Case #3: OFF
Case #4: ON