結果

問題 No.319 happy b1rthday 2 me
コンテスト
ユーザー rpy3cpp
提出日時 2015-12-13 00:24:17
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,050 bytes
コンパイル時間 72 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-09-15 08:57:28
合計ジャッジ時間 2,032 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve(A, B):
    return count12(B, 12) - count12(A - 1, 12)


def count12(N, target):
    return count12within(N, target) + count12between(N, target)
    

def count12within(N, target):
    '''0 から　N までの各整数の中に、target (2桁の数値) が何個含まれているかを返す。
    0 から　N までに、7が何個あるか？という問題の解法を、100進数に適用。
    ただし、開始位置をずらして2回計算している。
    '''
    count1 = count12within_core(N, target, 1, 1)
    count2 = count12within_core(N//10, target, 10, (N % 10) + 1)
    return count1 + count2

def count12within_core(N, target, tens, tail):
    unit = 10 ** len(str(target))
    count = 0
    while N:
        N, R = divmod(N, unit)
        if R > target:
            count += tens
        elif R == target:
            count += tail
        count += N * tens
        tail += R * tens
        tens *= unit
    return count

def count12between(N, target):
    '''0 から　N までの整数をつなげた数値のうち、２つの数値をまたいで12が何個含まれているかを返す。
    当該の２つの数値を m, m+1　とすると、m の末尾は1で、m+1 の先頭は2となる。
    このようなケースは、m が 1桁ならば、1, 2 のみ。
    m が 2桁ならば、21, 22 のみ。
    m が 3桁ならば、2x1, 2x2 が該当し、x=0..9 までの10個があり得る。
    m が 4桁ならば、2xy1, 2xy2 が該当し、xy = 00..99 までの100個があり得る。
    N が k 桁の場合は、(k-1)桁までの該当数の和 = 1 + sum(10**(i-1) for i in range(1, k))
    および、
    k桁目の数値が　1ならば、 + 0
    k桁目の数値が　2ならば、 (N % (10**k))//10 + (1 if (N % 10) >= 2 else 0)
    k桁目の数値が　3以上ならば、10**(k-2)
    を足した数となる。
    '''
    if N < 2:
        return 0
    if N < 22:
        return 1
    if N < 100:
        return 2
    k = len(str(N))
    head, tail = divmod(N, 10**(k - 1))
    count = 1 + sum(10**i for i in range(k - 2))    
    if head == 1:
        return count
    elif head == 2:
        count += tail // 10
        if (tail % 10) >= 2:
            count += 1
        return count
    else:
        return count + 10**(k - 2)


A, B = map(int, input().split())
print(solve(A, B))

#def count12naive(N, target):
#    lst = []
#    count = 0
#    target_str = str(target)
#    for i in range(N + 1):
#        count += str(i).count(target_str)
#        lst.append(count)
#    return lst
#
#def count12between_naive(N, target):
#    a, b = divmod(target, 10)
#    bstr = str(b)
#    prev = 0
#    count = 0
#    lst = [0]
#    for n in range(1, N):
#        if (prev == a) and (str(n)[0] == bstr):
#            count += 1
#        prev = n % 10
#        lst.append(count)
#    return lst
#
#
#N = 1000
#lst = count12between_naive(N, 12)
#for i, b in enumerate(lst):
#    a = count12between(i, 12)
#    if a != b:
#        print(i, a, b)
#    if i % 100 == 0:
#        print(i)
0