結果

問題 No.294 SuperFizzBuzz
コンテスト
ユーザー rpy3cpp
提出日時 2015-10-24 00:04:07
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 2,420 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-09-13 04:13:55
合計ジャッジ時間 1,787 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math


def f(a, b):
    n = a + 3 * b - 1
    return math.factorial(n)//math.factorial(a)//math.factorial(n - a)


def g(k):
    return sum(f(k - 3 * b, b) for b in range(1, k//3 + 1))


def find(N, k, use=False):
    '''k 桁の super fizz buzz 数のうち、N 番目に大きいものを返す。
    '''
    start = 0
    if use and k >= 20:
        start, N = use_cheat(k, N)
    for i in range(start, 2**(k-1)):
        if bin(i).count('1') % 3 == 2:
            N -= 1
            if N == 0:
                return convert2_35(i, k)

# 計算が間に合わないから予め10万毎に計算しておいて、近くの値からスタートする。
#def emb(k):
#    tic = 10**5
#    cum = 0
#    lst = [0]
#    for i in range(2**(k-1)):
#        if bin(i).count('1') % 3 == 2:
#            cum += 1
#            if cum % tic == 0:
#                lst.append(i)
#    return lst

#cheat = [emb(k) for k in range(20, 26)]

#for ch in cheat:
#    print(','.join(map(str, ch)))

cheat = [[0,299997],
[0,299997,600000,900000],
[0,299997,600000,900000,1200007,1499986,1799996],
[0,299997,600000,900000,1200007,1499986,1799996,2100007,2400000,2700005,2999991,3299993,3599992,3899994],
[0,299997,600000,900000,1200007,1499986,1799996,2100007,2400000,2700005,2999991,3299993,3599992,3899994,4199996,4500002,4799994,5099995,5399988,5699993,5999996,6299994,6599980,6899995,7199997,7499986,7799992,8100007],
[0,299997,600000,900000,1200007,1499986,1799996,2100007,2400000,2700005,2999991,3299993,3599992,3899994,4199996,4500002,4799994,5099995,5399988,5699993,5999996,6299994,6599980,6899995,7199997,7499986,7799992,8100007,8399988,8700003,9000001,9299994,9599988,9899993,10200000,10499996,10799984,11099993,11399988,11699993,12000004,12299998,12599992,12899985,13199991,13500007,13799994,14100004,14399996,14700001,15000001,15300006,15599998,15900009,16199996,16499993]]


def use_cheat(k, N):
    ch = cheat[k - 20]
    tic = 10**5
    for c in ch:
        if N <= tic:
            return c, N+1
        N -= tic

def convert2_35(i, k):
    i = 2 * i + 1
    idx = 1 << (k - 1)
    ans = []
    while idx:
        if i & idx:
            ans.append('5')
        else:
            ans.append('3')
        idx >>= 1
    return ''.join(ans)

def solve(N):
    for k in range(3, 26):
        gk = g(k)
        if N <= gk:
            break
        N -= gk
    return(find(N, k, True))

N = int(input())
print(solve(N))
0