裏 RjpWiki

Julia ときどき R, Python によるコンピュータプログラム,コンピュータ・サイエンス,統計学

回文数の中央値

2017年12月21日 | ブログラミング

回文数の中央値

締め切りが 2017/12/21 10:00 AM なので,その 1 分後に投稿されるように予約

【概要】
数の範囲を指定します。
その範囲内にある回文数( seeWikipedia - 回文数) の、真ん中の値を計算してください。

例えば下表の通りです:
値の範囲     回文数                真ん中の値
99〜120     99,101,111          101
200〜232     202,212,222,232    212,222
【入出力】
入力は
99,120
のように下限と上限がコンマ区切りで並んでいます。
下限以上で、上限以下の回文数の真ん中の値を求めてください。

出力も普通に10進数です。
範囲内にある回文数が奇数個の場合には、中央の値はひとつに決まるのでそれを。
偶数個の場合にはぴったり中央の値はありませんので、中央付近の2つの値をコンマ区切りで昇順に出力してください。
ただし、範囲内に回文数がひとつもない場合は"-"を出力してください。

【例】
入力            範囲内の回文数                    出力
99,120         99, 101, 111                    101
200,232        202,101,111,202,212,222,232     212,222
123,124                                        -
1234,1400      1331                            1331

【補足】
・ 不正な入力に対処する必要はありません。
・ 0 < 下限 < 上限 ≦ 一千兆 です。

==============================================================================================================

g = function(n, odd) {
    a = unlist(strsplit(as.character(n), ""))
    b = rev(a)
    if (odd)
        b = b[-1]
    as.numeric(sprintf("%s%s", paste(a, collapse = ""), paste(b, collapse = "")))
}

h = function(begin, end) {
    options(scipen=100)
    ans = NULL
    for (i in begin:end) {
        a = unlist(strsplit(as.character(i), ""))
        if (all(a == rev(a))) {
            ans = c(ans, i)
        }
    }
    n = length(ans)
    if (n == 0) {
        cat("-")
    } else if (n %% 2 == 1) {
        cat(ans[n%/%2+1])
    } else {
        cat(sprintf("%i,%i", ans[n/2], ans[n/2+1]))
    }
}

concatenate = function(...) {
    paste(c(...), sep = "", collapse = "")
}

Begin = function(d) {
    if (9 >= d) {
        return(d)
    }
    s = d
    repeat {
        s = unlist(strsplit(as.character(s), ""))
        n = length(s)
        half = n%/%2
        odd = n%%2
        left = concatenate(s[1:half])
        middle = ifelse(odd, s[half + 1], "")
        right = concatenate(s[half:1])
        x = as.numeric(concatenate(left, middle, right))
        if (x >= d) {
            break
        }
        t = unlist(strsplit(as.character(as.numeric(concatenate(left, middle)) + 1), ""))
        if (odd == 0) {
            s = concatenate(t, rev(t))
        } else {
            s = concatenate(t, rev(t)[-1])
        }
    }
    x
}

End = function(d) {
    options(scipen=100)
    if (log10(d) == floor(log10(d))) {
        d = d-1
    }
    s = d
    repeat {
        s = unlist(strsplit(as.character(s), ""))
        n = length(s)
        half = n%/%2
        odd = n%%2
        left = concatenate(s[1:half])
        middle = ifelse(odd, s[half + 1], "")
        right = concatenate(s[half:1])
        x = as.numeric(sprintf("%s%s%s", left, middle, right))
        if (d >= x) {
            break
        }
        t = unlist(strsplit(as.character(as.numeric(concatenate(left, middle)) - 1), ""))
        if (odd == 0) {
            s = concatenate(t, rev(t))
        } else {
            s = concatenate(t, rev(t)[-1])
        }
    }
    x
}

f = function(begin, end) {
    order = log10(end)
    if (100 >= end-begin) {
        h(begin, end)
    } else if (begin == 1 && order == floor(order) && order < 4) {
        cat( c("5", "9,11", "454,464")[order])
    } else if (begin == 1 && order == floor(order)) {
        if (order %% 2 == 1 && order >= 5) {
            ans1 = ans2 = concatenate("45", rep(0, order-4), "54")
        } else if (order %%2 == 0 && order >= 4) {
            ans1 = ans2 = concatenate("9", rep(0, order-3), "9")
        }
        half = nchar(ans2)%/%2+1
        substr(ans2, half, half+1) = "1"
        cat(ans1, ans2, sep=",")
    } else {
        b = Begin(begin)
        bs = as.character(b)
        bs.nchar = nchar(bs)
        bs.odd = bs.nchar %% 2
        bs.half = bs.nchar %/% 2
        if (bs.odd == 0) {
            b2 = as.numeric(substr(bs, 1, bs.half))
        } else {
            b2 = as.numeric(substr(bs, 1, bs.half+1))
        }
        e = End(end)
        es = as.character(e)
        es.nchar = nchar(es)
        es.odd = es.nchar %% 2
        es.half = es.nchar %/% 2
        if (es.odd == 0) {
            e2 = as.numeric(substr(es, 1, es.half))
        } else {
            e2 = as.numeric(substr(es, 1, es.half+1))
        }
        if ((e2 - b2 + 1) %% 2 == 1) {
            ans1 = g((b2+e2) %/% 2, es.nchar %% 2)
            cat(ans1)
        } else {        
            ans1 = g((b2+e2) %/% 2, es.nchar %% 2)
            ans2 = g((b2+e2) %/% 2+1, es.nchar %% 2)
            if (ans2 > end) {
                cat("-")
            } else {
                cat(sprintf("%s,%s", ans1, ans2))
            }
        }
    }
}

# arg = scan(file("stdin", "r"), sep = ",")
# f(arg[1], arg[2])

f(1, 2) #  1,2
f(9, 10) #  9
f(10, 11) #  11
f(10, 12) #  11
f(123456, 124000) #  -
f(28228056190, 77331569708) #  52779797725,52779897725
f(174517247652, 237309752247) #  205912219502,205913319502
f(468178194014, 4647762198268) #  2557969697552,  2557970797552
f(29904128799113, 50953812820424) #  40428977982404
f(495630518704001, 919719574970542) #  707675040576707
f(1, 1e+15) # 450000000000054,450000010000054
f(999999999999999, 1e+15) # 999999999999999

コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

PVアクセスランキング にほんブログ村

PVアクセスランキング にほんブログ村