締め切りが 2016/12/15 10:00 AM なので,その 1 分後に投稿されるように予約
【概要】
有理数を、図のようにならべます。
図では、紙面の都合で7段目までしか書かれていませんが、下に無限に広がっています。
与えられた有理数の、図上での左隣と右隣(図にある x は無視して)の有理数を求めてください。
【詳細】
有理数を並べるツリーは以下のルールに従っています:
自分が p/q の場合、左の子は p/(p+q)
自分が p/q の場合、右の子は (1-p/q)。ただし、自分が 1/2 以上の場合には右の子はいない。
入力は
3/7
という具合に標準入力から来ます。
出力は、左隣と右隣の有理数を、コンマ区切りで出力してください。
こんな
4/5,2/7
具合です。
ただし、左隣や右隣に有理数がない場合には、そこには有理数の代わりにハイフンをおいてください。
例えばこんな
-,4/5
3/4,-
具合です。
【例】
入力 出力
3/7 4/5,2/7
1/6 -,4/5
2/5 3/4,-
【補足】
不正な入力に対処する必要はありません。
入力の分母・分子 はいずれも正の整数で、分子<分母<二百五十 です。
=====
g = function(p, q) { # 親のノードを得る
if (2 * p == q) {
p = q = 0
} else if (2 * p > q) {
p = q - p
} else {
q = q - p
}
list(p = p, q = q)
}
h.l = function(p, q) { # 左側の子供のノードを得る
list(p = p, q = p + q)
}
h.r = function(p, q) {# 右側の子供のノードを得る
if (2 * p >= q) {
p = q = 0
} else {
p = q - p
}
list(p = p, q = q)
}
case.r = function(p, q) { # 発端が右の子供の場合
level = 0
parent = g(p, q)
l = h.l(parent$p, parent$q) # 発端者の左隣は親の左側の子供
repeat { # 右隣の探索は,まず左側の子供を持つ親までさか上る
parent = g(parent$p, parent$q)
if (parent$p == 0) {
return(list(l = l, r = parent))
}
level = level - 1
r = h.r(parent$p, parent$q)
if (r$p != p && r$q != q && r$p != 0 && r$q != 0) {
break
}
p = parent$p
q = parent$q
}
repeat { # しかる後に,左の子供をたどって下る
if (level == 0) {
break
}
level = level + 1
r = h.l(r$p, r$q)
}
list(l = l, r = r)
}
case.ll = function(p, q) {
level = -1
parent = g(p, q)
if (parent$p == 0 || parent$p == 1) {
return(list(p = 0, q = 0))
} else if (parent$p == 1) {
return(h.l(parent$p, parent$q))
}
repeat { # 左隣の探索は,まず左側の子供を持つ親までさかのぼる
parent = g(parent$p, parent$q)
if (parent$p == 0) {
return(list(p = 0, q = 0))
}
level = level - 1
l = h.l(parent$p, parent$q)
if (l$p != p && l$q != q && l$p != 0 && l$q != 0) {
break
}
p = parent$p
q = parent$q
}
level = level + 1
l = h.l(parent$p, parent$q)
if (level == 0) {
return(l)
}
repeat {
level = level + 1
l = h.r(l$p, l$q)
if (level == 0) {
break
}
if (2 * l$p > l$q) {
level = level + 1
l = h.l(l$p, l$q)
if (level == 0) {
break
}
}
}
l
}
case.lr = function(p, q) {
level = 0
repeat {
parent = g(p, q)
r = h.r(parent$p, parent$q)
if (0 > level && r$p == 0) {
return(r)
}
if (r$p != parent$p && parent$q != q && r$p != 0) {
break
}
level = level - 1
p = parent$p
q = parent$q
}
repeat {
if (level == 0) {
break
}
level = level + 1
r = h.l(r$p, r$q)
}
r
}
f = function(p, q) {
options(scipen = 100)
l = r = list(p = 0, q = 0)
if (2 * p > q) { # 右の子供が発端
ans = case.r(p, q)
l = ans$l
r = ans$r
} else { # 左の子供が発端
l = case.ll(p, q) # 左隣
r = case.lr(p, q) # 右隣
}
l = ifelse(l$p == 0, "-", sprintf("%s/%s", l$p, l$q))
r = ifelse(r$p == 0, "-", sprintf("%s/%s", r$p, r$q))
cat(sprintf("%s,%s", l, r))
}
f(3, 7) # 4/5,2/7
f(5, 37) # 16/41,27/32
f(1, 2) # -,-
f(1, 3) # -,-
f(248, 248) # -,-
f(1, 249) # -,247/248
f(2, 249) # 14662949395604/23725150497407,245/247
f(3, 248) # 1032569015/1670731762,242/245
f(144, 233) # 89/322,-
f(247, 248) # 1/249,246/493
f(65, 81) # 16/97,49/114
f(65, 73) # 8/81,57/122
f(134, 205) # 71/276,55/338