Статья Автор: Лебедев Дмитрий Алексеевич

Задания от учеников - переделка в 13

Петя заснул за чтение пьесы "Вишневый сад" и ему приснился страшный сон.

Он - студент Петя и хочет спасти вишневый сад, продав урожай вишни.
Пете приснилось, что продавать вишню можно следующим способом:

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

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

Помогите Пете найти стоимость сада, если урожай состоял из 1_000_000_000 вишен.

from time import process_time as prt
def ff(n) :
    if (n - sf[0]) * (n - sf[1]) > 0 : return 0
    if n in dp : return dp[n]
    a = [n//i for i in range(2, int(n**0.5)+1) if n % i == 0]
    if len(a) == 0 : a = [n-2, n-3, n-5, n-7]
    dp[n] = sum([ff(i) for i in a])
    return dp[n]
tstart = prt()
sf= [9503, 0]
dp = {sf[1]: 1}
ff(sf[0])
print(dp[sf[0]])
print(f'time = {prt() - tstart}')

Выпускник Петя заснул за чтением пьесы А. П. Чехова «Вишнёвый сад» перед экзаменом. Ему приснился кошмар: он сам стал «вечным студентом» Петей Трофимовым, который пытается спасти сад от вырубки. Урожай вишни лежит на кухонном столе, и Петя уговаривает купца Лопахина купить этот урожай.
Лопахин, размышляя о будущем дроблении сада на дачные участки, соглашается, но определяет цену урожая в число копеек, равное количеству вариантов, которыми можно продать этот урожай частями по следующим правилам:

Если текущее количество вишен N — составное число, Петя может продать часть ягод, оставив на столе K вишен. Лопахин разрешает выбрать в качестве K только собственный «больший делитель» числа N (такой делитель, что 1 < K < N и K² ≥ N).
Если текущее количество вишен N — простое число, Петя от тревоги должен сам съесть две, три, пять или семь вишен.
Продажа успешно завершается, как только на столе остаётся ровно 0 вишен.

Петя с Варей и Фирсом смогли сосчитать количество вишен, но здесь Петя проснулся в «холодном поту». Помогите Пете определить цену урожая в копейках, если урожай состоял из 10⁹ вишен. В ответе укажите только число.

Задание 13 (Высокий уровень, авторская задача на отрезок и сумму)

Выпускнику Ивану перед экзаменом по литературе приснился удивительный сон: он сам превратился в «ревизора» Ивана Александровича Хлестакова и очутился в доме городничего города N. Чиновники города один за другим заходят к нему и покорно вручают взятки. Хлестаков вместе со своим слугой Осипом решает распределить каждую полученную сумму по следующим правилам:

Если текущая сумма взятки N рублей — составное число, Хлестаков может отложить часть денег на игру в карты, оставив в общем кошельке K рублей. Из осторожности он разрешает выбрать в качестве K только собственный «больший делитель» числа N (такой делитель, что 1 < K < N и K² ≥ N).
Если текущая сумма взятки N рублей — простое число, Осип из «уважения к барину» сразу забирает из кошелька на дорожные расходы две, три, пять или семь банкнот номиналом в один рубль.
Распределение суммы успешно завершается, как только в кошельке остаётся ровно 0 рублей.

Перед самым пробуждением Иван вспомнил, что все полученные Хлестаковым взятки распределялись абсолютно одинаковым числом способов, а их значения были не меньше 1000, но и не больше 2000 рублей.

Какая наибольшая суммарная величина всех этих взяток могла быть получена Хлестаковым при таком условии? В ответе укажите только число.

Ответ к задаче: 11681

Печать