Problem:

短歌数

願はくは 花の下にて 春死なむ そのきさらぎの 望月のころ

これは，西行法師が詠んだとされる，有名な短歌の一つである．
短歌は，日本において古くから親しまれている和歌の一種であり，その多くは 5・7・5・7・7 の五句三十一音からなる．

ところで，57577 という数は，5 と 7 の二種類の数字からなる．
このような，十進表記がちょうど二種類の数字からなる正の整数を，短歌数と呼ぶことにする．
例えば，10, 12, 57577, 25252 などは短歌数であるが，5, 11, 123, 20180701 などは短歌数ではない．

正の整数 N が与えられる．N 番目に小さい短歌数を求めよ．

Input

入力は最大で 100 個のデータセットからなる．各データセットは次の形式で表される．

N

整数 N は 1 ≤ N ≤ 1018 を満たす．

入力の終わりは 1 つのゼロからなる行で表される．

Output

各データセットについて，N 番目に小さい短歌数を 1 行に出力せよ．

Sample Input

1
2
3
390
1124
1546
314159265358979323
0

Output for the Sample Input

10
12
13
2020
25252
57577
7744444777744474777777774774744777747477444774744744



Sample input:
1
2
3
390
1124
1546
314159265358979323
0


Sample output:
10
12
13
2020
25252
57577
7744444777744474777777774774744777747477444774744744

Submission status: Accepted

Solution code:
N = int(input())
while N:
    l = 2
    N -= 1
    while N >= ((1<<(l - 1)) - 1)*81:
        N -= ((1<<(l - 1)) - 1)*81
        l += 1
    s = N // (((1<<(l - 1)) - 1)*9) + 1
    N %= ((1<<(l - 1)) - 1)*9
    t = -1
    ans = str(s)
    #print("N = ", N)
    while t < 0:
        for i in range(s):
            if(N >= (1<<(l - 2))):
                N -= (1<<(l - 2))
            else:
                t = i
                break

        if t >= 0:
            continue

        if N >= ((1<<(l - 2)) - 1)*9:
            N -= ((1<<(l - 2)) - 1)*9
            for i in range(s+1, 10):
                if N >= (1<<(l-2)):
                    N -= (1<<(l-2))
                else:
                    t = i
                    break
        else:
            l -= 1
            ans += str(s)
    #print("N = ", N)
    ans += str(t)
    if s > t:
        b = bin(N)[2:]
        ans_ = str(t)*(l - 1 - len(b))
        C = [str(t), str(s)]
    else:
        b = bin(N)[2:]
        ans_ = str(s)*(l - 1 - len(b))
        C = [str(s), str(t)]

    for i in range(len(b)):
        ans_ += C[int(b[i])]
    print(ans+ans_[1:])
    N = int(input())

Submission status: Accepted

Solution code:
def solve(N):
    k = 0
    rng = 0
    for i in range(54):
        if cl[i] < N <= cl[i+1]:
            k = i + 2
            rng2 = cl[i]
            rng = cl[i+1] - cl[i]
    # print(k)
    posrng = (N-rng2)%(rng//9)
    perrng = (N-rng2)//(rng//9)+1
    if posrng == 0:
        posrng = rng//9
        perrng -= 1
    ans = [perrng]
    for i in range(k-1):
        if i == k-2:
            tmp = [0 if j == perrng else 1 for j in range(10)]
        else:
            tmp = [(cl[k-i-2]-cl[k-i-3])//9 if j == perrng else 2**(k-i-2) for j in range(10)]
        if posrng <= tmp[0]:
            ans.append(0)
            # posrng = posrng
        for j in range(1, 10):
            tmp[j] += tmp[j-1]
            if tmp[j-1] < posrng <=tmp[j]:
                ans.append(j)
                posrng -= tmp[j-1]
        if max(ans) != min(ans):
            break
    for i in range(k-len(ans), 0, -1):
        if posrng <= 2**(i-1):
            ans.append(min(ans))
        else:
            ans.append(max(ans))
            posrng -= 2**(i-1)
    print(''.join(map(str, ans)))

cl = [sum([9*2**j for j in range(i)])*9 for i in range(55)]
for i in range(1, 55):
    cl[i] += cl[i-1]
while True:
    N = int(input())
    if N == 0:
        break
    solve(N)

Submission status: Runtime Error

Solution code:
# 文字列s以下のa,bを使った短歌数
def calc(a, b, s):
    sz = len(s)
    dp = [[0] * 2 for i in range(sz + 1)]
    dp[0][0] = 1
    dp[0][1] = 0
    for i in range(sz):
        if s[i] == str(a):
            dp[i + 1][0] += dp[i][0]
        elif s[i] > str(a):
            if i == 0 and a == 0:
                a == 0
            else:
                dp[i + 1][1] += dp[i][0]
        if s[i] == str(b):
            dp[i + 1][0] += dp[i][0]
        elif s[i] > str(b):
            dp[i + 1][1] += dp[i][0]

        dp[i + 1][1] += dp[i][1] * 2
    
    # for i in range(sz + 1):
    #    print(dp[i])
    res = dp[sz][0] + dp[sz][1]
    if a != 0 and str(a) * sz <= s:
        res -= 1
    if str(b) * sz <= s:
        res -= 1
    return res

def check(x, N):
    s = str(x)
    sz = len(s)
    res = 0
    for i in range(0, 10):
        for j in range(i + 1, 10):
            tmp = calc(i, j, s)
            res += tmp
    for i in range(2, sz):
        res += 45 * (2 ** i - 2) - 9 * (2 ** (i - 1) - 1)
    return res >= N

while True:
    N = int(input())
    if N == 0:
        break
    ng = 1
    ok = 10 ** 61
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if (check(mid, N)): ok = mid
        else: ng = mid
    print(ok)