結果

問題 No.294 SuperFizzBuzz
ユーザー rpy3cpprpy3cpp
提出日時 2015-10-24 00:16:05
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 151 ms / 5,000 ms
コード長 2,421 bytes
コンパイル時間 318 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-09-13 04:18:58
合計ジャッジ時間 1,790 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
10,880 KB
testcase_01 AC 32 ms
11,008 KB
testcase_02 AC 40 ms
10,880 KB
testcase_03 AC 31 ms
11,008 KB
testcase_04 AC 31 ms
10,880 KB
testcase_05 AC 32 ms
10,880 KB
testcase_06 AC 31 ms
11,008 KB
testcase_07 AC 32 ms
10,880 KB
testcase_08 AC 39 ms
11,008 KB
testcase_09 AC 151 ms
11,008 KB
testcase_10 AC 31 ms
10,880 KB
testcase_11 AC 53 ms
11,008 KB
testcase_12 AC 105 ms
11,008 KB
testcase_13 AC 121 ms
11,008 KB
testcase_14 AC 41 ms
11,008 KB
権限があれば一括ダウンロードができます

ソースコード

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+1, N
        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