与えられる2つのバイナリ文字列のうち、少なくとも片方の最高位が1であることは保証されますか？

保証されません．

全域木のURLが間違ってます

修正しました．

使える数字の数に制限がありますか

ありません。

Python2.7.3で解いたら全てTLEになってしまいました。
割り切れるか問う時は、
print "? 10"
とかで、その答えを入力するときは
raw_input()
で入力すればいいんですよね？

出力をflushしてください．

問題文で"i<j"と表記すべきところの表示が崩れて"i"になっています

修正しました．

順位表のペナルティタイムの付きかたが http://www.kupc.jp/rule.html に書かれているのと異なっているように見えます

申し訳ありません．http://www.kupc.jp/rule.htmlの記述が間違っていました．正しくは，ペナルティタイムは「最後に提出した時間 + 誤答の数×4分」です．

TLEについて

TLEが6秒に変更されました。
また、それにともない問題文も修正されています。

強さの上昇は離散的ですか？すなわち，cost 0.5c を払って強さ 0.5 上げることは不可能ですか？

不可能です．