Problem:


FizzBuzz

FizzBuzzとは、1以上の整数を順に、以下のルールに従って発言していくゲームである。

 3で割り切れる時には「Fizz」

 5で割り切れる時には「Buzz」

 3と5の両方で割り切れる時には「FizzBuzz」

 それ以外の時はその数字

ゲームの進行状況の例を以下に示す。

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, …

得られた発言を1つの文字列に結合し得られた文字列をFizzBuzz Stringと呼ぶ。インデックスsが与えられるので、FizzBuzz Stringのs文字目から20文字を出力せよ。但し、インデックスは1から始まるものとし、得られた文字列の長さは十分に大きい（s+20以上）としてよい。

Input

入力は以下の形式で与えられる

s

Constraints

 sは整数である

 1 ≤ s ≤ 1018

Output

FizzBuzz Stringのs文字目から20文字を1行に出力せよ

Sample Input 1

1

Output for the Sample Input 1

12Fizz4BuzzFizz78Fiz

Sample Input 2

20

Output for the Sample Input 2

zzBuzz11Fizz1314Fizz

Sample Input 3

10000000000

Output for the Sample Input 3

93FizzBuzz1418650796



Sample input:
1


Sample output:
12Fizz4BuzzFizz78Fiz

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def main():
    S = int(raw_input()) - 1
    FizzBuzzString = '12Fizz4BuzzFizz78FizzBuzz11Fizz1314FizzBuzz'
    size = len(FizzBuzzString)
    start_index = S % size
    end_index = start_index + 20
    
    return FizzBuzzString[start_index:end_index]

print main()

Submission status: Accepted

Solution code:
D = 20
ds = [0]*D

from math import log10

for i in xrange(1, D):
    fr = 10**(i-1)-1
    to = 10**i-1
    ds[i] = ds[i-1] + (4-i)*(to/3 + to/5 - (to/15)*2 - fr/3 - fr/5 + (fr/15)*2) + (8-i)*(to/15 - fr/15) + i*(to-fr)

def calc(m):
    if m == 0:
        return 0
    c = int(log10(m))+1
    fr = 10**(c-1)-1
    to = m
    return ds[c-1] + (4-c)*(to/3 + to/5 - (to/15)*2 - fr/3 - fr/5 + (fr/15)*2) + (8-c)*(to/15 - fr/15) + c*(to-fr)

s = input()
left = 0; right = 10**18
while left+1 < right:
    mid = (left + right) / 2
    if calc(mid) <= s-1:
        left = mid
    else:
        right = mid
idx = calc(left)
num = left+1
ans = ""
while len(ans) < s - idx + 20:
    if num % 15 == 0:
        ans += "FizzBuzz"
    elif num % 3 == 0:
        ans += "Fizz"
    elif num % 5 == 0:
        ans += "Buzz"
    else:
        ans += str(num)
    num += 1
print ans[s-idx-1:s-idx+19]

Submission status: Accepted

Solution code:
def calc_start(mid):
    cnt = -1
    i = 1
    while 10 ** i < mid:
        cnt += i * (10 ** i - 10 ** (i - 1))
        fif = (10 ** i - 1) // 15 - (10 ** (i - 1) - 1) // 15
        three = (10 ** i - 1) // 3 - (10 ** (i - 1) - 1) // 3
        five = (10 ** i - 1) // 5 - (10 ** (i - 1) - 1) // 5
        cnt += (three + five) * 4 - (three + five - fif) * i
        i += 1
    cnt += i * (mid - 10 ** (i - 1))
    fif = (mid - 1) // 15 - (10 ** (i - 1) - 1) // 15
    three = (mid - 1) // 3 - (10 ** (i - 1) - 1) // 3
    five = (mid - 1) // 5 - (10 ** (i - 1) - 1) // 5
    cnt += (three + five) * 4 - (three + five - fif) * i
    return cnt + 1


N = int(input()) - 1
left, right = 1, 10 ** 18
while left + 1 < right:
    mid = (left + right) // 2
    start = calc_start(mid)
    if start <= N:
        left = mid
    else:
        right = mid
ans = ''
for i in range(left, left + 30):
    tmp = ''
    if i % 3 == 0:
        tmp += "Fizz"
    if i % 5 == 0:
        tmp += "Buzz"
    if not tmp:
        tmp = str(i)
    ans += tmp
start = calc_start(left)
print(ans[N - start:N - start + 20])

Submission status: Accepted

Solution code:
def count_div(start, end, div):
    # [start, end)
    return (end - 1) // div - (start - 1) // div


def calc_start(mid):
    cnt, i = 0, 1
    while 10 ** i < mid:
        d, p = 10 ** i, 10 ** (i - 1)
        fif, three, five = count_div(p, d, 15), count_div(p, d, 3), count_div(p, d, 5)
        cnt += i * (d - p) + (three + five) * 4 - (three + five - fif) * i
        i += 1
    d = 10 ** (i - 1)
    fif, three, five = count_div(d, mid, 15), count_div(d, mid, 3), count_div(d, mid, 5)
    cnt += i * (mid - d) + (three + five) * 4 - (three + five - fif) * i
    return cnt


