DjangoBB LoFi version

Начало » Python для новичков » Задачка с олимпиады

polsovatel

Янв. 28, 2018 06:08:43

Добрый день, дорогие друзья!
Помогите пожалуйста решить такую задачку:

Рассмотрим таблицу из n строк и n столбцов. Известно, что в клетке, образованной пересечением i-й строки и j-го столбца, записано число i × j. Строки и столбцы нумеруются с единицы.

Дано целое положительное число x. Требуется посчитать количество клеток таблицы, в которых находится число x.

Входные данные
В единственной строке находятся числа n и x (1 ≤ n ≤ 105, 1 ≤ x ≤ 109) — размер таблицы и число, которое мы ищем в таблице.

Выходные данные
Выведите единственное число: количество раз, которое число x встречается в таблице.

Я решил данную задачу(написал 2 цикла for, записал всю таблицу в список и дальше нашел количество числа x в списке), но мое решение не оптимально, выполняется очень медленно. Помогите пожалуйста придумать, как сделать алгоритм быстрее.

Заранее спасибо!

polsovatel

Янв. 28, 2018 06:29:17

Задачку решил. Кому интересно вот оптимизированный алгоритм:

def code(n, x):
count = 0

if x == 1:
return 1

for i in range(1, n + 1):
if i == 1 and n >= x:
count += 1
elif x % i == 0 and i != 1 and x <= n * i:
count += 1
return count

st = input()
n, x = st.split()
n, x = int(n), int(x)
ch = code(n, x)
print(ch)

scidam

Янв. 28, 2018 06:38:59

Учитывая, что у вас точно заданы границы изменения значений (и они не большие), можно воспользоваться
самым эффективным, однако неинтересным и скучным приемом для решения этой задачи – посчитать заранее.

 def get_x_count(n, x):
    assert n in range(1, 106), "n should be an integer from [1, 105]"
    assert x  in range(1, 110), "x should be an integer from [1, 109]"
    precomputed = {1: 1, 2: 2, 3: 2, 4: 3, 5: 2, 6: 4, 7: 2, 8: 4, 9: 3, 10: 4, 11: 2, 12: 6, 13: 2, 14: 4, 15: 4, 16: 5, 17: 2, 18: 6, 19: 2, 20: 6, 21: 4, 22: 4, 23: 2, 24: 8, 25: 3, 26: 4, 27: 4, 28: 6, 29: 2, 30: 8, 31: 2, 32: 6, 33: 4, 34: 4, 35: 4, 36: 9, 37: 2, 38: 4, 39: 4, 40: 8, 41: 2, 42: 8, 43: 2, 44: 6, 45: 6, 46: 4, 47: 2, 48: 10, 49: 3, 50: 6, 51: 4, 52: 6, 53: 2, 54: 8, 55: 4, 56: 8, 57: 4, 58: 4, 59: 2, 60: 12, 61: 2, 62: 4, 63: 6, 64: 7, 65: 4, 66: 8, 67: 2, 68: 6, 69: 4, 70: 8, 71: 2, 72: 12, 73: 2, 74: 4, 75: 6, 76: 6, 77: 4, 78: 8, 79: 2, 80: 10, 81: 5, 82: 4, 83: 2, 84: 12, 85: 4, 86: 4, 87: 4, 88: 8, 89: 2, 90: 12, 91: 4, 92: 6, 93: 4, 94: 4, 95: 4, 96: 12, 97: 2, 98: 6, 99: 6, 100: 9, 101: 2, 102: 8, 103: 2, 104: 8, 105: 8, 106: 2, 107: 0, 108: 10, 109: 0}
    return precomputed[x]

doza_and

Янв. 28, 2018 09:45:33

scidam
самым эффективным

Ваш алгоритм довольно быстрый но я наверное что-то не понял. Зададим n=1,x=3, что не противоречит условию. У вас ответ будет 2 но такая таблица содержит одно число 1 и оно не совпадает с 3 похоже ответ должен быть 0.

Кроме того время построения словаря тоже наверное надо учитывать.

doza_and

Янв. 28, 2018 10:24:11

polsovatel
Задачку решил. Кому интересно вот оптимизированный алгоритм:

Код желательно оборачивать в теги code см кнопочку <>

Думаю вы сможете улучшить алгоритм если учтете симметрию задачи.
Если вы найдете остаток от деления то сможете прибавлять по 2 и сразу определить верхнюю границу поиска что сократит перебор более чем в 2 раза.

А граница 109 я думаю призвана вам напомнить что в школе обычно учат таблицу простых чисел до 109 и предполагается что вы ее знаете наизусть.

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109
разложение дорогая операция, но потом точки легко получить комбинируя множители. Может это будет и быстрее.

scidam

Янв. 29, 2018 02:45:33

doza_and
Зададим n=1,x=3, что не противоречит условию

Это ж надо, я так однобоко задачу воспринял… Поскольку я так неправильно воспринял задачу, решил ее порешать
и сравнить варианты по быстродействию:

 from math import sqrt 
import random
import numpy as np
import timeit
def get_x_count(n, x):
    if x > n * n: return 0
    if x < 1: return 0
    if x == 1: return 1
    count = 0
    sqx2 = int(sqrt(x))
    sq_flag = False
    for j in range(2, sqx2 + 1):
        if x % j == 0 and x // j <= n:
            count += 1
            if x // j == j:
                sq_flag = True
    if x <= n:
        count += 1
    return count * 2 - sq_flag
def get_x_count_np(n, x):
    _ = np.meshgrid(np.arange(1, n+1), np.arange(1, n+1)) # Expensive computations, 
    return np.sum(_[0] * _[1] == x) 
def code(n, x):
    count = 0
    if x == 1:
        return 1
    for i in range(1, n + 1):
        if i == 1 and n >= x:
            count += 1
        elif x % i == 0 and i != 1 and x <= n * i:
            count += 1
    return count
def code_modified(n, x):
    if x > n * n: return 0
    if x < 1: return 0
    if x == 1: return 1
    count = 0
    for i in range(1, n + 1):
        if i == 1 and n >= x:
            count += 1
        elif x % i == 0 and i != 1 and x <= n * i:
            count += 1
    return count
def test(func):
    n = random.randint(1, 105)
    x = random.randint(1, 109)
    func(n, x)
    
print("Original code: ", timeit.timeit("test(code)", setup="from __main__ import test, code;"))
print("Silly numpy version: ", timeit.timeit("test(get_x_count_np)", setup="from __main__ import test, get_x_count_np;"))
print("Sq2 version: ", timeit.timeit("test(get_x_count)", setup="from __main__ import test, get_x_count;"))
print("Slightly modified version: ", timeit.timeit("test(code_modified)", setup="from __main__ import test, code_modified;"))

Получилось следующее:

 Original code:  12.706644643039908
Silly numpy version:  89.43882536696037
Sq2 version:  7.127855834958609
Slightly modified version:  12.50681558700744

Ну и конечно, можно было бы создать версию на основе вычисленного заранее словаря, только
теперь он был бы большим, чтобы доступ к результату был в виде

 result[n][x]

Rodegast

Янв. 29, 2018 09:56:05

> Дано целое положительное число x. Требуется посчитать количество клеток таблицы, в которых находится число x.

ИХМО. Нужно получить множество факторизаций числа x и посчитать их сочетания.