問題
回文とは、前から読んでも後ろから読んでも同じになるもののことです。33 は10進数で回文であり、2進数では 100001 となって、これも回文です。1 から limit までの数のうち、10進数でも base 進数でも回文になるものをすべて足し合わせてください。数は先頭に余分な 0 を付けずに書きます。
double_base_palindromes(limit, base) を実装してください。
入力
limit:調べる最大の数。
base:2つ目の基数。
出力
条件を満たす数の和を返してください。
制約
1 ≤ limit ≤ 100,000; 2 ≤ base ≤ 16
例
入力:
limit = 10
base = 2
期待される出力:
expected = 25
入力:
long long limit = 10;
long long base = 2;
期待される出力:
long long expected = 25;
入力:
long limit = 10;
long base = 2;
期待される出力:
long expected = 25;
解説
1, 3, 5, 7, 9 は2進数で 1, 11, 101, 111, 1001 となり、すべて回文です。2, 4, 6, 8 は回文になりません。和は 25 です。
入力:
limit = 50
base = 3
期待される出力:
expected = 15
入力:
long long limit = 50;
long long base = 3;
期待される出力:
long long expected = 15;
入力:
long limit = 50;
long base = 3;
期待される出力:
long expected = 15;
解説
3進数では 1, 2, 4 (11), 8 (22) が当てはまり、33 は 1020、44 は 1122 なので当てはまりません。和は 15 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
基数で割り算を繰り返すと、最後の桁から順に各桁が得られます。
ヒント 2
回文かどうかは、桁のリストとそれを逆にしたものを比べれば判定できます。
ヒント 3
まず10進数で判定しましょう。通過する数は少ないので、2つ目の変換はめったに必要になりません。
目安の計算量
時間 O(limit × log limit)、追加メモリ O(log limit)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。