N = int(input()) - 1
left, right = 1, 10 ** 18
while left + 1 < right:
    mid = (left + right) // 2
    start = calc_start(mid)
    if start <= N:
        left = mid
    else:
        right = mid
ans = ''
for i in range(left, left + 30):
    tmp = ''
    if i % 3 == 0:
        tmp += "Fizz"
    if i % 5 == 0:
        tmp += "Buzz"
    if not tmp:
        tmp = str(i)
    ans += tmp
start = calc_start(left)
print(ans[N - start:N - start + 20])

Submission status: Accepted

Solution code:
def count_div(start, end, div):
    # [start, end)
    return (end - 1) // div - (start - 1) // div


def calc_start(mid):
    cnt, i = 0, 1
    while 10 ** i < mid:
        d, p = 10 ** i, 10 ** (i - 1)
        fif, three, five = count_div(p, d, 15), count_div(p, d, 3), count_div(p, d, 5)
        cnt += i * (d - p) + (three + five) * 4 - (three + five - fif) * i
        i += 1
    d = 10 ** (i - 1)
    fif, three, five = count_div(d, mid, 15), count_div(d, mid, 3), count_div(d, mid, 5)
    cnt += i * (mid - d) + (three + five) * 4 - (three + five - fif) * i
    return cnt


N = int(input()) - 1
left, right = 1, 10 ** 18
while left + 1 < right:
    mid = (left + right) // 2
    start = calc_start(mid)
    if start <= N:
        left = mid
    else:
        right = mid
ans = ''
for i in range(left, left + 9):
    tmp = ''
    if i % 3 == 0:
        tmp += "Fizz"
    if i % 5 == 0:
        tmp += "Buzz"
    if not tmp:
        tmp = str(i)
    ans += tmp
start = calc_start(left)
print(ans[N - start:N - start + 20])

Submission status: Accepted

Solution code:


