結果

問題 No.757 チャンパーノウン定数 (2)
コンテスト
ユーザー 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 WA * 17 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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