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 | Python (3.4.3) |
Score | 500 |
Code Size | 696 Byte |
Status | AC |
Exec Time | 26 ms |
Memory | 3940 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 500 / 500 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01, sample_02, sample_03, sample_04 |
All | 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 | AC | 22 ms | 3572 KB |
hand_02 | AC | 22 ms | 3572 KB |
hand_03 | AC | 22 ms | 3572 KB |
hand_04 | AC | 22 ms | 3572 KB |
hand_05 | AC | 23 ms | 3572 KB |
max_01 | AC | 24 ms | 3684 KB |
max_02 | AC | 25 ms | 3812 KB |
max_03 | AC | 24 ms | 3684 KB |
max_04 | AC | 25 ms | 3812 KB |
max_05 | AC | 26 ms | 3812 KB |
random_01 | AC | 23 ms | 3572 KB |
random_02 | AC | 26 ms | 3812 KB |
random_03 | AC | 25 ms | 3808 KB |
random_04 | AC | 24 ms | 3684 KB |
random_05 | AC | 22 ms | 3572 KB |
random_06 | AC | 23 ms | 3572 KB |
random_07 | AC | 24 ms | 3684 KB |
random_08 | AC | 24 ms | 3684 KB |
sample_01 | AC | 22 ms | 3572 KB |
sample_02 | AC | 22 ms | 3572 KB |
sample_03 | AC | 22 ms | 3572 KB |
sample_04 | AC | 26 ms | 3940 KB |