結果

問題 No.757 チャンパーノウン定数 (2)
ユーザー yuppe19 😺yuppe19 😺
提出日時 2018-12-05 17:17:36
言語 PyPy2
(7.1.1)
結果
AC   .
実行時間 1,887 ms / 2,000 ms
コード長 2,432 Byte
コンパイル時間 120 ms
使用メモリ 160,612 KB
最終ジャッジ日時 2020-06-30 03:48:03

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 127 ms
102,868 KB
testcase_01 AC 127 ms
102,868 KB
testcase_02 AC 127 ms
102,864 KB
testcase_03 AC 129 ms
102,864 KB
testcase_04 AC 127 ms
102,868 KB
testcase_05 AC 129 ms
102,876 KB
testcase_06 AC 128 ms
102,864 KB
testcase_07 AC 128 ms
102,868 KB
testcase_08 AC 127 ms
102,872 KB
testcase_09 AC 127 ms
102,868 KB
testcase_10 AC 128 ms
102,872 KB
testcase_11 AC 127 ms
102,864 KB
testcase_12 AC 128 ms
102,868 KB
testcase_13 AC 130 ms
102,868 KB
testcase_14 AC 129 ms
102,868 KB
testcase_15 AC 128 ms
102,864 KB
testcase_16 AC 127 ms
102,868 KB
testcase_17 AC 126 ms
102,868 KB
testcase_18 AC 131 ms
102,868 KB
testcase_19 AC 172 ms
103,008 KB
testcase_20 AC 126 ms
103,004 KB
testcase_21 AC 128 ms
102,992 KB
testcase_22 AC 126 ms
102,988 KB
testcase_23 AC 127 ms
102,996 KB
testcase_24 AC 127 ms
102,996 KB
testcase_25 AC 126 ms
102,980 KB
testcase_26 AC 127 ms
102,992 KB
testcase_27 AC 125 ms
102,996 KB
testcase_28 AC 1,405 ms
155,844 KB
testcase_29 AC 1,099 ms
144,772 KB
testcase_30 AC 139 ms
103,864 KB
testcase_31 AC 139 ms
103,624 KB
testcase_32 AC 130 ms
103,492 KB
testcase_33 AC 192 ms
113,348 KB
testcase_34 AC 535 ms
124,968 KB
testcase_35 AC 151 ms
104,900 KB
testcase_36 AC 144 ms
104,628 KB
testcase_37 AC 985 ms
142,660 KB
testcase_38 AC 1,237 ms
152,944 KB
testcase_39 AC 1,501 ms
160,608 KB
testcase_40 AC 1,783 ms
160,612 KB
testcase_41 AC 1,876 ms
160,608 KB
testcase_42 AC 1,059 ms
160,612 KB
testcase_43 AC 1,887 ms
160,604 KB
testcase_44 AC 1,812 ms
160,608 KB
testcase_45 AC 1,509 ms
160,604 KB
testcase_46 AC 1,450 ms
160,612 KB
testcase_47 AC 1,677 ms
160,608 KB
testcase_48 AC 1,218 ms
157,428 KB
testcase_49 AC 1,602 ms
160,604 KB
testcase_50 AC 131 ms
102,868 KB
testcase_51 AC 129 ms
102,868 KB
testcase_52 AC 128 ms
102,804 KB
testcase_53 AC 128 ms
102,800 KB
権限があれば一括ダウンロードができます

ソースコード

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