Помогите с задачей с++(сириус) даю 60баллов
Дипломы
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причём, как оказалось, все они имели одинаковые размеры: w
в ширину и h
в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером w
на h
. Дипломы запрещается поворачивать. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
int n, w, h;
cin >> n >> w >> h;
int d = gcd(w, h);
int k1 = w / d, k2 = h / d;
int max_row = min(n, w / k2);
int max_col = min(n, h / k1);
int ans = 1;
while (max_row * max_col < n) {
if (max_row < max_col) max_row++;
else max_col++;
ans++;
}
cout << ans * d << endl;
return 0;
}
"Сразу говорю, решал не я"
Алгоритм решения:
1. Вводим количество дипломов и их размеры w и h.
2. Находим наибольший общий делитель w и h, так как квадрат может быть образован только если w и h имеют одинаковый НОД.
3. Вычисляем количество дипломов, которые могут быть помещены в одной строке и в одном столбце доски, используя размеры w и h и размеры доски.
4. Находим минимальный размер доски, который может содержать все дипломы, увеличивая размеры доски до тех пор, пока количество помещаемых дипломов в строке или столбце не совпадет с количеством дипломов.
5. Выводим минимальный размер стороны доски.
Пример кода на C++:
```
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
int n, w, h;
cin >> n >> w >> h;
int d = gcd(w, h);
int k1 = w / d, k2 = h / d;
int max_row = min(n, w / k2);
int max_col = min(n, h / k1);
int ans = 1;
while (max_row * max_col < n) {
if (max_row < max_col) max_row++;
else max_col++;
ans++;
}
cout << ans * d << endl;
return 0;
}
```