Submission #9991364


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import lru_cache

N, K = map(int,read().split())

@lru_cache(None)
def F(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
    assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    q,r = divmod(N,10)
    ret = 0
    if K >= 1:
        # 1の位が nonzero
        ret += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    # 1の位が zero
    ret += F(q, K)
    return ret

# F(100, 1), F(25, 2), F(314159, 2)

print(F(N, K))

Submission Info

Submission Time
Task E - Almost Everywhere Zero
User maspy
Language Python3 (3.4.3)
Score 500
Code Size 696 Byte
Status
Exec Time 26 ms
Memory 3940 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01, sample_02, sample_03, sample_04
All 500 / 500 hand_01, hand_02, hand_03, hand_04, hand_05, max_01, max_02, max_03, max_04, max_05, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
hand_01 22 ms 3572 KB
hand_02 22 ms 3572 KB
hand_03 22 ms 3572 KB
hand_04 22 ms 3572 KB
hand_05 23 ms 3572 KB
max_01 24 ms 3684 KB
max_02 25 ms 3812 KB
max_03 24 ms 3684 KB
max_04 25 ms 3812 KB
max_05 26 ms 3812 KB
random_01 23 ms 3572 KB
random_02 26 ms 3812 KB
random_03 25 ms 3808 KB
random_04 24 ms 3684 KB
random_05 22 ms 3572 KB
random_06 23 ms 3572 KB
random_07 24 ms 3684 KB
random_08 24 ms 3684 KB
sample_01 22 ms 3572 KB
sample_02 22 ms 3572 KB
sample_03 22 ms 3572 KB
sample_04 26 ms 3940 KB