結果

問題 No.3277 Forever Monotonic Number
コンテスト
ユーザー ゼット
提出日時 2025-09-19 22:05:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,014 ms / 4,000 ms
コード長 1,272 bytes
コンパイル時間 441 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 78,812 KB
最終ジャッジ日時 2025-09-19 22:06:17
合計ジャッジ時間 7,279 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

Q=int(input())
v=[0]*200
for x in range(1,200):
  if x<10:
    v[x]=1
    continue
  y=str(x)
  ans=True
  for i in range(1,len(y)):
    if int(y[i])<int(y[i-1]):
      ans=False
  c=0
  for i in range(len(y)):
    c+=int(y[i])
  if v[c]==0:
    ans=False
  if ans==True:
    v[x]=1
for _ in range(Q):
  N=int(input())
  if N<=8:
    print('1'*(N+1))
    continue
  N+=1
  N=str(N)
  M=len(N)
  h=[0]*M
  for i in range(M):
    h[i]=int(N[i])
  for i in range(1,M):
    if h[i]<h[i-1]:
      for j in range(i,M):
        h[j]=h[i-1]
      break
  y=-1
  for i in range(M-1,-1,-1):
    if i<M-1:
      if h[i]==9:
        continue
      h[i]+=1
    for j in range(i+1,M):
      h[j]=h[i]
    l=sum(h)
    r=sum(h[:i])+9*(M-i)
    for x in range(l,r+1):
      if v[x]==1:
        y=x
        break
    if y>=0:
      break
  if y==-1:
    M+=1
    h=[1]*M
    l=M
    r=9*M
    for x in range(l,r+1):
      if v[x]==1:
        y=x
        break
  rest=y-sum(h)
  for i in range(M-1,-1,-1):
    c=min(9-h[i],rest)
    h[i]+=c
    rest-=c
  for i in range(len(h)):
    h[i]=str(h[i])
  N=int(N)
  d=''.join(h)
  d=int(d)
  x=(d-N)//8
  e=(d-N)%8
  mod=998244353
  result=pow(10,x,mod)-1+pow(10,x,mod)*((pow(10,N-x,mod)-1)*pow(9,-1,mod)+e)
  result%=mod
  print(result)
0