Озеленение Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт…
- User
Озеленение Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Администрация города решила разбить парк на пустыре площадью N×M . В парке планируется высадить деревья. Для каждого дерева нужно выделить участок прямоугольной формы с целочисленными сторонами и площадью, равной S . Все участки должны быть равны, одинаково ориентированы, и их стороны должны быть параллельны сторонам пустыря. Какое наибольшее количество деревьев можно высадить в парке?
Формат входных данных В трёх строках вводится три числа N , M , S (1≤N⋅M≤1018, 1≤S≤1012 ) — длина поля, ширина поля и площадь участка соответственно. Обратите внимание, что значения N , M и S могут превышать возможное значение 32 ‑битной целочисленной переменной, поэтому необходимо использовать 64 ‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++ тип long в Java и C#).
Формат выходных данных В первой строке выведите одно целое число — максимальное количество деревьев, которые можно высадить в этом парке. Гарантируется, что всегда удастся высадить хотя бы одно дерево.
Система оценки Решения, правильно работающие при N , M , S≤102 , будут оцениваться в 20 баллов. Решения, правильно работающие при S≤106 , будут оцениваться в 40 баллов.
Замечание В первом примере все участки будут иметь только размер 1×1 , их поместится ровно 100 штук. Во втором примере оптимальный размер участков будет 2×1 , их поместится ровно 5 штук. В третьем примере оптимальный размер участка будет 3×3 и участков поместится только два. Три или более участков разместить невозможно.
Ввод Вывод 10 10 1 100 2 5 2 5 4 8 9 2
- Assistant
Размер участка можно найти как квадратный корень из площади участка S , т.е. S ‾‾√ . Количество участков по длине будет равно N ‾‾√ , а по ширине — M ‾‾√ . Таким образом, общее количество участков будет равно N ‾‾√ ×M ‾‾√ . Найдем наименьшее целое число x , которое удовлетворяет условию: x <= N ‾‾√ ×M ‾‾√ . Это число и будет наибольшим количеством деревьев, которые можно высадить в парке.
Алгоритм решения:
- Считать значения N, M, S.
- Найти размер участка R = S ‾‾√ .
- Найти количество участков по длине L1 = N ‾‾√ .
- Найти количество участков по ширине L2 = M ‾‾√ .
- Найти наименьшее целое число x, которое удовлетворяет условию: x <= L1*L2.
- Вывести x.
Пример решения на Python:
import math
N = int(input()) M = int(input()) S = int(input())
R = int(math.sqrt(S)) L1 = int(math.sqrt(N)) L2 = int(math.sqrt(M))
x = L1*L2
print(x)
- User
мне нужно простое решение на языке С++
- Assistant
Конечно! Вот одно из простых решений на языке C++:
#include <iostream> #include <cmath> int main() { long long N, M, S; std::cin >> N >> M >> S; long long R = sqrt(S); long long L1 = sqrt(N); long long L2 = sqrt(M); long long x = L1 * L2; std::cout << x << std::endl; return 0; }В этом коде мы используем функцию
sqrt()из библиотеки<cmath>для вычисления квадратного корня. ЗначенияN,MиSсчитываются с помощьюstd::cin, а результат выводится на экран с помощьюstd::cout.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.