SamCoding Round 7 (Div. 2) D - Perfect Number
- サイト
- SamCoding
- コンテスト
- SamCoding Round 7 (Div. 2)
- 問題
- D - Perfect Number(常設版)
各桁の和が になる正の整数を「完全数」と呼びます()。小さい方から 番目の完全数を求める問題です()。
完全数を小さい順にすべて列挙し、 番目を出力します。
仕切りで桁を表す
Section titled “仕切りで桁を表す”桁の完全数は、 個の玉と 本の仕切りを一列に並べたものと対応させられます。仕切りで区切られた 個の区間に入っている玉の個数を、上の桁から順に並べたものが各桁の数字です。
たとえば で、 マスの列のうち位置 ( 始まり)に仕切りを置くと、各区間の玉の個数は なので を表します。
ただし、次の 2 つに注意します。
- 最上位の桁は 以上: 位置 に仕切りを置かなければよいので、仕切りの位置は から選びます。
- 各桁は 以下: 区間に玉が 個入る並べ方は数字として不正なので除きます。
小さい順に列挙する
Section titled “小さい順に列挙する”桁数が少ないほど小さいので、 の順に列挙します。桁数が同じなら、仕切りの位置を辞書順に並べたものが数の小さい順と一致します。仕切りの位置が前にあるほど、上の桁が小さくなるからです。
桁の完全数は 個あり、 桁()までで 個になります。 個を超えるので、 まで列挙すれば十分です。
Python
from itertools import combinations
ans = []for r in range(1, 11): for c in combinations(range(1, 10 + r), r=r): t = 0 l = [] for x in c: l.append(x - t) t = x + 1 l.append(10 + r - t) if 10 in l: continue ans.append(int("".join(map(str, l))))K = int(input())print(ans[K - 1])combinations で仕切りの位置 c を辞書順に列挙しています。t は直前の仕切りの次の位置で、x - t が仕切りの間にある玉の個数、つまりその桁の数字です。最後の区間は列の長さ 10 + r までの玉の個数です。
桁に 10 があるものを除き、残りを数にして ans に入れていきます。