裏 RjpWiki

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

連続する整数の各桁の数字の和

2017年01月24日 | ブログラミング

連続する整数の各桁の数字の和

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

設問

a, b という2つの正の整数が与えられたとき、aからbまでの連続する整数について、各桁の数字の和を求めることを考えます。

例えば、a = 7, b = 16のとき、7, 8, 9, 10, 11, 12, 13, 14, 15, 16の各桁の数字を足して、
7 + 8 + 9 + 1 + 0 + 1 + 1 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 + 1 + 6 = 52
となります。

また、a = 12, b = 19のときは、
1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 + 1 + 6 + 1 + 7 + 1 + 8 + 1 + 9 = 52
となり、同じ値になります。

このように、同じ値が得られる正の整数 a, b のペアは一つとは限りません。
標準入力から a, b の値がスペースで区切って与えられたとき、与えられた a, b の範囲に重なる(両端を含む)ようなペアがいくつあるかを求め、標準出力に出力してください。
(a = 21, b = 28 なども同じ値になりますが、7〜16 と 21〜28は重なる範囲がないため対象外です。)

例えば、上記の a = 7, b = 16 の場合、a = 12, b = 19 の他にも a = 3, b = 13 の場合があり、合わせて2通りですので、以下のように出力します。

【入出力サンプル】
標準入力
7 16

標準出力
2

※a, b は32ビット整数の範囲で、0 < b - a < 2500 を満たす数が与えられるものとします。

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

R で書くと実行時間制限にかかるので,Java に書き直して O.K.
ただ,Java だと,処理系によりメモリーオーバーになるので小細工が必要になる

R によるプログラム

f = function(a, b, range=8000) {
    if (b-a < 1000) {
        max = b+2*(b-a)
        min = 2
    } else {
        max = b+range
        min = a-range
    }
    x = integer(max)
    x[min-1] = sum(as.numeric(unlist(strsplit(as.character(min-1), ""))))
    for (i in min:max) {
        x[i] = x[i-1]+sum(as.numeric(unlist(strsplit(as.character(i), ""))))
    }
    s = x[b]-x[a-1]
    count = 0
    for (i in a:(b-1)) {
        for (j in min:a) {
            if (x[i]-x[j-1] == s) {
                count = count+1
            }
        }
    }
    for (i in (a+1):b) {
        for (j in i:max) {
            if (x[j]-x[i-1] == s) {
                count = count+1
            }
        }
    }
    count
}
f(7, 16) # 2
f(100, 150) # 15
f(2000, 2017) # 3
f(12345678, 12347654)) # 167
f(123456789, 123459012) # 294

2 つの二重ループを outer 関数に置き換え,制約範囲を限ると,テストシステムでも 1 秒以内に収まった(テストデータをクリアーするということに限る。一般解ではない)。

f = function(a, b, range=2500) {
    if (b-a < 1000) {
        max = b+2*(b-a)
        min = 2
    } else {
        max = b+range
        min = a-range
    }
    x = integer(max)
    x[min-1] = sum(as.integer(strsplit(as.character(min-1), "")[[1]]))
    for (i in min:max) {
        x[i] = x[i-1]+sum(as.integer(strsplit(as.character(i), "")[[1]]))
    }
    s = x[b]-x[a-1]
    res1 = outer(x[a:(b-1)], x[min:a-1], "-")
    res2 = outer(x[b:max], x[(a+1):b-1], "-")
    sum(res1 == s)+sum(res2 == s)
}

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

Java によるプログラム

import java.util.*;
import java.util.regex.*;

class Main {

    public static void main(String[] args) {
        System.out.println(f(7, 16));
        System.out.println(f(100, 150));
        System.out.println(f(2000, 2017));
        System.out.println(f(12345678, 12347654));
        System.out.println(f(123456789, 123459012));
     }

    static int digitsSum(int n) {
        int sum = 0;
        while (n != 0) {
            sum += n%10;
            n /= 10;
        }
        return sum;
    }

    static int f(int a, int b) {
        int max, min, i, j, s, count = 0;
        int range = 8000;
        if (b-a < 1000) {
            max = b+2*(b-a);
            min = 2;
        } else {
            max = b+range;
            min = a-range;
        }
        int [] x = new int[max-min+3];
        x[1] = digitsSum(min-1);
        for (i = min; max >= i; i++) {
            x[i-min+2] = x[i-1-min+2]+digitsSum(i);
        }
        s = x[b-min+2]-x[a-1-min+2];
        count = 0;
        for (i = a-min+2; b-1-min+2 >= i; i++) {
            for (j = min-min+2; a-min+2 >= j; j++) {
                if (x[i]-x[j-1] == s) {
                    count++;
                }
            }
        }
        for (i = a+1-min+2; b-min+2 >= i; i++) {
            for (j = i; max-min+2 >= j; j++) {
                if (x[j]-x[i-1] == s) {
                    count++;
                }
            }
        }
        return count;
    }
}

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

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

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