結果

問題 No.757 チャンパーノウン定数 (2)
ユーザー yuppe19 😺yuppe19 😺
提出日時 2018-12-05 13:58:25
言語 PyPy2
(7.3.15)
結果
WA  
実行時間 -
コード長 1,723 bytes
コンパイル時間 1,318 ms
コンパイル使用メモリ 76,728 KB
実行使用メモリ 87,864 KB
最終ジャッジ日時 2024-07-18 16:03:00
合計ジャッジ時間 26,054 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
75,512 KB
testcase_01 AC 68 ms
75,928 KB
testcase_02 AC 70 ms
75,772 KB
testcase_03 AC 70 ms
75,932 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 72 ms
75,680 KB
testcase_07 AC 72 ms
75,640 KB
testcase_08 WA -
testcase_09 AC 69 ms
75,904 KB
testcase_10 AC 72 ms
75,520 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 68 ms
75,688 KB
testcase_15 AC 68 ms
75,520 KB
testcase_16 AC 69 ms
75,676 KB
testcase_17 AC 68 ms
75,812 KB
testcase_18 AC 68 ms
75,916 KB
testcase_19 AC 69 ms
75,460 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 67 ms
75,800 KB
testcase_23 WA -
testcase_24 AC 68 ms
75,836 KB
testcase_25 WA -
testcase_26 AC 67 ms
75,704 KB
testcase_27 AC 66 ms
75,792 KB
testcase_28 AC 1,507 ms
82,468 KB
testcase_29 WA -
testcase_30 AC 76 ms
78,264 KB
testcase_31 AC 122 ms
77,856 KB
testcase_32 AC 68 ms
76,692 KB
testcase_33 AC 103 ms
77,588 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 74 ms
77,996 KB
testcase_37 AC 810 ms
79,528 KB
testcase_38 WA -
testcase_39 WA -
testcase_40 TLE -
testcase_41 AC 1,924 ms
86,004 KB
testcase_42 AC 612 ms
77,976 KB
testcase_43 AC 1,829 ms
83,492 KB
testcase_44 AC 1,681 ms
84,764 KB
testcase_45 AC 1,185 ms
81,800 KB
testcase_46 AC 1,200 ms
80,412 KB
testcase_47 AC 1,310 ms
83,488 KB
testcase_48 AC 798 ms
79,352 KB
testcase_49 AC 1,285 ms
82,460 KB
testcase_50 WA -
testcase_51 WA -
testcase_52 AC 67 ms
76,032 KB
testcase_53 AC 66 ms
75,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

# 基数変換. 10進数の{num}を{base}進数にします。
def int2base(num, base, digits=string.digits+string.ascii_uppercase):
    assert base > 1
    is_negative = num < 0
    num = abs(num)
    if num == 0:
        return digits[0]
    s = ''
    while num != 0:
        s = digits[num % base] + s
        num /= base
    if is_negative:
        s = '-' + s
    return s

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


# 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 ord(s[i]) > ord(t[i]):
            return False
    return True

# i文字の開始位置
def create(B, i):
    if i == 1:
        return '10'
    res = int2base(i-1, B) + str(B-2) * (i-2) + str(B-1) + '0'
    return res


def f(B, D):
    DB = base2int(D, B)
    lo, hi = 0, len(D)
    while hi - lo > 1:
        md = (lo + hi) / 2
        if leq(create(B, md), D):
            lo = md
        else:
            hi = md
    x = base2int(create(B, lo), B)
    z, r = divmod(DB-x, hi)
    w = z + B**lo
    m = int(log(w, B)) + 1
#    p = int2base(w, B)
#    return p[r]
    return (w / B**(m-1-r)) % B


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