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

@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).
Т.е. у Вас из перебора исключаются все длинные(широкие), но низкие и широкие(длинные) коробки.
Еще, не критично, но у вас в переборе иногда получаются коробки нулевой высоты.

Новые блоги и статьи Все статьи Все блоги /
Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .
Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .

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

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

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

Опции темы

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

Решение