問題一覧 > 通常問題

No.1446 ハンバーグと納豆ごはん

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 103
作問者 : LithopsLithops / テスター : shiomusubi496shiomusubi496
2 ProblemId : 6078 / 出題時の順位表
問題文最終更新日: 2021-04-03 09:31:23

問題文

Lithops 君はある三ツ星レストランのシェフを務めています。彼の料理はとてもおいしいことで評判です。

さて、今日のランチはハンバーグと納豆ごはんのセットです。ランチはハンバーグと納豆ごはんをちょうど $1$ 品ずつ使って作ります。同じハンバーグや納豆ごはんを複数のセットで使うことはできません。 Lithops 君は予めハンバーグを $A$ 品、納豆ごはんを $B$ 品作ってあります。

Lithops 君はこれらの料理を使って、なるべく多くのランチを作りたいです。

そこで、 Lithops 君が作ったのが「ハンバーグと納豆ごはん相互変換マシーン」です。

「ハンバーグと納豆ごはん相互変換マシーン」にハンバーグを $N$ 品入れると、それらのハンバーグがなくなる代わりに、 $1$ 品の納豆ごはんが出てきます。同様に、納豆ごはんを $M$ 品入れると、それらの納豆ごはんがなくなる代わりに、 $1$ 品のハンバーグが出てきます。

この「ハンバーグと納豆ごはん相互変換マシーン」を $0$ 回以上任意の回数使うことで、最大で何食のランチを作れるか求めてください。

入力

$A\ B\ N\ M$
  • $1\leq A, B, N, M\leq 10^{18}$
  • 入力は全て整数

出力

最大で何食のランチが作れるか出力してください。

最後に改行してください。

サンプル

サンプル1
入力
1 10 2 3
出力
3

納豆ごはん $3$ 品を「ハンバーグと納豆ごはん相互変換マシーン」に入れることを $2$ 回繰り返します。するとハンバーグが $3$ 品、納豆ごはんが $4$ 品となるので、ランチを $3$ 食作ることができます。

ランチを $4$ 食以上作ることはできないので、 $3$ と出力します。

サンプル2
入力
60 10 21 121
出力
12

サンプル3
入力
137734418266269227 770038739817504238 253812456928708090 155625970401908842
出力
137734418266269231

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。