結果

問題 No.757 チャンパーノウン定数 (2)
ユーザー yuppe19 😺
提出日時 2018-12-05 17:17:36
言語 PyPy2
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,432 bytes
コンパイル時間 1,204 ms
コンパイル使用メモリ 76,800 KB
実行使用メモリ 166,464 KB
最終ジャッジ日時 2024-07-19 07:27:55
合計ジャッジ時間 34,128 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 48 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/python2
# -*- coding: utf-8 -*-
# †
from math import log
from collections import deque

digits = [0,1,2,3,4,5,6,7,8,9]

# 基数変換. 10進数の{num}を{base}進数にします。
def int2base(num, base):
    assert base > 1
    if num == 0:
        return [digits[0]]
    v = []
    while num != 0:
        q, r = divmod(num, base)
        v.append(digits[r])
        num = q
    v.reverse()
    return v

# 基数変換. {base}進数で表現された{s}を10進数にします。
#base2int = lambda s, base: int(s, base)
def base2int(v, base):
    if len(v) == 0:
        return 0
    num = 0
    for c in v:
        num *= base
        num += digits[c]
    return num

# B進 で v0 + v1
def add(v0, v1, B):
    n0 = len(v0)
    n1 = len(v1)
    n = max(n0, n1) + 1
    v0 = [0] * (n - n0) + v0
    v1 = [0] * (n - n1) + v1
    v = deque([0] * n)
    carry = 0
    for i in reversed(xrange(1, n)):
        v[i] = carry + v0[i] + v1[i]
        if v[i] >= B:
            v[i] -= B
            carry = 1
    while v[0] == 0 and len(v) > 1:
        v.popleft()
    return v
        

# B進 で v0 - v1
# v0 >= v1 であること
def sub(v0, v1, B):
    n0 = len(v0)
    n1 = len(v1)
    v1 = [0] * (n0-n1) + v1
    v = deque(v0)
    for i in reversed(xrange(n0)):
        v[i] -= v1[i]
        if v[i] < 0:
            v[i-1] -= 1
            v[i] += B
    while v[0] == 0 and len(v) > 1:
        v.popleft()
    return v


# s <= t か
def leq(s, t):
    n1 = len(s)
    n2 = len(t)
    if n1 < n2:
        return True
    if n1 > n2:
        return False
    for i in xrange(n1):
        if s[i] < t[i]:
            return True
        if s[i] > t[i]:
            return False
    return True


# i文字の開始位置 B進
def create(B, i):
    if i == 1:
        return [1]
    if i == 2:
        return [1, 0]
    res = int2base(i-2, B) + [B-2] * (i-3) + [B-1, 0]
    return res



def f(B, D):
    lo, hi = 0, 10**6 # lo: D番目が属する文字数
    while hi - lo > 1:
        md = (lo + hi) / 2
        rrr = leq(create(B, md), D)
        if rrr:
            lo = md
        else:
            hi = md
    posB = create(B, lo)
    difB = sub(D, posB, B)
    dif10 = base2int(difB, B)
    if dif10 == 0:
        return 1
    z, r = divmod(dif10, lo)
    w = z + B**(lo-1)
    m = int(log(w, B)) + 1
    return (w / B**(m-1-r)) % B


B = int(raw_input())
D = map(int, raw_input())
res = f(B, D)
print res
0