裏 RjpWiki

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

同じ数字でサンドイッチ

2017年08月22日 | ブログラミング

同じ数字でサンドイッチ

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

1〜Nまでの数字が書かれたカードがそれぞれ2枚ずつと、ジョーカー1枚があります。
このカードを一列に並べるとき、書かれている数字の数だけ他のカードを挟んで並べることにします。
(ジョーカーは挟まれるだけで、挟む必要はありません。)

例えば、1, 2, 3のカードがそれぞれ2枚あるとき、 ジョーカーを「0」で表すと
2, 3, 1, 2, 1, 3, 0
2, 3, 0, 2, 1, 3, 1

などのように並べられます。
※いずれも1で挟まれたカードは1枚、2で挟まれたカードは2枚、3で挟まれたカードは3枚です。

N=5のときは、以下のような例で挟めます。
1, 5, 1, 2, 3, 4, 2, 5, 3, 0, 4
1, 4, 1, 5, 3, 0, 4, 2, 3, 5, 2


標準入力から N が与えられるとき、上記のように挟んだ並べ方の中から、ジョーカーが最も右側に来る並べ方を求め、その位置を標準出力に出力してください。
例えば、N=3, N=5 のときは上図のそれぞれ一行目が該当しますので、以下のように出力します。

Nは9以下の正の整数とし、上記のような挟み方が存在しない場合は0を出力してください。

【入出力サンプル1】
標準入力
3

標準出力
7

【入出力サンプル2】
標準入力
5

標準出力
10

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

オンライン整数列大辞典の A279934
https://oeis.org/A279934

f = function(n) {
    m = 1:19
    a = (m-1)*((1+sqrt(5))/2)
    cat(m[a-floor(a) > 0.5][n])
}

#f(scan(file("stdin", "r"), quiet=TRUE))

f(3) # 7
f(4) # 9
f(5) # 10
f(8) # 17
f(9) # 18

以下の単純なプログラムで n の小さい方の解を求めてから

f = function(n) {
    library(e1071)
    a = c(0, rep(1:n, 2))
    p = permutations(length(a))
    maxPos = apply(p, 1, function(x) {
        b = a[x]
        ok = 1
        for (i in 1:n) {
            if (diff(grep(i, b))-1 != i) {
                ok = 0
                break
            }
        }
        if (ok == 1) {
            grep(0, b)
        } else {
            0
        }
    })
    cat(max(maxPos))
}



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

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

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