結果

問題 No.757 チャンパーノウン定数 (2)
ユーザー yuppe19 😺yuppe19 😺
提出日時 2018-12-05 17:17:36
言語 PyPy2
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,432 bytes
コンパイル時間 1,829 ms
コンパイル使用メモリ 77,800 KB
実行使用メモリ 167,128 KB
最終ジャッジ日時 2023-09-26 13:03:37
合計ジャッジ時間 39,091 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 102 ms
108,452 KB
testcase_01 AC 100 ms
108,868 KB
testcase_02 AC 100 ms
108,628 KB
testcase_03 AC 100 ms
108,552 KB
testcase_04 AC 102 ms
108,456 KB
testcase_05 AC 102 ms
108,672 KB
testcase_06 AC 104 ms
108,236 KB
testcase_07 AC 99 ms
108,836 KB
testcase_08 AC 100 ms
108,476 KB
testcase_09 AC 101 ms
108,520 KB
testcase_10 AC 102 ms
108,348 KB
testcase_11 AC 102 ms
108,544 KB
testcase_12 AC 101 ms
108,356 KB
testcase_13 AC 101 ms
108,384 KB
testcase_14 AC 99 ms
108,696 KB
testcase_15 AC 100 ms
108,708 KB
testcase_16 AC 101 ms
108,388 KB
testcase_17 AC 102 ms
108,868 KB
testcase_18 AC 104 ms
108,500 KB
testcase_19 AC 101 ms
108,284 KB
testcase_20 AC 101 ms
108,508 KB
testcase_21 AC 101 ms
108,628 KB
testcase_22 AC 105 ms
108,468 KB
testcase_23 AC 99 ms
108,384 KB
testcase_24 AC 99 ms
108,948 KB
testcase_25 AC 102 ms
108,416 KB
testcase_26 AC 102 ms
108,268 KB
testcase_27 AC 102 ms
108,492 KB
testcase_28 AC 1,985 ms
161,484 KB
testcase_29 AC 1,418 ms
150,480 KB
testcase_30 AC 112 ms
110,476 KB
testcase_31 AC 111 ms
109,704 KB
testcase_32 AC 103 ms
109,896 KB
testcase_33 AC 157 ms
119,636 KB
testcase_34 AC 510 ms
130,732 KB
testcase_35 AC 126 ms
111,032 KB
testcase_36 AC 114 ms
110,380 KB
testcase_37 AC 1,198 ms
148,244 KB
testcase_38 AC 1,739 ms
159,028 KB
testcase_39 TLE -
testcase_40 TLE -
testcase_41 TLE -
testcase_42 AC 1,770 ms
166,588 KB
testcase_43 TLE -
testcase_44 TLE -
testcase_45 TLE -
testcase_46 TLE -
testcase_47 TLE -
testcase_48 AC 1,845 ms
163,484 KB
testcase_49 TLE -
testcase_50 AC 100 ms
108,648 KB
testcase_51 AC 99 ms
108,492 KB
testcase_52 AC 104 ms
108,328 KB
testcase_53 AC 104 ms
108,348 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