結果
問題 | No.757 チャンパーノウン定数 (2) |
ユーザー |
|
提出日時 | 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 |
ソースコード
#!/usr/bin/python2# -*- coding: utf-8 -*-# †from math import logfrom collections import dequedigits = [0,1,2,3,4,5,6,7,8,9]# 基数変換. 10進数の{num}を{base}進数にします。def int2base(num, base):assert base > 1if num == 0:return [digits[0]]v = []while num != 0:q, r = divmod(num, base)v.append(digits[r])num = qv.reverse()return v# 基数変換. {base}進数で表現された{s}を10進数にします。#base2int = lambda s, base: int(s, base)def base2int(v, base):if len(v) == 0:return 0num = 0for c in v:num *= basenum += digits[c]return num# B進 で v0 + v1def add(v0, v1, B):n0 = len(v0)n1 = len(v1)n = max(n0, n1) + 1v0 = [0] * (n - n0) + v0v1 = [0] * (n - n1) + v1v = deque([0] * n)carry = 0for i in reversed(xrange(1, n)):v[i] = carry + v0[i] + v1[i]if v[i] >= B:v[i] -= Bcarry = 1while 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) + v1v = deque(v0)for i in reversed(xrange(n0)):v[i] -= v1[i]if v[i] < 0:v[i-1] -= 1v[i] += Bwhile 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 Trueif n1 > n2:return Falsefor i in xrange(n1):if s[i] < t[i]:return Trueif s[i] > t[i]:return Falsereturn 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 resdef f(B, D):lo, hi = 0, 10**6 # lo: D番目が属する文字数while hi - lo > 1:md = (lo + hi) / 2rrr = leq(create(B, md), D)if rrr:lo = mdelse:hi = mdposB = create(B, lo)difB = sub(D, posB, B)dif10 = base2int(difB, B)if dif10 == 0:return 1z, r = divmod(dif10, lo)w = z + B**(lo-1)m = int(log(w, B)) + 1return (w / B**(m-1-r)) % BB = int(raw_input())D = map(int, raw_input())res = f(B, D)print res