ファレイ数列
(paizaランク D 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
有理数を二分探索したい場合には、2 つの分数 a / b と c / d の間に存在する分数を求めることで実現できます。
a / b < c / d であるとき、a / b < (a + c) / (b + d) < c / d であることは簡単に示せます。
よって、2 つの分数の間にある値 (a + c) / (b + d) を使うと、この値は必ず区間 [a / b, c / d] の範囲に収まります。
整数 a, b, c, d が与えられるので、(a + c) / (b + d) の形で出力してください。
- 入力される値
-
a b c d
・ 1 行目に、分数 a / b の分子を表す整数 a と分母を表す整数 b, 分数 c / d の分子を表す整数 c と分母を表す整数 d がこの順に半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
p/q
答えの分数を 1 行で出力してください。
約分はおこなわず、p = a + c, q = b + d として分数の形で出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ a, b, c, d ≦ 10^5
・ a / b < c / d
- 入力例1
-
1 2 3 4
- 出力例1
-
4/6
