結果

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

ソースコード

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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0