裏 RjpWiki

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

限られた数字で作れる数の、まんなかの値

2016年10月21日 | ブログラミング

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

限られた数字で作れる数の、まんなかの値」を求める

【概要】
たとえば。
0, 4, 5以外の数を使わずに作ることができる3桁以下の非負の整数は、

    0, 4, 5, 40, 44, 45, 50, 54, 55, 400, 404, 405, 440, 444, 445, 450, 454, 455, 500, 504, 505, 540, 544, 545, 550, 554, 555

の27個です。中央は14番目の数なので、求める値は444になります。
このような感じで、桁数の最大値と使える数字を与えますので、作ることができる数の中央の値を求めてください。

【入出力】
入力は
3 045
こんな感じです。
空白の前が桁数の上限。空白の後が使える数字です。使える数字は重複なく昇順に並んでいます。

出力は、
444
のように、中央の値を出力してください。
作れる数が偶数個の場合には、中央に近い数を2つ、小さい順にコンマ区切りで並べてください。

【例】
入力     出力
3 045     444
1 012789     2,7
10 059     5555555555

【補足】
桁数の上限の最小値は 1 。最大値は 15 です
不正な入力に対処する必要はありません

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

f = function(s) {
    g = function(m) {
        d = 0
        if (m > 0) {
            m = m-1 # 与えられる中央値は 1 から始まるので,j 進数で 0 から始めるために 1 を引く
            for (i in 1:99) {
                if (m == 0) break
                d[i] = x[m %% j + 1] # j 進数で各桁を決める。ただし,表記に使うのは x にある,実際に使える数字
                m = m %/% j
            }
        }
        paste(rev(d), collapse="")
    }
    options(scipen=100)
    s = unlist(strsplit(s, " "))
    k = as.numeric(s[1])
    x = as.numeric(unlist(strsplit(s[2], "")))
    if (length(x) == 1) { # 1 桁の場合は特別に扱う(簡単なのだけど)
        f = unique(as.numeric(sapply(1:k, function(y) paste(rep(x, y), collapse=""))))
        n = length(f)
        m = n %/% 2
        if (n %% 2 == 1) {
            cat(f[m+1])
        } else {
            cat(f[m+0:1], sep=",")
        }
    } else {
        j = length(x) # 使える数字の個数を j
        n = j^k # 作られる数の個数は 0 〜 (j^k)-1 の n 個。それぞれに 1 を足して 1 〜 n=j^k とする
        if (n %% 2 == 0) { # 真ん中の数は,要するに中央値。求め方は初歩の統計学の教科書に書いてある
            m = n/2
            cat(g(m), ",", g(m+1), sep="") # g() は十進数表記の中央値を j 進数で表記し直すだけ
        } else {
            m = (n+1) / 2
            cat(g(m))
        }
    }
}

> f("1 2") # 2
2
> f("2 2") # 2,22
2,22
> f("15 3") # 33333333
33333333
> f("1 0") # 0
0
> f("2 0") # 0
0
> f("15 04") # 44444444444444,400000000000000
44444444444444,400000000000000
> f("1 0246") # 2,4
2,4
> f("2 0246") # 26, 40
26,40
> f("15 0246") # 266666666666666,400000000000000
266666666666666,400000000000000
> f("15 12345789")
499999999999999,511111111111111
> f("15 123456789")
555555555555555
> f("15 0123456789") # 499999999999999,500000000000000
499999999999999,500000000000000

以下の 2 ケースの解が異なるのだが
■テストケース10 ・・・ 【入力値:15 12345789】【期待値:444444444444444,444444444444445】
■テストケース11 ・・・ 【入力値:15 123456789】【期待値:494949494949495】

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

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

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