1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| '''
Author: NEFU AB-IN
Date: 2024-08-21 13:14:23
FilePath: \LeetCode\3007\3007.py
LastEditTime: 2024-08-21 15:39:04
'''
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)
setrecursionlimit(int(2e9))
class Arr:
array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
graph = staticmethod(lambda size=N: [[] for _ in range(size)])
class Math:
max = staticmethod(lambda a, b: a if a > b else b)
min = staticmethod(lambda a, b: a if a < b else b)
class IO:
input = staticmethod(lambda: stdin.readline().strip())
read = staticmethod(lambda: map(int, IO.input().split()))
read_list = staticmethod(lambda: list(IO.read()))
read_mixed = staticmethod(lambda *types: [t(v) for t, v in zip(types, IO.input().split())])
class Std:
pass
class Solution:
def findMaximumNumber(self, k: int, x: int) -> int:
def dfs(n: int, is_limit: bool, is_num: bool):
n = bin(n)[2:]
@lru_cache(None)
def _dfs(i: int, num: int, is_limit: bool, is_num: bool):
if i == len(n):
return num if is_num else 0
res = 0
if not is_num:
res = _dfs(i + 1, num, False, False)
up = int(n[i]) if is_limit else 1
down = 0 if is_num else 1
for d in range(down, up + 1):
w = 0
if (len(n) - i) % x == 0:
w = d
res += _dfs(i + 1, num + w, is_limit and up == d, True)
return res
res = _dfs(0, 0, is_limit, is_num)
_dfs.cache_clear()
return res
l, r = 0, k << x
while l < r:
mid = l + r + 1 >> 1
if dfs(mid, True, False) <= k:
l = mid
else:
r = mid - 1
return r
|