Минимальное количество конфет, которое мог подарить самый первый дедушка

@Nagibator2771 · Регистрация: 15.10.2020

Студворк — интернет-сервис помощи студентам

Условие:
Ванечка — хороший мальчик. Но он единственный ребенок в большой семье. И когда приходят в гости родственники, они стараются угостить Ванечку конфеткой.
Дедушка пришел самым первым и подарил X конфет. Потом пришла бабушка, и ей хочется, чтобы Ванечка любил ее чуть больше, чем дедушку, она дарит ему X + 1 конфету.
Приходит тётя и дарит X + 2 конфеты, а дядя, разумеется, X + 3. И так продолжается дальше.
Когда в конце концов Ванечка остается один перед кучей конфет, он уже не помнит не только, сколько было родственников с конфетами, но и сколько подарил самый первый дедушка.
Напишите программу, которая по введённому количеству конфет в куче определяет минимальное количество конфет, которое мог подарить самый первый дедушка.

Я вроде написал, и вроде все значения код выдает правильно. Но при больших значениях работает медленно, чуть больше секунды. Можно как-то оптимизировать его, чтобы он делал тоже самое но с меньшим временем? Или вообще плохо написано и надо переделывать?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
n = int(input())
d = 0
z = 1
col = 0
while True:
    d += z
    if d > n:
        d -= z
        break
    z += 1
    col += 1
x = (n - d) / (col + 1)
if x % 2 != 0 or x % 2 != 1 or x == 0:
    first = True
    while True:
        if first is not True:
            col -= 1
        else:
            first = False
        d -= col
        x = (n - d) / col
        if (x % 2 == 0 or x % 2 == 1) and x != 0:
            print(int(x))
            break
else:
    print(x)

@eaa · 29.10.2020, 12:28

а формула сумма арифметической прогрессии, тут не подходит?

@Gdez · 29.10.2020, 15:03

Nagibator2771, https://www.cyberforum.ru/pyth... 12393.html

@Nagibator2771 · 29.10.2020, 18:20 **[ТС]**

Не подумал, спасибо

@Avocatocat · 09.11.2023, 07:09

Python
1
2
3
4
5
6
7
8
n = int(input())
max_guests = int((2 * n) ** 0.5)  # Максимальное количество гостей, при котором дедушка подарил >= 1 конфеты.
for i in range(max_guests, 0, -1):  # i - это возможное количество гостей.
    if (2 * n - i ** 2 + i) % (2 * i) == 0:  # По формуле, если бы вместо "%" стоял "//", то мы нашли бы возможного а1
        # члена арифметической прогрессии, но если i будет неверным, то a1 получится дробным, поэтому мы ищем первое
        # верное i с нулевым остатком.
        print((2 * n - i ** 2 + i) // (2 * i))  # Выводим количество конфет, подаренных первым дедушкой.
        break

Формула суммы арифметической прогрессии (n здесь - это не n в программе!):
S = ( ( a(1) + a(n) ) * n) / 2

Разложим an-ый член програссии:
S = ( (2a(1) + n - 1) * n) / 2

a(1) - первый член прогрессии (количество конфет дедушки). После преобразований:
a(1) = (2 * S - n ** 2 - n) / (2 * n)

Из последней формулы: (2 * s) ** 0.5 <= n, иначе дедушка принёс меньше 1 конфеты.

Новые блоги и статьи Все статьи Все блоги /
Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.10.2020, 12:28
	а формула сумма арифметической прогрессии, тут не подходит? 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	29.10.2020, 15:03
	Nagibator2771, https://www.cyberforum.ru/pyth... 12393.html 1

@Nagibator2771 2 / 2 / 0 Регистрация: 15.10.2020 Сообщений: 12
	29.10.2020, 18:20 [ТС]
	Не подумал, спасибо 0