結果

問題 No.319 happy b1rthday 2 me
ユーザー rpy3cpprpy3cpp
提出日時 2015-12-13 00:24:17
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 3,050 bytes
コンパイル時間 125 ms
コンパイル使用メモリ 10,840 KB
実行使用メモリ 8,364 KB
最終ジャッジ日時 2023-10-13 12:02:38
合計ジャッジ時間 2,090 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
8,288 KB
testcase_01 AC 16 ms
8,176 KB
testcase_02 AC 16 ms
8,240 KB
testcase_03 AC 17 ms
8,336 KB
testcase_04 AC 16 ms
8,364 KB
testcase_05 AC 16 ms
8,316 KB
testcase_06 AC 16 ms
8,336 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 16 ms
7,960 KB
testcase_10 AC 16 ms
8,120 KB
testcase_11 WA -
testcase_12 AC 16 ms
8,356 KB
testcase_13 AC 16 ms
8,248 KB
testcase_14 AC 16 ms
8,364 KB
testcase_15 AC 16 ms
8,244 KB
testcase_16 AC 16 ms
8,160 KB
testcase_17 WA -
testcase_18 AC 16 ms
8,160 KB
testcase_19 AC 17 ms
8,172 KB
testcase_20 AC 16 ms
8,172 KB
testcase_21 AC 16 ms
8,332 KB
testcase_22 AC 16 ms
8,248 KB
testcase_23 WA -
testcase_24 AC 16 ms
8,264 KB
testcase_25 AC 17 ms
8,228 KB
testcase_26 AC 16 ms
7,928 KB
testcase_27 WA -
testcase_28 AC 16 ms
8,328 KB
testcase_29 AC 16 ms
8,340 KB
testcase_30 AC 16 ms
8,192 KB
testcase_31 AC 16 ms
8,276 KB
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

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