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

@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 конфеты.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

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

@Gdez 8849 / 4501 / 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