結果

問題 No.757 チャンパーノウン定数 (2)
ユーザー yuppe19 😺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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
108,320 KB
testcase_01 AC 92 ms
107,904 KB
testcase_02 AC 90 ms
108,544 KB
testcase_03 AC 92 ms
108,324 KB
testcase_04 AC 91 ms
107,796 KB
testcase_05 AC 92 ms
107,908 KB
testcase_06 AC 91 ms
108,288 KB
testcase_07 AC 91 ms
108,160 KB
testcase_08 AC 96 ms
108,060 KB
testcase_09 AC 92 ms
108,068 KB
testcase_10 AC 94 ms
108,032 KB
testcase_11 AC 92 ms
108,160 KB
testcase_12 AC 99 ms
107,928 KB
testcase_13 AC 97 ms
108,032 KB
testcase_14 AC 95 ms
108,160 KB
testcase_15 AC 93 ms
108,160 KB
testcase_16 AC 94 ms
107,824 KB
testcase_17 AC 95 ms
108,440 KB
testcase_18 AC 100 ms
107,904 KB
testcase_19 AC 96 ms
108,060 KB
testcase_20 AC 93 ms
108,160 KB
testcase_21 AC 96 ms
108,032 KB
testcase_22 AC 100 ms
108,672 KB
testcase_23 AC 95 ms
108,544 KB
testcase_24 AC 94 ms
108,160 KB
testcase_25 AC 93 ms
108,112 KB
testcase_26 AC 99 ms
107,944 KB
testcase_27 AC 95 ms
108,160 KB
testcase_28 AC 1,873 ms
161,280 KB
testcase_29 AC 1,205 ms
149,632 KB
testcase_30 AC 105 ms
109,772 KB
testcase_31 AC 105 ms
109,952 KB
testcase_32 AC 96 ms
109,392 KB
testcase_33 AC 147 ms
119,040 KB
testcase_34 AC 371 ms
129,920 KB
testcase_35 AC 108 ms
109,796 KB
testcase_36 AC 106 ms
110,336 KB
testcase_37 AC 1,000 ms
148,096 KB
testcase_38 AC 1,575 ms
157,952 KB
testcase_39 AC 1,899 ms
165,472 KB
testcase_40 TLE -
testcase_41 TLE -
testcase_42 AC 1,424 ms
165,756 KB
testcase_43 TLE -
testcase_44 AC 1,928 ms
165,856 KB
testcase_45 AC 1,865 ms
165,632 KB
testcase_46 AC 1,840 ms
165,720 KB
testcase_47 TLE -
testcase_48 AC 1,660 ms
162,424 KB
testcase_49 AC 1,933 ms
166,464 KB
testcase_50 AC 89 ms
107,928 KB
testcase_51 AC 91 ms
108,288 KB
testcase_52 AC 93 ms
108,192 KB
testcase_53 AC 92 ms
107,904 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