Как ускорить работу скрипта?

Question

[pepl213]

Задача:
Бутылки
(Время: 1 сек. Память: 16 Мб Сложность: 48%)

Группа программистов собралась в понедельник и на все свои деньги купила «Sprite» в бутылках емкостью по 0.25 л., не забыв взять сдачу.

Во вторник они сдали пустую посуду, добавили оставшуюся сдачу и вновь купили столько таких же бутылок «Sprite», сколько могли.

Так они действовали до пятницы. В пятницу, сдав посуду и добавив сдачу с четверга, они смогли купить только одну бутылку напитка. При этом денег у них уже не осталось.

Требуется написать программу, определяющую минимальную сумму, которой располагали программисты в понедельник.
Входные данные

Входной файл INPUT.TXT состоит из единственной строки, содержащей два целых числа F (стоимость одной бутылки «Sprite») и P (стоимость одной пустой бутылки из под «Sprite»), разделенных пробелом.

Ограничения: 1 ≤ P < F ≤ 109, начальная сумма не превосходит 2×109.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число – минимальную сумму, которой располагали программисты в понедельник.

Пример:
7 3
Пт.7
Чт.11
Ср.19
Вт.39
Пн. 83

<br>
F,P = map(int,input().split()) #7 3<br><br>
def f(Q, deep):<br>
    if deep == 5:<br>
        return Q<br>
    for x in range(Q, 100*Q):<br>
        if x == Q+ (F-P)*(x//F):<br>
            break<br>
    return f(x,deep+1)<br>
print(f(F,1)) <br>

12 тест не проходит по времени (На Си тоже самое)
Как ускорить время выполнения скрипта.
Предыдущее кол-во денег можно посчитать по формуле x - (F-P)(x div F) = Q , где x - минимальное число, которое подходит для выполнения равенства. Q- кол-во денег в этот день.
В пятницу оно равно F.

Comments

[Сергей Соколов]

в исходной задаче ограничение чуть пошире: не до 109, а до 10⁹

Answer 1

[Сергей Соколов]

В начале у ребят только деньги. В конце 1 пустая бутылка и весь выпитый напиток без посуды.
Начальное кол-во денег минус P делится без остатка на (F - P)

Работающее решение на JavaScript

function f(F, P) {
  const D = F - P; // стоимость напитка без посуды

  // сколько останется денег если 1 раз купить, выпить и сдать?
  function drink(m) {
    const n = Math.floor(m / F);
    if (n <= 0) throw "Nope";
    return m - n * D;
  }
  
  for( let M = P + D * Math.ceil((F + 1) / D); M <= D * Math.floor(2 * 109 / D); M += D) {
    try {
      if (F === drink(drink(drink(drink(M))))) return M;
    } catch(e) {
      continue;
    }
  }
}

f(7, 3) // 83

spoiler

import math

F,P = map(int, input("Введите два целых через пробел:").split())


def bruteforce(F, P):
    D = F - P
    
    def drink(m):
        n = math.floor(m / F)
        if 0 == n:
            raise Exception()
        return m - n * D
	

    for M in range(P, int(1e9), D):
        try:
            rem = drink(drink(drink(drink(M))))
            if (F == rem):
                return M
        except Exception as E:
            pass
            
    return "Нет решения"

print(bruteforce(F, P))

Comments

[pepl213]

Т.е.?

[Сергей Соколов]

pepl213, можно проверять гипотезы, какова была начальная сумма, начиная от F + 1, увеличивая на F - P.
Проверка гипотезы сводится к просчёту цепочки дней в прямом порядке Пн → Пт. На каждом шаге считайте сколько денег осталось после трат на выпивку N * (F - P).
Для F = 7 и P = 3 стоимость жидкости 4, значит на диапазоне от 8 до 2 * 109 всего 52 шага. В каждом никаких циклов, поэтому всё проверится очень быстро. Тем более, остановимся на первом же найденном M, которое пройдёт проверку.

[Сергей Соколов]

Я ошибся. Начальная сумма без стоимости пустой бутылки делится на разницу без остатка!

[pepl213]

Сергей Соколов, ЛЯТЬ! СПАСИБО ОГРОМНОЕ. ПРОШЛО

[Сергей Соколов]

pepl213, есть кнопка «Отметить решением»

[Дмитрий]

pepl213, Можешь выложить скрипт, который прошёл? Интересно

[pepl213]

Дмитрий,

F,P = map(int,input().split())
  
def f(Q, deep):
    if deep == 5:
        return Q
    for x in range(Q, Q*Q, F-P):
        if x == Q+ (F-P)*(x//F):
            break
    return f(x,deep+1)
print(f(F,1))

[Дмитрий]

pepl213, т.е. только не хватало в range F-P и Q*Q, вместо 100*Q? Странно: всё равно ж перебор... Может, просто повезло в этот раз? Просто не вижу существенных изменений - а хотелось бы понять.

За одно попрошу объяснить, верхняя граница (100*Q и Q*Q) выбиралась условно? Просто как заведомо достаточная или есть какой-то смысл в переходе от 100-крат к квадрату?

[pepl213]

Дмитрий, я просто попытался сделать 99*Q - не прошло. Потом 100*Q, получилось, но не по времени. Эксперементальным путём. Со 100*Q работает на 15% быстрее работает