Оптимизация кода<<>>

Question

Оптимизируйте код ниже, чтобы при значениях n, k, a, b = 1000000000000, 1234, 5, 6; код выполнялся менее чем за секунду. Ссылка на задачу: https://codeforces.com/gym/104778/problem/E

n, k, a, b = map(int, input().split())

for i in range(n, 0, -1):
    counter = sum(1 for x in range(i, n) if str(x)[-1] in (str(a), str(b)))

    if counter == k:
        print(i)
        break
else:
    print(-1)

Answer 1

Вариант с циклом

n, k, *ab = map(int, input().split())
for i in range(n, -1, -1):
    if i % 10 in ab:
        k -= 1
        if k == 0:
            print(i)
            break
else:
    print(-1)

Вариант без цикла.
Сначала ищем ближайшие числа, оканчивающиеся на a и b. Поскольку 2 числа уже найдены, минусуем счетчик на 2. Дальше делим счетчик на 2. Если число нечетное, то в c2 попадает с1+1. Учитывая, что одна и та же цифра повторяется через 10 единиц, перемножаем c1 и с2 на 10 и отнимаем от найденных ранее ближайших чисел. При этом используем min и max, чтобы не отнять лишнего. Если x ушел в минус, то решения нет.

for test in "29 3 8 0", "20 5 4 7", "1000000000000 1234 5 6":
    n, k, *ab = map(int, test.split())
    pa, pb = (n - (n % 10 + 10 - d) % 10 for d in ab)
    c2 = k - 2 - (c1 := (k - 2) // 2)
    x = min(max(pa, pb) - c2 * 10, min(pa, pb) - c1 * 10)
    print(-1 if x < 0 else x)

18
-1
999999993835

Обновление. Оптимизировал расчет pa и pb. К последней цифре числа сразу добавляем 10, потом отнимаем искомую цифру. Для отсечения значений больше 9 забираем остаток от деления на 10. Отнимаем это от числа, получаем равное или ближайшее меньшее число, заканчивающееся на искомую цифру:

n - (n % 10 + 10 - d) % 10

Вариант от @MBo из комментариев лучше:

(x-d)//10*10+d

Answer 2

n, k, a, b = 1000000000000, 1234, 5, 6
# Помещаем критерии отбора именно в set, т.к. по set оператор in работает максимально быстро
last_num = {a, b}
# Формируем генератор перебора страниц с одновременной фильтрацией
selected_pages= (page_num for page_num in range(n, 0, -1) if (page_num % 10) in last_num)
# По списку страниц проходим только один раз и останавливаемся при достижении счетчиком требуемого значения
for i,num in enumerate(selected_pages, 1):
    if i == k:
        print(num)
        break
else:
    print(-1)

Answer 3

Доработанный вариант без цикла от @Алексей Р. Позволяет добавлять произвольное количество цифр, на которые может оканчиваться номер страницы (от 0 до 9).

test = "1000000000000 1234 5 6"
n, k, *last_digits = map(int, test.split())
ld = n % 10
# Формируем список с ближайшими числами, оканчивающиеся на цифры из списка last_digits
page_numbers = list()
for i in range(len(last_digits)):
    pn = n - ld + last_digits[i] - (int(ld < last_digits[i]) * 10)
    page_numbers.append(pn)
# Полученный список обязательно должен быть отсортирован в обратном порядке
page_numbers.sort(reverse=True)
len_pn = len(page_numbers)
# Вычисляем позицию числа, которое будет базисом для вычислений
idx = (k % len_pn) - 1
# Т.к. последующая последняя цифра повторяется через 10, вычисляем множитель с учетом уже вычисленных значений
multiplier: int = (k - 1)//len_pn
result = page_numbers[idx] - (multiplier * 10)
print('start page =', -1 if result <= 0 else result)

БЛОГ НА HUSL

Оптимизация кода<<>>

Ответы (3 шт):