問題一覧 > 通常問題

No.598 オーバーフローファンタジー

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 168
作問者 : koyumeishikoyumeishi / テスター : はむこはむこ
2 ProblemId : 1868 / 出題時の順位表
問題文最終更新日: 2017-11-24 02:10:15

問題文

コンピューターゲーム Toaru Fantasy では $N$ bit の符号付き整数 (2の補数) を用いて様々な数値を管理しています。

Toaru Fantasy には最近オーバーフローバグが見つかり、これを利用した攻略法が研究されています。
通常、敵を攻撃し、 敵の体力を 0 以下にするとその敵を撃破できます。
一方オーバーフローバグ攻略法では、 敵の体力をわざと回復し、 オーバーフローで体力が 0 以下になったときにも撃破判定されることを利用して敵を撃破します。

敵の初期体力を $X$ 、 1回の攻撃で減少させられる敵の体力を $A$ 、 1回の回復で増加させられる敵の体力を $B$ とします。
攻撃・回復ともに1回当たり1単位時間かかるとき、敵を撃破するのに必要な最短時間を求めてください。
敵が自らの体力を増減させることはありません。

2の補数知らない方向け情報

ある整数 $x (-2^{N-1} \leq x < 2^{N-1})$ は $N$ bit 符号付き整数で
$$ x = - 2^{n-1} * a_{n-1} + \sum_{k=0}^{k < n-1} 2^k * a_k $$
となるようなビット列 $a_{n-1}, a_{n-2}, \dots, a_{3}, a_{2}, a_{1}$ ($a_i$ = 0 または 1) を用いて表すことが出来ます (参考 : 二進法)

すなわち、各ビットが表す数は下の表のようになります。

 bit  |   N-1  |  N-2  | ... | 3 | 2 | 1 | 0 
------|--------|-------|-----|---|---|---|---
value |-2^(N-1)|2^(N-2)| ... | 8 | 4 | 2 | 1 

また、 二つの整数 $x,y (-2^{N-1} \leq x,y < 2^{N-1})$ の加算処理は通常の整数型と同様です。 最上位ビットより左に飛び出た分(carry flag)は無視されます。
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

入力

$N$
$X$
$A$
$B$

1行目にゲームで使われる整数型のビット長 $N$ が与えられます。
2行目に敵の最初の体力 $X$ が与えられます。
3行目に1回の攻撃で減少させられる敵の体力 $A$ が与えられます。
4行目に1回の回復で増加させられる敵の体力 $B$ が与えられます。

入力は全て整数で与えられます
$2\leq N \leq 32$
$1\leq X,A,B < 2^{N-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もしくは右上の雲マークをクリックしてアカウントを作成してください。