Как сделать быстрее код Python
Столкнулся с таком задачей пользователь вводит k число которое обозначает номер магического числа в последовательности. Магическим называется число сумма цифр которого равна 10. A. Магическое число Ограничение времени 0.1 секунд Ограничение памяти 5.0 Мб
Будем называть положительное целое число «магическим», если сумма его цифр равна 10. Вам дано целое число k, найдите k-ое по величине «магическое» целое число.
Формат ввода Пользователь вводит целое число k ( 1 ≤ k ≤ 10000 1≤k≤10000).
Формат вывода Выведите k-ое по величине «магическое» число.
Пример 1 Ввод Вывод 1 19 Пример 2 Ввод Вывод 2 28 Пример 3 Ввод Вывод 3 37
Не знаю как ускорить еще свой код не поппадаю в тайм
k = int(input())
count = 0
number = 18
while count != k:
tmp = str(number)
suma = 0
for i in tmp:
t = int(i)
suma += t
if suma == 10:
count += 1
number += 1
else:
number += 1
print(number-1)
Подскажите пожалуйста что можно сделать
Ответы (5 шт):
итак - проверяю на k = 10000, исходный алгоритм автора - 12сек
вариант 1 [10сек] (используем стандартные функции работы со списками и строками):
count = 0
number = 18
while count != k:
s = sum(map(int, str(number)))
if s == 10:
count += 1
number += 1
print(number-1)
вариант 2 [6 сек] (работа с цифрами числа, а не со строкой):
count = 0
number = 18
while count != k:
s = 0
tmp = number
while tmp != 0:
s += tmp % 10
tmp //= 10
if s == 10:
count += 1
number += 1
print(number-1)
вариант 3 [3.8 сек] (вариант 2, но отсекаем вычисление суммы, если она стала выше 10):
count = 0
number = 18
while count != k:
s = 0
tmp = number
while tmp != 0:
s += tmp % 10
tmp //= 10
if s > 10:
break
if s == 10:
count += 1
number += 1
print(number-1)
вариант 3.1 [3.45 сек] (вариант 3, но не делаем лишнюю операцию деления когда цикл вычисления цифр прерывается):
count = 0
number = 18
while count != k:
s = 0
tmp = number
while tmp != 0:
s += tmp % 10
if s > 10:
break
tmp //= 10
if s == 10:
count += 1
number += 1
print(number-1)
вариант 4 [3.1 сек] (экономим на спичках - проверку на условие выхода из цикла делаем только когда это условие надо проверять, а не всегда):
count = 0
number = 18
while True:
s = 0
tmp = number
while tmp != 0:
s += tmp % 10
if s > 10:
break
tmp //= 10
if s == 10:
count += 1
if count == k:
print(number)
return
number += 1
вариант 5 [0.5сек]:
логика чуть посложнее - если сумма цифр больше 10, то все числа с последней цифрой до следующего 0 можно не рассматривать, потому что сумма будет только расти
например если у xxxx4 сумма 11, то числа xxxx5, xxxx6, xxxx7, xxxx8, xxxx9 можно уже не рассматривать и переходить к числу xxxy0
count = 0
number = 18
while True:
s = 0
tmp = number
while tmp != 0:
s += tmp % 10
if s > 10:
break
tmp //= 10
if s > 10:
number = (number // 10) * 10 + 10
else:
if s == 10:
count += 1
if count == k:
print(number)
return
number += 1
придумал еще один алгоритм (его надо доработать - сейчас он выдает чуть другой результат, но принцип правильный), скорость работы 0.04 сек (для k = 10000)
основной смысл:
получаем все возможные комбинации цифр 1-9, которые в сумме дают 10
начинаем формировать все возможные комбинации этих цифр с нулями, увеличивая кол-во нулей
из цифр собираем числа и заносим их в список (вот тут и надо допилить алгоритм, чтобы только уникальные числа добавлять в список)
когда в списке k значений - забираем самое большое
код:
# получить все возможные варианты цифр
def func(value, digits, res):
if value <= 0:
if value == 0:
res.append(digits)
else:
for i in range(digits[-1] if digits else 1, 10):
func(value - i, digits + [i], res)
variants = []
func(10, [], variants)
# собрать все возможные комбинации с 0 найденных вариантов цифр
numbers = []
size = 2
while True:
# для заданного кол-ва цифр в числе рассмотреть все возможные варианты цифр с суммой 10
for variant in variants:
# вычислить кол-во нулей в числе
zero_count = size - len(variant)
if zero_count < 0:
continue
# получить все возможные комбинации цифр
nums = set(itertools.permutations(variant + [0] * zero_count))
for num in nums:
# рассматривать комбинации не начинающиеся с 0
if num[0] != 0:
# сформировать из цифр число
value = 0
for digit in num:
value = value * 10 + digit
# добавить число в список найденных магических чисел
numbers.append(value)
if len(numbers) > k:
print(sorted(numbers)[k - 1])
return
size += 1
для k = 10000 алгоритм работает 0,04 сек и находит 61111000, хотя правильный ответ 10800100 - надо подумать почему
Нашел проблему - не рассмариваются все числа (не успевают) - если сделать так:
вместо:
if len(numbers) > k:
надо
if len(numbers) > 2 * k:
то все работает!
вариант 2:
Вариант даёт ГАРАНТИРОВАННЫЙ РЕЗУЛЬТАТ, но поэтому работает помедленнее (0,15 сек)
# получить все возможные варианты цифр
def func(value, digits, res):
if value == 0:
res.append(digits)
else:
for i in range(digits[-1] if digits else 1, 10):
if value >= i:
func(value - i, digits + [i], res)
variants = []
func(10, [], variants)
# собрать все возможные комбинации с 0 найденных вариантов цифр
count = 0
size = 2
while True:
# для заданного кол-ва цифр в числе рассмотреть все возможные варианты цифр с суммой 10
nums = []
for variant in variants:
# вычислить кол-во нулей в числе
zero_count = size - len(variant)
if zero_count < 0:
continue
# получить все возможные комбинации цифр
for num in set(itertools.permutations(variant + [0] * zero_count)):
# рассматривать комбинации не начинающиеся с 0
if num[0] != 0:
# сформировать из цифр число
value = 0
for digit in num:
value = value * 10 + digit
nums.append(value)
# если искомое число присутствует в найденных числах - найти его
if len(nums) + count >= k:
print(sorted(nums)[k - count - 1])
return
# увеличить размер искомых чисел
count += len(nums)
size += 1
Zhinar вот что получилось меньше 0.1 секунды алгоритмы просто ушли гулять
def checking(n: int) -> bool:
r = 0
while n:
r, n = r + n % 10, n // 10
if r > 10:
break
return True if (r == 10) else False
magic_number = int(input())
if magic_number >= 9212:
count = 9212
i = 10200007
elif magic_number >= 7996:
count = 7996
i = 9000001
elif magic_number >= 7975:
count = 7975
i = 8000002
elif magic_number >= 7919:
count = 7919
i = 7000003
elif magic_number >= 7793:
count = 7793
i = 6000004
elif magic_number >= 7541:
count = 7541
i = 5000005
elif magic_number >= 7079:
count = 7079
i = 4000006
elif magic_number >= 6287:
count = 6287
i = 3000007
elif magic_number >= 5000:
count = 5000
i = 2000008
elif magic_number >= 4705:
count = 4705
i = 1322020
elif magic_number >= 3000:
count = 3000
i = 1000027
elif magic_number >= 2747:
count = 2747
i = 500005
elif magic_number >= 2000:
count = 2000
i = 220033
else:
count = 1
i = 19
while True:
summ = 0
if count == magic_number:
print(str(i))
break
i = i + 9
if checking(i):
count += 1
Для серьезных значений k перебор не подойдёт, нужен алгоритм, генерирующий нужное число.
Используем метод stars and bars (wiki). У нас имеется 10 единиц, обозначаемых звёздочками. Между ними мы можем ставить m перегородок (bars). Эти перегородки могут находиться в любом из 9 внутренних промежутков между звездочками, а также справа.
* * * * * * * * * *
| || |
Единственное ограничение - все m перегородок не могут быть одновременно справа. Что же означает какое либо расположение? Это m+1-значное десятичное число. Чтобы его получить, просто считаем количество звездочек между перегородками. Например, выше изображено пятизначное число 23050. Ограничение означает, что у нас нет цифры `десять'
Сколько существует нужных нам m-значных чисел? По ссылке выше - число k-кортежей неотрицательных целых чисел, сумма которых равна n, и отнимем один ненужный нам случай, когда все перегородки справа:
F(m) = С(9+m-1, m-1) - 1
(C(n,k) - формула из комбинаторики для количества сочетаний). Таким образом, есть 9 двузначных, 54 трёхзначных, 219 четырехзначных, 714 пятизначных чисел и так далее.
Используя данную формулу, мы можем посчитать 9+54+219... пока сумма не превысит k, т.е. быстро определим, сколько цифр в искомом числе. Далее можно генерировать нужную комбинацию через сочетания, и перевести её в число.
А вот и код:
def cnk(n, k): # math.comb для Python 3.8+
k = min(k, n - k)
if k <= 0:
return 1 if k == 0 else 0
res = 1
for i in range(k):
res = res * (n - i) // (i + 1)
return res
def num2comb(n, k, m): #получение сочетания по его номеру в лекс. порядке
res = []
next = 1
while k > 0:
cn = cnk(n - 1, k - 1)
if m < cn:
res.append(next)
k -= 1
else:
m -= cn
n -= 1
next += 1
return res
def fun(k):
s = 0
m = 1
while s < k:
m += 1
last = s
s += cnk(8 + m, m - 1) - 1
kk = k - last #порядковый номер среди m-значных чисел
comb = num2comb(8 + m, m - 1, kk - 1) + [9 + m]
v = comb[0]
for i in range(len(comb) - 1):
v = v * 10 + comb[i + 1] - comb[i] - 1
return v
print(fun(10000))
>>> 10800100
Время логарифмическое от k. Для k=10000 и мерить нечего, микросекунды.
Чтобы получить заметное время работы, примерно одну секунду, понадобится k=100000000000000000000000000000000000000000, результат сюда не поместится
Есть такой вариант:
def A051885(n):
return ((n % 9) + 1) * 10 ** (n // 9) - 1
def A228915(n):
p = r = 0
while True:
d = n % 10
if d < 9 and r:
return (n + 1) * 10**p + A051885(r - 1)
n //= 10
r += d
p += 1
def A052224(N=19):
"""Return a generator of the sequence of all integers >= N with the same
digit sum as N."""
while True:
yield N
N = A228915(N)
k = int(input())
for i, _ in zip(A052224(19), range(k)):
pass
print(i)