Сдать решение задачи 5-Интересные числа
Полный : 100
Ограничение времени: 1 с
Ограничение памяти: 512M
Ограничение размера стека: 64M
Задача 5: Интересные числа
На занятиях математического кружка Сережа узнал об интересных числах — это числа, которые имеют простые делители только 2, 3 и 5. Теперь он хочет узнать наибольшее интересное число, не превосходящее числа n.
Входные данные
Программа получает на вход целое число n (2 ≤ n ≤ 1017).
Обратите внимание, что значение n может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные числа (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).
Выходные данные
Программа должна вывести одно целое число — максимальное интересное число, не превосходящее n.
Система оценки
Решения, правильно работающие при n ≤ 104, будут оцениваться в
Решения, правильно работающие при n ≤ 108, будут оцениваться в
Примеры
Ввод
Вывод
Пояснение
7
6
Первые интересные числа — это 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30,
Поэтому максимальное интересное число, не превосходящее 7 — это 6.
100
100
Число 100 разлагается на множители, как 100 = 22 × 52, поэтому число 100 само является интересным.
Какой оператор цикла желательно использовать, если известно число повторений тела цикла?
repeat <оператор1, …>until <условие>
while <условие>do <оператор>
for <параметр>:= <начальное значение>to<конечное значение> do<оператор>
2. Используется оператор for i:= -10 to 10 do…
После завершения выполнения тела цикла i = 10
3. Цикл в фрагменте программы
p:=1;
repeat
p:=p*0.1
until p>0.1;
будет исполнен:
1 раз
2 раза
бесконечное число раз
0 раз
3 раза
4. Цикл в фрагменте программы
a:=1;
b:=1;
while a+b<8 do
begin
a:=a+1; b:=b+2
end;
выполнится:
0 раз
3 раза
2 раза
1 раз
бесконечное число раз
5. Какой оператор цикла желательно использовать для записи алгоритмической конструкции, изображённой на схеме?
НЕТ СХЕМЫ. ОТВЕТИТЬ НА ВОПРОС НЕВОЗМОЖНО.
while <условие> do <оператор>
for <параметр>:= <начальное значение> to <конечное значение> do <оператор>
repeat <оператор1, …> until <условие>
6. Какой оператор цикла желательно использовать, если известно условие выхода из цикла?
repeat <оператор1, …> until <условие>
for <параметр>:= <начальное значение> to <конечное значение> do <оператор>
while <условие> do <оператор>
7. Определите, какое значение будет выведено на экран в результате выполнения приведенной ниже последовательности операторов:
a:=1; b:=1;
while a<=32 do a:=a*2; b:=b*a; //Обратите внимание! Нет begin end.
write (b)
32
256
64
128
8. Используется оператор for i:= -5 to 9 do…
При первом выполнении тела цикла i = -5
9. Чему равно значение переменной s после выполнения следующего фрагмента программы
Фрагмента программы нет! Задание решить нельзя!
Требуется найти максимум этого выражения (т.е. на самом деле - максимум суммы квадратов) при условии, что сумма всех ni равна N и ni - натуральные числа.
Если K = 1, то всё очевидно - ответ N(N - 1)/2. Пусть K > 1.
Предположим, n1 <= n2 <= ... <= nK - набор чисел, для которых достигается максимум, и n1 > 1. Уменьшим число вершин в первой компоненте связности до 1, а оставшиеся вершины "перекинем" в K-ую компоненту связности. Вычислим, как изменится сумма квадратов:
Поскольку по предположению n1 > 1 (тогда и nK > 1), то сумма квадратов увеличится, что противоречит предположению о том, что на выбранном изначально наборе достигается максимум. Значит, максимум достигается, если наименьшая по размеру компонента связности - изолированная вершина. Выкинем эту компоненту связности, останутся K - 1 компонента связности и N - 1 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.
Итак, должно выполняться
Подставив в исходную формулу, получаем
Это и есть ответ.