Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/40: Рейтинг темы: голосов - 40, средняя оценка - 4.60
 Аватар для Melvil
58 / 55 / 28
Регистрация: 20.05.2015
Сообщений: 256

Минимальный размер квадрата для размещения в нём N одинаковых прямоугольников

25.08.2015, 23:43. Показов 7866. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый вечер, не могу решить вот такую задачку:

Кликните здесь для просмотра всего текста
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причем, как оказалось, все они имели одинаковые размеры: w – в ширину и h – в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней – дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером w на h. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Входные данные

Входной файл INPUT.TXT содержит три целых числа: w, h, n (1 ≤ w, h, n ≤ 10^9).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.


Первый пример: 2 3 10
Ответ: 9
Пояснение:
Название: 1.gif
Просмотров: 166

Размер: 2.7 Кб

Собственно, попытался решить:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
int main()
{
    int n,w,h;
    cin >> w >> h >> n;
    int SquareSize = sqrt((double)n);
    int Result = SquareSize * max(w, h);
    cout << Result << endl;
}
Подскажите, что не так, спасибо.
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
25.08.2015, 23:43
Ответы с готовыми решениями:

Вычислить минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.
Здравствуйте. Попалась вот такая задачка: Дипломы Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике,...

Выбор сервера для размещения на нем файлов для скачивания пользователями
Здравствуйте. Есть сейчас сайт на Юкозе, тамошнее дисковое пространство не бесконечно, а брать более дорогой тариф не вижу смысла. Поэтому...

Как создать сервер для дальнейшего размещения на нем сайта?
Всем доброго времени суток. Прошу прощения, если вдруг я создал не в том разделе тему. Ситуация следующая: Хочу создать сайт с...

12
117 / 121 / 42
Регистрация: 25.08.2012
Сообщений: 1,294
26.08.2015, 00:47
Melvil, проверенные решения уже есть? Ну кроме 2, 3 и 10
0
2393 / 1920 / 763
Регистрация: 27.07.2012
Сообщений: 5,561
26.08.2015, 00:54
Цитата Сообщение от Melvil Посмотреть сообщение
Первый пример: 2 3 10
Ответ: 9
Пояснение:
А почему не 8? Почему во втором ряду один должен "выпирать" вправо?
0
117 / 121 / 42
Регистрация: 25.08.2012
Сообщений: 1,294
26.08.2015, 01:05
Melvil, попробуйте так:
C++
1
2
3
4
5
6
7
int side(int w, int h, n)
{
   int res = sqrt(w * h * n),
       sqr = pow(max(w, h), 2);
 
   return sqr < res ? res : sqr;
}
0
 Аватар для Melvil
58 / 55 / 28
Регистрация: 20.05.2015
Сообщений: 256
26.08.2015, 08:48  [ТС]
Цитата Сообщение от tnk500 Посмотреть сообщение
проверенные решения уже есть? Ну кроме 2, 3 и 10
Увы, нет.

John Prick, Нам нужен квадрат, высота трёх дипломов = 3, следовательно 3*3 = 9. Ширина = 2, а их в ряду либо 3, либо 4, но нам нужен квадрат, поэтому минимальная величина в данном случае 9.

tnk500, Не проходит второй тест, самих тестов не знаю.
0
26.08.2015, 10:05

Не по теме:

Цитата Сообщение от Melvil Посмотреть сообщение
Нам нужен квадрат, высота трёх дипломов = 3, следовательно 3*3 = 9. Ширина = 2, а их в ряду либо 3, либо 4, но нам нужен квадрат, поэтому минимальная величина в данном случае 9.
Цитата Сообщение от Melvil Посмотреть сообщение
Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной
Какие-то странные у Пети понятия о красоте...

0
 Аватар для Kuziaka
6 / 6 / 3
Регистрация: 22.07.2015
Сообщений: 36
26.08.2015, 12:13
попробуй так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
 
int main()
{
    long w,h,n;
    cin>>w>>h>>n;
    long long x=1;
    while((x*max(h,w)*x*max(h,w))<n*w*h)
    {
        x++;
    }
    cout<<x*max(h,w);
    return 0;
}
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
26.08.2015, 13:13
Лучший ответ Сообщение было отмечено Melvil как решение

Решение

