No.598 オーバーフローファンタジー
タグ : / 解いたユーザー数 201
作問者 :


問題文
コンピューターゲーム Toaru Fantasy では
Toaru Fantasy には最近オーバーフローバグが見つかり、これを利用した攻略法が研究されています。
通常、敵を攻撃し、 敵の体力を 0 以下にするとその敵を撃破できます。
一方オーバーフローバグ攻略法では、 敵の体力をわざと回復し、
オーバーフローで体力が 0 以下になったときにも撃破判定されることを利用して敵を撃破します。
敵の初期体力を
攻撃・回復ともに1回当たり1単位時間かかるとき、敵を撃破するのに必要な最短時間を求めてください。
敵が自らの体力を増減させることはありません。
2の補数知らない方向け情報
ある整数
となるようなビット列
すなわち、各ビットが表す数は下の表のようになります。
bit | N-1 | N-2 | ... | 3 | 2 | 1 | 0 ------|--------|-------|-----|---|---|---|--- value |-2^(N-1)|2^(N-2)| ... | 8 | 4 | 2 | 1
また、 二つの整数
https://en.wikipedia.org/wiki/Two%27s_complement#Addition
疑似コードで書くとこのような感じです。
// Bit Array A + B => C carry = 0 for i in [0, N) : C[i] = (A[i] + B[i] + carry) % 2 carry = floor( (A[i] + B[i] + carry) / 2 ) return C
入力
1行目にゲームで使われる整数型のビット長
2行目に敵の最初の体力
3行目に1回の攻撃で減少させられる敵の体力
4行目に1回の回復で増加させられる敵の体力
入力は全て整数で与えられます
出力
敵を撃破するのに必要な最短時間を出力してください。
サンプル
サンプル1
入力
4 4 3 1
出力
2
全ての数値は 4 bit 符号付整数型で管理されます。
攻撃2回行うと最短で撃破できます。
1回目の攻撃
0100 ( 敵の体力 4 ) +)1101 ( -A(=-3) を 2 の補数で表現 ) ------ 0001 ( 残り体力 1 )
2回目の攻撃
0001 ( 敵の体力 1 ) +)1101 ( -A(=-3) を 2 の補数で表現 ) ------ 1110 ( 残り体力 -2 )
サンプル2
入力
4 6 2 1
出力
2
2回敵の体力を回復をするとオーバーフローして撃破判定されます。
0110 ( 敵の体力 6 ) +)0001 ( B(=1) ) ------ 0111 ( 残り体力 7 ) 0111 ( 敵の体力 7 ) +)0001 ( B(=1) ) ------ 1000 ( 残り体力 -8 )
サンプル3
入力
26 16777221 20 20
出力
838861
攻撃のとき 838862 回、 回復のとき 838861 回 で撃破できます
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。