結果

問題 No.362 門松ナンバー
コンテスト
ユーザー titia
提出日時 2026-01-04 03:55:41
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 374 ms / 3,000 ms
コード長 2,723 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 251 ms
コンパイル使用メモリ 82,052 KB
実行使用メモリ 79,616 KB
最終ジャッジ日時 2026-01-04 03:55:50
合計ジャッジ時間 8,014 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

T=int(input())

for tests in range(T):
    K=int(input())

    OK=37294859064823
    NG=101

    while OK>NG+1:
        mid=(OK+NG)//2

        DP1=[[0]*10 for i in range(10)]
        DP2=[[0]*10 for i in range(10)]

        S=list(map(int,list(str(mid))))

        for i in range(S[0]+1):
            if i==0:
                continue
            if i==S[0]:
                for j in range(S[1]+1):
                    if j==S[1]:
                        if i!=j:
                            DP1[i][j]+=1
                    else:
                        if i!=j:
                            DP2[i][j]+=1
            else:
                for j in range(10):
                    if i!=j:
                        DP2[i][j]+=1

        for keta in range(2,len(S)):
            x=S[keta]
            NDP1=[[0]*10 for i in range(10)]
            NDP2=[[0]*10 for i in range(10)]

            for i in range(10):
                for j in range(10):
                    if DP1[i][j]==0:
                        continue
                    for k in range(x+1):
                        if x==k:
                            if i<j and j>k and i!=k:
                                NDP1[j][k]+=DP1[i][j]
                            elif i>j and j<k and i!=k:
                                NDP1[j][k]+=DP1[i][j]
                        else:
                            if i<j and j>k and i!=k:
                                NDP2[j][k]+=DP1[i][j]
                            elif i>j and j<k and i!=k:
                                NDP2[j][k]+=DP1[i][j]

            for i in range(10):
                for j in range(10):
                    if DP2[i][j]==0:
                        continue
                    for k in range(10):
                        if i<j and j>k and i!=k:
                            NDP2[j][k]+=DP2[i][j]
                        elif i>j and j<k and i!=k:
                            NDP2[j][k]+=DP2[i][j]

            if keta>=3:
                for i in range(10):
                    if i==0:
                        continue
                    for j in range(10):
                        for k in range(10):
                            if i<j and j>k and i!=k:
                                NDP2[j][k]+=1
                            if i>j and j<k and i!=k:
                                NDP2[j][k]+=1


            DP1=NDP1
            DP2=NDP2

        ko=0
        for i in range(10):
            for j in range(10):
                ko+=DP1[i][j]+DP2[i][j]

        #print(mid,ko)

        if ko>=K:
            OK=mid
        else:
            NG=mid

    print(OK)
0