Найдите наибольший возможный объем прямоугольный коробки

@ARSENJ · Регистрация: 13.01.2020

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

Количество одинаковых квадратов со стороной 1- не больше заданного числа. Найдите наибольший возможный объем прямоугольный коробки (без крышки), которую можно сделать из этих квадратов.

Ввод: Натуральное число от 5 до 2019.
Вывод: натуральное число.

Пример: Ввод: 9 Вывод: 2

Пояснение: такую коробку можно сделать из восьми или девяти квадратов

помогите пожалуйста буду благодарен

@u235 · 25.01.2020, 11:39

eaa, мне не совсем понятно, откуда взялся квадратный корень из N.. Поясните?
Если говорить чисто про перебор, то у меня получается два цикла что-то типа $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n)$ .

Добавлено через 10 минут
Matrix3007, даже если рассматримать коробки с непрямоугольным основанием, то при одном и том же N коробки с прямоугольным основанием будут иметь больший или равный объем.

Добавлено через 23 минуты

Python
1
2
3
4
5
6
7
8
9
10
import math
n=int(input('n='))
V=0
for h in range(1, int(((n-1)/4))+1):
    for l in range(1, int(math.sqrt(4*h*h+n)-2*h)+1):
        w=int((n-2*h*l)/(l+2*h));
        t=h*l*w
        if t>V:
            V=t
print('max volume=',V)

@eaa · 25.01.2020, 15:11

Действительно с корнем не правильно. Нужно брать sqrt(n) + 1. И высоту не перебирать, а вычислить.

Python
1
2
3
4
5
6
7
n = int(input())
n2 = round(n**.5) + 1
V = 0
for L in range(1, n2):
    for W in range(L, n2):
        V = max(V, (n - L * W) // (2 * (L + W)) * L * W)
print(V)

Вот тут $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n)$

u235, у Вас не $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n)$ , a $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n\sqrt{n})$

Добавлено через 3 минуты
забыл что range в python отнимает от правой границы 1

@u235 · 26.01.2020, 09:22

eaa, хорошее решение!
Но все же непонятно, почему у Вас W итерируется именно до n2, а не далее, до N/L или чего-то подобного?
C L и H - все понятно.
Например, для N=26 возможна коробка (1,8,1), в вашем коде максимально длинная коробка - (1,5,1).
Т.е. у Вас из перебора исключаются все длинные(широкие), но низкие и широкие(длинные) коробки.
Еще, не критично, но у вас в переборе иногда получаются коробки нулевой высоты.

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

@ARSENJ 0 / 0 / 0 Регистрация: 13.01.2020 Сообщений: 15

	Найдите наибольший возможный объем прямоугольный коробки 22.01.2020, 08:34. Показов 8749. Ответов 22 Метки нет (Все метки) Количество одинаковых квадратов со стороной 1- не больше заданного числа. Найдите наибольший возможный объем прямоугольный коробки (без крышки), которую можно сделать из этих квадратов. Ввод: Натуральное число от 5 до 2019. Вывод: натуральное число. Пример: Ввод: 9 Вывод: 2 Пояснение: такую коробку можно сделать из восьми или девяти квадратов помогите пожалуйста буду благодарен 0

@u235 5515 / 2868 / 571 Регистрация: 07.11.2019 Сообщений: 4,759
	26.01.2020, 09:22
	eaa, хорошее решение! Но все же непонятно, почему у Вас W итерируется именно до n2, а не далее, до N/L или чего-то подобного? C L и H - все понятно. Например, для N=26 возможна коробка (1,8,1), в вашем коде максимально длинная коробка - (1,5,1). Т.е. у Вас из перебора исключаются все длинные(широкие), но низкие и широкие(длинные) коробки. Еще, не критично, но у вас в переборе иногда получаются коробки нулевой высоты. 0

Найдите наибольший возможный объем прямоугольный коробки

Решение