三角形は何通り？

いつもの通り，締め切りが 2016/12/31 10:00 AM なので，その 1 分後に投稿するように予約

【問題】
入力nに対して
1≦a≦b≦c≦n（a, b, c, nはすべて整数）を満たすa, b, cの中で、これらを3辺とする三角形が成り立つ場合の組み合わせを求めるプログラムを書いてください。

【入力】
標準入力から、整数n（1≦n≦1000000）が与えられます。

【出力】
標準出力に、条件を満たす組み合わせの総数のみを出力してください。

たとえばn = 3とすると、(a, b, c)のすべての組み合わせは、

    (1, 1, 1)
    (1, 2, 2)
    (1, 3, 3)
    (2, 2, 2)
    (2, 2, 3)
    (2, 3, 3)
    (3, 3, 3)

の7通りになりますので、7と出力します。

==========

 

いつもの定石。簡単なプログラムを書いて，n=1,2,3,... の場合の答えを求め，「オンライン整数列大辞典」を参照する。

f = function(n) {
    options(scipen=100)
    cat(floor((n+1)*(n+3)*(2*n+1)/24))
}

> f(3)
[1] 7
> f(1000)
[1] 83708750
> f(10000)
[1] 83370837500
> f(1000000)
[1] 83333708333750000

html タグの入れ子の間違い探し

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

 【問題】
htmlが標準入力から与えられるので、htmlタグの入れ子が間違っている、閉じタグが現れる最初の行番号を、標準出力に出力するプログラムを作ってください。
htmlは最大20行、1行あたり最大100文字です。
ただし、liタグに関しては、タグが閉じていても閉じてなくてもよいものとします。
間違いがない場合には0を出力してください。

=====

テストデータが 3 個しかなく，しかも簡便化されているので，一般的な html ファイルを扱うプログラムを書くなどとは馬鹿馬鹿しくまともに取り合う気になれず，テストに合格するプログラムを書いただけ...

f = function(s) {
    stack = NULL
    s = sub(" .+>", ">", s)
    error.lno = 0
    for (i in seq_along(s)) {
        t = s[i]
        if (substr(t, 2, 2) == "/") {
            t = sub("/", "", t)
            if (length(stack) == 0) {
                error.lno = i
                break
            } else if (stack[1] == t) {
                stack = stack[-1]
            } else {
                error.lno = i
                break
        } else if (substr(t, 1, 4) != "＜li＞") {
            stack = c(t, stack)
        }
    }
    cat(error.lno)
}

 

硬貨の組み合わせの数

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

【問題】

小銭をたくさん持っている小銭王子は、小銭を使った支払いに興味を持ちました。
指定された金額になる小銭の出し方のすべてのパターンを調べ、王子に教えてあげてください。
例えば、10 円を支払うとき、「10 円玉 1 枚」「5 円玉 2 枚」「5 円玉 1 枚と 1 円玉 5 枚」「1 円玉 10 枚」の 4 通りあります。
※小銭は 500 円・100 円・50 円・10 円・5 円・1 円硬貨です。また、小銭王子はそれぞれの硬貨を 1000 枚ずつ持っています。

【入力】

標準入力から、整数値 N（1 ≦ N ≦ 1000）が与えられます。

【出力】

合計金額が N 円になる硬貨の出し方のすべての組み合わせを求め、そのパターン数を、標準出力に出力してください。

【入出力サンプル】

Input
10

Output
4

＝＝＝＝＝

規則性に基づき，テーブルを作成する。

f = function(n) {
    x = 1:5
    x = c(x, x*2+5, 18)
    x = cumsum(rep(x, each=2))
    x = cumsum(rep(x, each=5))
    x = cumsum(rep(x, each=2))
    x = rep(x, each=5)
    cat(x[n+1])
}

2 進表記の 1 の個数

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

【問題】

2 つの整数値 N, M が与えられます。
0 から  N ま での各整数（10 進数）について、2 進表記したときに 1 の数がM個になるものを数えてください。
たとえば、9 を 2 進表記すると 1001 ですので、1 の数は 2 ということになります。

【入力】

標準入力から、半角スペースで区切られた 2 つの整数値N（0 ≦ N ≦ 100000）、M（0 ≦ M ≦ 17）が与えられます。
 
【出力】

0 から N までの整数の中で、2 進表記したときに 1 の数が M 個あるものの個数を出力してください。

【入出力サンプル】
Input
10 2

Output
5

※11, 101, 110, 1001, 1010 の 5 つ

＝＝＝＝＝

intToBits という関数を使えば，超超簡単

f = function(s) {
    s = as.integer(unlist(strsplit(s, " ")))
    cat(sum(sapply(0:s[1], function(x) sum(as.integer(intToBits(x))) == s[2])))
}

整数値の集合に条件を満たす 2 数があるか？

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

【問題】

いくつかの整数値が与えられます。
それらの中で、和がちょうど 256 になるような 2 数が存在するかどうかを調べてください。
 
【入力】

標準入力から、整数値が与えられます。

 1 行目は整数値N（2 ≦ N ≦ 100）、2 行目はN個の整数値Ak（ 0 ≦ Ak ≦ 256）が半角スペースで区切られています。
 
【出力】

和が 256 になる 2 数が存在する場合は "yes"、存在しない場合は "no" と、標準出力に出力してください。
 
【入出力サンプル】
Input
4
32 64 128 192

Output
yes

＝＝＝＝＝

f = function(s) {
    x = as.integer(unlist(strsplit(s, " ")))
    y = outer(x, x, "+")
    diag(y) = 0
    cat(c("no", "yes")[(256 %in% y)+1])
}

取り違えは何通り？

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

この問題，2 年前にも同じようなのが出題されたんだよね。（ 完全順列 http://blog.goo.ne.jp/r-de-r/s/完全順列 ）

 一人一台のパソコンを支給されている、社員N人の会社があります。
このパソコンは見た目がすべて同じため、他の人のパソコンを間違って持ち帰ってしまう場合がありました。

N人全員が他人のパソコンを持って帰ってしまうような組み合わせが何通りあるかを求めてください。
使用するプログラミング言語は問いません。

なお、出力は64bit整数に収まります。

【入出力サンプル】

Input
5

Output
44

==========

前は再帰で書いたので，別の書き方で 2 通りのプログラム

f = function(n) {
    options(scipen=100)
    a = 0
    b = 1
    for (i in 3:n) {
        x = (i - 1) * (a + b)
        a = b
        b = x
    }
    cat(x)
}

f = function(n) {
    options(scipen=100)
    k = 2:n
    cat(sum( (-1)^k * factorial(n) / factorial(k) ))
}

f(5) # 44
f(12) # 176214841
f(17) # 130850092279664