結果

問題 No.294 SuperFizzBuzz
ユーザー rpy3cpprpy3cpp
提出日時 2015-10-24 00:16:05
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
AC  
実行時間 113 ms / 5,000 ms
コード長 2,421 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 11,028 KB
実行使用メモリ 8,260 KB
最終ジャッジ日時 2023-10-11 05:01:03
合計ジャッジ時間 1,661 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
8,136 KB
testcase_01 AC 17 ms
8,148 KB
testcase_02 AC 25 ms
8,140 KB
testcase_03 AC 17 ms
8,172 KB
testcase_04 AC 18 ms
8,176 KB
testcase_05 AC 17 ms
8,176 KB
testcase_06 AC 17 ms
8,260 KB
testcase_07 AC 18 ms
8,144 KB
testcase_08 AC 23 ms
8,192 KB
testcase_09 AC 113 ms
8,188 KB
testcase_10 AC 18 ms
8,172 KB
testcase_11 AC 35 ms
8,148 KB
testcase_12 AC 77 ms
8,200 KB
testcase_13 AC 90 ms
8,104 KB
testcase_14 AC 25 ms
8,160 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