Вот это проходит все тесты:
C++
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/////////////////////////////////////////////////////////////////////////////////////////
//Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике 
//и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих 
//из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, 
//причём, как оказалось, все они имели одинаковые размеры: w — в ширину и h — в высоту. 
//Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со 
//своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои 
//дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно 
//трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её 
//к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, 
//Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. 
//Каждый диплом должен быть размещён строго в прямоугольнике размером w на h. Дипломы 
//запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным 
//дипломам, не должны иметь общих внутренних точек. Требуется написать программу, 
//которая вычислит минимальный размер стороны доски, которая потребуется Пете для 
//размещения всех своих дипломов.
//
//ВХОДНЫЕ ДАННЫЕ
//
//Входной файл содержит три целых числа: w, h, n (1whn109 ).
//
//ВЫХОДНЫЕ ДАННЫЕ
//
//В выходной файл необходимо вывести ответ на поставленную задачу.
//
//ПРИМЕРЫ
//Входные данные
//
//2 3 10
//
//Выходные данные
//
//9
//
//Входные данные
//
//1 1 1
//
//Выходные данные
//
//1
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
bool    dim_is_valid
    (
        long long     dim,
        long long     w,
        long long     h,
        long long     n
    )
{
    return  dim / w * (dim / h)     >=   n;
}
/////////////////////////////////////////////////////////////////////////////////////////
long long     f
    (
        long long     w,
        long long     h,
        long long     n
    )
{
    long long   R   =   1;
 
    while   (
                !dim_is_valid
                    (
                        R,
                        w,
                        h,
                        n
                    )
            )
    {
        R   *=  2;
    }
    
    long long   L   =   R / 2;
 
    while( R - L > 1 )
    {
        long long     N   =   (L + R) / 2;
 
        if  (
                !dim_is_valid
                    (
                        N,
                        w,
                        h,
                        n
                    )
            )
        {
            L   =   N;
        }
        else
        {
            R   =   N;
        }
    }//while
 
    return  R;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    long long     w   =   0;
    long long     h   =   0;
    long long     n   =   0;
 
    std::cin    >>  w
                >>  h
                >>  n;
 
    std::cout   <<  f( w, h, n )
                <<  std::endl;
 
    //system("pause");
}
1
 Аватар для Melvil
58 / 55 / 28
Регистрация: 20.05.2015
Сообщений: 256
29.08.2015, 12:37  [ТС]
Цитата Сообщение от Mr.X Посмотреть сообщение
Вот это проходит все тесты:
Да, спасибо. тесты проходит, можно узнать по какой логике строилось это решение? Не очень понятно:
C++
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
27
28
29
30
31
32
33
34
35
36
37
#include "stdafx.h"
#include <iostream>
bool dim_is_valid (long long dim, long long w, long long h, long long n)
{
    return  (dim / w) * (dim / h) >= n;
}
 
long long f(long long w, long long h, long long n)
{
    long long R = 1;
    while (!dim_is_valid (R,w,h,n) )
    {
        R *= 2;
    }
    long long L = R / 2;
    while (R - L > 1)
    {
        long long N = (L + R) / 2;
        if (!dim_is_valid(N,w,h,n))
        {
            L = N;
        }
        else
        {
            R = N;
        }
    }
    return  R;
}
int main()
{
    long long w = 0;
    long long h = 0;
    long long n = 0;
    std::cin >> w>> h >> n;
    std::cout << f(w, h, n)<< std::endl;
}
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
29.08.2015, 14:58
Цитата Сообщение от Melvil Посмотреть сообщение
можно узнать по какой логике строилось это решение?
Ну, пусть ответ равен m. Тогда значения меньше m не удовлетворяют условию, а >= m - удовлетворяют, т.е. имеем монотонную функцию. Применяя бинарный поиск, находим m.

Добавлено через 45 минут
Цитата Сообщение от Melvil Посмотреть сообщение
C++
1
long long f(long long w, long long h, long long n)
Красиво смотрится! Вы реально способны это прочесть?
1
 Аватар для Melvil
58 / 55 / 28
Регистрация: 20.05.2015
Сообщений: 256
30.08.2015, 00:25  [ТС]
Mr.X, Спасибо, разобрался.

Цитата Сообщение от Mr.X Посмотреть сообщение
Красиво смотрится! Вы реально способны это прочесть?
Лично мне так удобнее.

Добавлено через 21 минуту
Такой вопрос, а почему именно с помощью бинарного поиска находится верный ответ?
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
30.08.2015, 07:33
Цитата Сообщение от Melvil Посмотреть сообщение
Такой вопрос, а почему именно с помощью бинарного поиска находится верный ответ?
Вопрос задан слишком философски. Можете его попроще сформулировать?

Добавлено через 5 часов 58 минут
В смысле, почему он срабатывает или почему я его выбрал?
Срабатывает потому, что размер доски является монотонной функцией от количества дипломов. А выбрал я его потому, что этот способ решения показался мне самым простым.
0
 Аватар для Melvil
58 / 55 / 28
Регистрация: 20.05.2015
Сообщений: 256
30.08.2015, 09:25  [ТС]
Mr.X, Всё ясно, спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
30.08.2015, 09:25
Помогаю со студенческими работами здесь

Рекурсия: создать программу которая будет рисовать квадрат, в нем еще 4 квадрата, в левом верхнем опять 4 квадрата и так далее.
Помогите пожалуйста, нужно создать программу которая будет рисовать квадрат, в нем еще 4 квадрата, в левом верхнем опять 4 квадрата и так...

Шифровать методом Магического квадрата (размер квадрата 9х9) С++
Шифровать методом Магического квадрата (размер квадрата 9х9) С++ Дана таблица 9х9. Надо реализовать программу на С++...

Для каждого квадрата размером MхM матрицы вычислить сумму стоящих в нем чисел
Примечание: Вывод результата на рабочий лист MS Excel. При решении задач использовать динами-ческие массивы. Дана квадратная таблица A и...

Массив: Для каждого квадрата размером MxM в этой таблице вычислить сумму стоящих в нём чисел.
Здравствуйте, помогите пожалуйста, как можно сделать цикл по перемещению квадрата в матрице. Понятно, что мы должны вычитать и прибавлять...

Минимальный размер выборки - для научного исследования
Уважаемые знатоки! Научным руководителем была поставлена задача - определить репрезентативный сабж из генеральной совокупности, при...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Символьное дифференцирование
igorrr37 13.02.2026
/ * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru