Олимпиада по информатике 2025-2026 муниципальный этап Магическая семёрка

Олимпиада по информатике 2025-2026 муниципальный этап Магическая семёрка

olimp-inf-tatmunits-2025-B

Идея:
Пусть f(x) — количество «магических» чисел ≤ x.
Число магическое, если:

делится на 7
или оканчивается цифрой 7

Посчитаем f(x) по включению–исключению:

cnt_div7 = x // 7 — делятся на 7
cnt_end7 — числа, оканчивающиеся на 7: 7, 17, 27, …
если x >= 7, то cnt_end7 = (x - 7) // 10 + 1, иначе 0
cnt_both — и делятся на 7, и оканчиваются на 7: 7, 77, 147, 217, …
это числа вида 7 + 70*k, значит, если x >= 7, то
cnt_both = (x - 7) // 70 + 1, иначе 0

Тогда:

f(x) = cnt_div7 + cnt_end7 - cnt_both

1	f(x) = cnt_div7 + cnt_end7 - cnt_both

Дальше бинарным поиском найдём минимальное x, для которого f(x) >= k.

def count_magic(x: int) -> int:
    """Считает количество магических чисел <= x."""
    if x <= 0:
        return 0

    cnt_div7 = x // 7

    if x >= 7:
        cnt_end7 = (x - 7) // 10 + 1
        cnt_both = (x - 7) // 70 + 1
    else:
        cnt_end7 = 0
        cnt_both = 0

    return cnt_div7 + cnt_end7 - cnt_both


def kth_magic(k: int) -> int:
    """Возвращает k-е магическое число."""
    left = 1
    right = 7 * k  # верхняя граница: точно хватит, т.к. каждое 7-е число магическое

    while left < right:
        mid = (left + right) // 2
        if count_magic(mid) >= k:
            right = mid
        else:
            left = mid + 1

    return left


def main():
    import sys
    k = int(sys.stdin.readline())
    print(kth_magic(k))


if __name__ == "__main__":
    main()

def count_magic(x: int) -> int:

"""Считает количество магических чисел <= x."""

if x <= 0:

return 0

cnt_div7 = x // 7

if x >= 7:

cnt_end7 = (x - 7) // 10 + 1

cnt_both = (x - 7) // 70 + 1

else:

cnt_end7 = 0

cnt_both = 0

return cnt_div7 + cnt_end7 - cnt_both

def kth_magic(k: int) -> int:

"""Возвращает k-е магическое число."""

left = 1

right = 7 * k # верхняя граница: точно хватит, т.к. каждое 7-е число магическое

while left < right:

mid = (left + right) // 2

if count_magic(mid) >= k:

right = mid

else:

left = mid + 1

return left

def main():

import sys

k = int(sys.stdin.readline())

print(kth_magic(k))

if __name__ == "__main__":

main()