def fizzbuzz_length(n):
  f3 = 0
  f5 = 0
  f15 = 0
  folen = 0
  keta = 1
  while True:
    ub = 10**keta - 1
    lim = min(n, ub)
    folen += keta * (lim-10**(keta-1)+1 - (lim // 3 - f3) - (lim // 5 - f5) + (lim//15 - f15))
    f3 = lim // 3
    f5 = lim // 5
    f15 = lim // 15
    if n <= ub:
      break
    keta += 1
  return folen + 4 * (f3 + f5)
  
def fizzbuzz(i):
  if i % 15 == 0:
    return "FizzBuzz"
  elif i % 3 == 0:
    return "Fizz"
  elif i % 5 == 0:
    return "Buzz"
  else:
    return str(i)
  
s = int(input())
  
lb = 0
ub = s

while ub - lb > 1:
  m = (ub + lb) // 2
  if s <= fizzbuzz_length(m):
    ub = m
  else:
    lb = m

ans = ""
for i in range(ub, ub + 20):
  ans += fizzbuzz(i)

pos  = s - fizzbuzz_length(ub-1) - 1
print(ans[pos:pos+20])

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

s = input()

m = {}
m[0] = 0
index = 0
for i in range(20):
    minx = 10 ** i
    maxx = 10 ** (i + 1) - 1
    F_num = maxx // 3 - minx // 3
    B_num = maxx // 5 - (minx - 1) // 5
    FB_num = maxx // 15 - minx // 15
    P_num = maxx - minx - F_num - B_num + FB_num + 1
    m[i + 1] = m[i] + P_num * (i + 1) + F_num * 4 + B_num * 4
    if s <= m[i + 1]:
        s -= m[i]
        index = i + 1
        break

#print index
ans = []
rem = 0

for i in range(index - 1, -1, -1):
    rem *= 10
    lst = range(10)
    if rem == 0:
        lst = range(1, 11)
    for j in lst:
        minx = rem + j * (10 ** i)
        maxx = rem + (j + 1) * (10 ** i) - 1
        F_num = maxx // 3 - (minx - 1) // 3
        B_num = maxx // 5 - (minx - 1) // 5
        FB_num = maxx // 15 - (minx - 1) // 15
        P_num = maxx - minx - F_num - B_num + FB_num + 1
        S_num = P_num * (index) + F_num * 4 + B_num * 4
        #print minx, maxx
        #print S_num
        if s > S_num:
            s -= S_num
        else:
            rem += j
            break
S = ""
for num in range(rem, rem + 100):
    if num % 3 == 0:
        S += "Fizz"
    if num % 5 == 0:
        S += "Buzz"
    if num % 3 != 0 and num % 5 != 0:
        S += str(num)
print S[s - 1:s + 19]

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

s = input()

m = {}
m[0] = 0
index = 0
for i in range(20):
    minx = 10 ** i
    maxx = 10 ** (i + 1) - 1
    F_num = maxx // 3 - minx // 3
    B_num = maxx // 5 - (minx - 1) // 5
    FB_num = maxx // 15 - minx // 15
    P_num = maxx - minx - F_num - B_num + FB_num + 1
    m[i + 1] = m[i] + P_num * (i + 1) + F_num * 4 + B_num * 4
    if s < m[i + 1]:
        s -= m[i]
        index = i + 1
        break

#print index
ans = []
rem = 0

for i in range(index - 1, -1, -1):
    rem *= 10
    lst = range(10)
    if rem == 0:
        lst = range(1, 10)
    for j in lst:
        minx = rem + j * (10 ** i)
        maxx = rem + (j + 1) * (10 ** i) - 1
        F_num = maxx // 3 - (minx - 1) // 3
        B_num = maxx // 5 - (minx - 1) // 5
        FB_num = maxx // 15 - (minx - 1) // 15
        P_num = maxx - minx - F_num - B_num + FB_num + 1
        S_num = P_num * (index) + F_num * 4 + B_num * 4
        #print minx, maxx
        #print S_num
        if s > S_num:
            s -= S_num
        else:
            rem += j
            break
S = ""
for num in range(rem, rem + 100):
    if num % 3 == 0:
        S += "Fizz"
    if num % 5 == 0:
        S += "Buzz"
    if num % 3 != 0 and num % 5 != 0:
        S += str(num)
print S[s - 1:s + 19]

Submission status: Accepted

Solution code:
def f(n):
    i = 0
    while (10**i <= n):
        i += 1
    i -= 1
    return 8 if n % 15 == 0 else 4 if n % 3 == 0 or n % 5 == 0 else i


def fizzbuzzlen(n):
    if n == 0:
        return 0
    i = 0
    ans = 0
    while (10**i <= n):
        start = 10**i
        end = min(10**(i+1)-1, n)
        numbase = (end-start+1)
        num3 = end//3-(start-1)//3
        num5 = end//5-(start-1)//5
        num15 = end//15-(start-1)//15
        numbase = numbase-num3-num5+num15
        ans += (i+1)*numbase+4*num3+4*num5  # +8*num15
        i += 1
    return ans


n = int(input())

# print("".join(["FizzBuzz" if i % 15 == 0 else "Buzz" if i % 5 ==
#              0 else "Fizz" if i % 3 == 0 else str(i) for i in range(1, n+20)])[n-1:n-1+20])


l = 0
r = 10**18+1
while (l+1 != r):
    med = (l+r)//2
    if (fizzbuzzlen(med) < n):
        l = med
    else:
        r = med
s = "".join(["0"if i == 0 else "FizzBuzz" if i % 15 == 0 else "Buzz" if i % 5 ==
             0 else "Fizz" if i % 3 == 0 else str(i) for i in range(l+1, l+21)])
print(s[n-fizzbuzzlen(l)-1:n-fizzbuzzlen(l)-1+20])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    if n < 30:
        s = ''
        for i in range(1, 100):
            if i % 15 == 0:
                s += 'FizzBuzz'
            elif i % 5 == 0:
                s += 'Buzz'
            elif i % 3 == 0:
                s += 'Fizz'
            else:
                s += str(i)
        # print(s)
        return s[n-1:n+19]
    i = 2
    n -= 4 * 4 + 5
    while 1:
        t = 10**i - (10**(i-1))
        s3 = t // 3
        s5 = t // 5
        s15 = t // 15
        sl = s3 + s5 - s15
        tl = (s3 + s5) * 4 + (t - sl) * i
        if tl >= n:
            break
        n -= tl
        i += 1

    si = 10**(i-1) - 1
    for j in range(i-1,0,-1):
        t = 10**j
        for k in range(1,10):
            s3 = (si+t) // 3 - si // 3
            s5 = (si+t) // 5 - si // 5
            s15 = (si+t) // 15 - si // 15
            sl = s3 + s5 - s15
            tl = (s3 + s5) * 4 + (t - sl) * i
            if tl >= n:
                break
            n -= tl
            si += t
    # print('si,n',si,n)
    s = ''
    for i in range(si+1,si+100):
        if i % 15 == 0:
            s += 'FizzBuzz'
        elif i % 5 == 0:
            s += 'Buzz'
        elif i % 3 == 0:
            s += 'Fizz'
        else:
            s += str(i)
    # print(s)

    return s[n-1:n+19]


print(main())

Submission status: Accepted

Solution code:
# coding: utf-8

def f(n):
    return (n*8+32)*6*10**(n-2)-5

i=2
count=0
s=int(input())
while 1:
    if count+f(i)<s:
        count+=f(i)
    else:
        break
    i+=1
j=0
x=10**(i-1)-9
tmp=(s-count)//(i*8+32)
count-=(5 if tmp!=0 else 0)
count+=tmp*(i*8+32)
x+=tmp*15
fzbz=''
while len(fzbz)<=s-count+100:
    fzbz+=('FizzBuzz' if x%15==0 else 'Fizz' if x%3==0 else 'Buzz' if x%5==0 else str(x))
    x+=1
print(fzbz[s-count-1:s-count-1+20])