解説

2000年1月1日～3399年9月29日（理由は後述）までの範囲を全探索する事でこの問題を解くことが出来ます。うるう年を考慮しないので1年は365日です。これを1400年分探索したとしても計算量は$5×10^5$回程度となり十分高速です。

実装上は年月日をそれぞれ3重ループで探索すれば良いです。各月によって日数が変わる点には注意が必要です。また、実装時に探索範囲の上限を意識する必要はなく、条件を満たす年月日を発見した時点で処理を終了すれば問題はありません。

解答例(Python)

xxxxxxxxxx

n = int(input())

s = input()

​

# 各月の日数を表すリスト

days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

​

def destiny_number(u: str) -> int:

  """数字のみの文字列から運命数を計算する"""

  while 1:

    sum = 0

    for c in u:

      sum += (ord(c) - 48)

​

    if sum <= 9 or sum in {11, 22, 33, 44}:

      return sum

​

    u = str(sum)

​

for y in range(2000, 3400):

  for m in range(1, 13):

    for d in range(1, days[m - 1] + 1):

      # y, m, dをゼロ埋めした8桁の文字列に変換

      t = str(y) + f'{m:02}' + f'{d:02}'

​

      # 条件を満たす年月日が見つかれば終了する

      if s <= t and destiny_number(t) == n:

        print(t)

        exit()

探索範囲の上限が3399年9月29日となる理由

探索範囲の上限は$N$の上限である2999年12月31日以降に最も遅く現れる運命数の年月日に等しいです。

運命数が$x$となる年月日において、年月日の各桁を一度だけ全て足し合わせた数(運命数になるとは限らない)の順序付き集合を$D(x)$とします。

問題で使われている13パターンの運命数についての集合を考えると以下のようになります。なお、1と2は2999年12月31日以降に一度も出現しないため、取り消し線を付けています。

• $D(1) = \{\sout1,10,19,...\}$
• $D(2) = \{\sout2,20,101,...\}$
• $D(3) = \{3,12,21,...\}$
• $D(4) = \{4,13,31,...\}$
• $D(5) = \{5,14,23,...\}$
• $D(6) = \{9,15,24,...\}$
• $D(7) = \{7,16,25,...\}$
• $D(8) = \{8,17,26,...\}$
• $D(9) = \{9,18,27,...\}$
• $D(11) = \{11,29,38,...\}$
• $D(22) = \{22,499,589,...\}$
• $D(33) = \{33,6999,7899,...\}$
• $D(44) = \{44,89999,98999,...\}$

1年間に現れる日付で作れる、各桁を一度だけ全て足し合わせた数のうち、最も小さい値は1月1日の2、最も大きい値は9月29日の20です。また、1月1日から1月9日で2～10、9月20日～9月29日で11～20を作れるので取り得る値の範囲は2～20です。実際は年の各桁を全て足した値の分だけ範囲がずれていきます。例えば、3000年の取り得る値の範囲は5～23です。

$D(x)$の要素が一つでも範囲に含まれているならその年に運命数$x$となる日付が存在するので、3000年に22までの運命数が全て現れます。運命数33は13だけ範囲をずらせば良いので、3019年9月29日に初めて現れます。

年月日の各桁を一度だけ足した和は日付が進むにつれて単調増加になるとは限らない事に注意してください。例えば、3000年1月9日は13ですが、3000年1月10日は5です。この事から、範囲をずらす際には下から桁を埋めていく必要があります。同様に、運命数44は24だけ範囲をずらす必要があるので、下から桁を埋めていくと3399年9月29日に初めて現れる事になります。結局、これが探索範囲の上限になります。