Last active
October 27, 2016 18:01
-
-
Save meredian/19eeb104fc3d9af5df74874fabdbfffd to your computer and use it in GitHub Desktop.
Решение второй задачи по информатике отборочного тура http://nti-contest.ru/wp-content/uploads/7-%D0%91%D0%94.pdf
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Константа, очень большое значение, | |
# будет намекать нам, что мы пока не знаем, | |
# как на самом деле представить какое-то число | |
# в виде оптимальной суммы | |
NONE = 1000000000 | |
def solve(n, x): | |
# Создаём пустой массив чисел из X + 1 ячеек, | |
# так что storage[i] - сумма степеней для i | |
storage = [NONE] * (x + 1) | |
fill_powers(storage, n) | |
fill_multiplications(storage) | |
fill_sums(storage) | |
return storage[x] | |
# Заполняем в массив все известные нам целочисленные корни | |
def fill_powers(storage, n): | |
set_target(storage, n, 1) | |
pow = 2 | |
while True: | |
sqrt = int_sqrt(n, pow); | |
set_target(storage, sqrt, pow); | |
pow += 1 | |
if (sqrt == 1): | |
break | |
# Функция вычисляет конкретный целочисленный корень степени pow из числа n | |
def int_sqrt(n, pow): | |
for y in range(1, n + 1): | |
if (y ** pow) <= n < (y + 1) ** pow: | |
return y; | |
# Из уже заполненных значений находим все возможные произведения | |
# с оптимальным количеством корней | |
def fill_multiplications(storage): | |
for i in range(2, len(storage)): | |
for j in range(2, i): | |
if (i % j == 0): | |
set_target(storage, i, storage[j] + storage[i / j]) | |
# Вычисляем все доступные нам оптимальные суммы | |
# комбинируя уже найденные числа | |
def fill_sums(storage): | |
for i in range(2, len(storage)): | |
for j in range(1, i): | |
set_target(storage, i, storage[j] + storage[i - j]) | |
# очень удобный вспомогательный метод - обновляет значение | |
# в массиве, если оно лучше старого | |
def set_target(storage, index, value): | |
if (index < len(storage) and storage[index] > value): | |
storage[index] = value | |
# Тут опущена работа со строками, это еще одна строчка нужна |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment