Гадание время 1 сек память 16 мб сложность 13

Входные данные В единственной строке входного файла INPUT.TXT записаны через пробел два натуральных числа – А и В, не превышающие 46340.

Выходные данные В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число – НОК чисел А и В.

Примеры № INPUT.TXT OUTPUT.TXT 36 27 39 65 Разбор Наименьшее общее кратное (НОК) двух целых чисел a и b есть наименьшее натуральное число, которое делится на a и b. Обычно обозначается [a, b], а иногда НОК(m, n) или LCM(a, b). Например, НОК(16, 24)=48.

Для нахождения НОК удобно использовать следующее свойство: для любых натуральных чисел a и b верно равенство НОД(a, b)*НОК(a, b)=a*b, откуда получаем, что НОК(a, b)=a*b/НОД(a, b).

В условиях данной задачи можно НОД найти перебором, но более универсально использовать алгоритм Евклида, реализация которого рассмотрена в задаче 148.

015. Дороги (Время: 1 сек. Память: 16 Мб Сложность: 18%) В галактике «Milky Way» на планете «Snowflake» есть N городов, некоторые из которых соединены дорогами. Император галактики «Milky Way» решил провести инвентаризацию дорог на планете «Snowflake». Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог. Требуется написать программу, помогающую императору сосчитать количество дорог на планете «Snowflake».

Входные данные В первой строке входного файла INPUT.TXT записано число N (0 N 100). В следующих N строках записано по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i, j) квадратной матрицы стоит единичка, то i-ый и j-ый города соединены дорогами, а если нолик, то не соединены.

Выходные данные В выходной файл OUTPUT.TXT необходимо вывести число, определяющее количество дорог на планете «Snowflake».

Пример № INPUT.TXT OUTPUT.TXT 5 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 016. Лесенка (Время: 1 сек. Память: 16 Мб Сложность: 55%) Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий. Требуется написать программу, вычисляющую число лесенок, которое можно построить из N кубиков.

Входные данные Во входном файле INPUT.TXT записано натуральное число N (1 N 100) – количество кубиков в лесенке.

Выходные данные В выходной файл OUTPUT.TXT необходимо вывести число лесенок, которые можно построить из N кубиков.

Примеры № INPUT.TXT OUTPUT.TXT 1 3 2 6 017. Поле чудес (Время: 1 сек. Память: 16 Мб Сложность: 31%) Для игры в «Поле чудес» используется круглый барабан, разделенный на сектора, и стрелка. В каждом секторе записано некоторое число. В различных секторах может быть записано одно и то же число. Однажды ведущий игры решил изменить правила. Он сам стал вращать барабан и называть игроку (который барабана не видел) все числа подряд в том порядке, в котором на них указывала стрелка в процессе вращения барабана. Получилось так, что барабан сделал целое число оборотов, то есть последний сектор совпал с первым. После этого, ведущий задал участнику вопрос: какое наименьшее число секторов может быть на барабане Требуется написать программу, отвечающую на этот вопрос ведущего.

Входные данные В первой строке входного файла INPUT.TXT записано число N – количество чисел, которое назвал ведущий (2 N 30000). Во второй строке записано N чисел, на которые указывала стрелка в процессе вращения барабана. Первое число всегда совпадает с последним (в конце стрелка указывает на тот же сектор, что и в начале). Числа, записанные в секторах барабана – натуральные, не превышающие 32000.

Выходные данные В выходной файл OUTPUT.TXT необходимо вывести одно число – минимальное число секторов, которое может быть на барабане.

Примеры № INPUT.TXT OUTPUT.TXT 13 5 3 1 3 5 2 5 3 1 3 5 2 4 1 1 1 4 1 2 3 018. Факториал (Время: 1 сек. Память: 16 Мб Сложность: 42%) Требуется вычислить факториал целого числа N. Факториал обозначают как N! и вычисляют по формуле:

N! = 1 * 2 * 3 * … * (N-1) * N, причем 0! = 1.

Так же допустимо рекуррентное соотношение: N! = (N-1)! * N Входные данные В единственной строке входного файла INPUT.TXT записано одно целое неотрицательное число N (N a3 an-1 a2 … an.

Дана числовая последовательность. Требуется определить длину самой длиной ее пилообразной непрерывной подпоследовательности.

Входные данные В первой строке входного файла INPUT.TXT записано натуральное число N – количество элементов последовательности. Во второй строке файла через пробел записаны N элементов целочисленной последовательности . Ограничения: N

Выходные данные В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число – длину самой длиной непрерывной пилообразной подпоследовательности.

Примеры № INPUT.TXT OUTPUT.TXT 3 1 2 12 5 7 6 3 4 2 7 1 8 9 4 5 1 -2 3 -4 021. Зарплата (Время: 1 сек. Память: 16 Мб Сложность: 4%) В отделе работают 3 сотрудника, которые получают заработную плату в рублях. Требуется определить: на сколько зарплата самого высокооплачиваемого из них отличается от самого низкооплачиваемого.

Входные данные В единственной строке входного файла INPUT.TXT записаны размеры зарплат всех сотрудников через пробел. Каждая заработная плата – это натуральное число, не превышающее 105.

Выходные данные В выходной файл OUTPUT.TXT необходимо вывести одно целое число – разницу между максимальной и минимальной зарплатой.

Примеры № INPUT.TXT OUTPUT.TXT 1 100 500 1000 2 36 11 20 Разбор В данной задаче необходимо найти наибольшее и наименьшее значение и вывести их разность. Для этого проще всего упорядочить заданные числа A, B и C в порядке неубывания (ABC) и тогда значение C-A будет решением этой задачи. Для этого можно было бы прибегнуть к принципу чайника и отсортировать массив из трех элементов методом «пузырька», например. Но это решение не самое разумное в данном случае.

Здесь мы можем применить тот же метод «пузырька», но без циклов и массивов. Действительно, за 3 сравнения можно достичь желаемого результата. Сначала сравнивая А и B мы можем в A поместить наименьшее из них, поменяв их местами. Далее сравнивая A и C мы поместим в А наименьший из 3х чисел элемент. А после сравнения B и C в C получим наибольший. Описанный выше алгоритм можно представить в виде следующей блок-схемы:

На всякий случай напомним как с помощью третьей переменной можно поменять значения переменных местами:

В языке Си для различных целочисленных переменных a и b можно использовать более красивую и короткую запись без использования третьей переменной:

022. Единицы (Время: 1 сек. Память: 16 Мб Сложность: 16%) На уроках информатики вас, наверное, учили переводить числа из одних систем счисления в другие и выполнять другие подобные операции. Пришло время продемонстрировать эти знания. Найдите количество единиц в двоичной записи заданного числа.

Входные данные Во входном файле INPUT.TXT записано целое число n (0 n 2*109).

Выходные данные В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число – количество двоичных единиц в записи числа n.

Примеры № INPUT.TXT OUTPUT.TXT 1 5 2 7 Разбор Это достаточно простая задача, т.к. ответом является сумма цифр заданного числа в двоичном представлении. Реализация алгоритма решения может иметь следующий вид:

023. Гадание (Время: 1 сек. Память: 16 Мб Сложность: 13%) Как и многие другие девочки, Маша любит разные гадания. Некоторое время назад Маша узнала новый способ гадать на числах – для какого-нибудь интересующего ее натурального числа n надо посчитать сумму всех чисел, на которые n делится без остатка. Маша не очень любит арифметику, и попросила вас написать программу, которая автоматизирует процесс гадания.

Входные данные В единственной строке входного файла INPUT.TXT записано натуральное число n (0 n 1000), которое Маша была вынуждена сообщить.

Выходные данные В выходной файл OUTPUT.TXT выведите сумму всех натуральных делителей числа n.

Примеры № INPUT.TXT OUTPUT.TXT 1 6 2 10 024. Вырубка деревьев (Время: 1 сек. Память: 16 Мб Сложность: 46%) Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом.

Деревья перед дворцом короля посажены в ряд, всего там растет n деревьев, расстояния между соседними деревьями одинаковы.

После вырубки перед дворцом должно остаться m деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.

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

Входные данные Входной файл INPUT.TXT содержит два целых числа n и m (0 m, n 1000).

Выходные данные В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число – искомое число способов.

Пример № INPUT.TXT OUTPUT.TXT 1 5 3 Пояснение к примеру Если обозначить условно исходное расположение деревьев перед дворцом как «TTTTT», то возможные результаты после вырубки следующие: «TTT..», «.TTT.», «..TTT», «T.T.T».

025. Больше-меньше (Время: 1 сек. Память: 16 Мб Сложность: 3%) Одна из основных операций с числами – их сравнение. Мы подозреваем, что вы в совершенстве владеете этой операцией и можете сравнивать любые числа, в том числе и целые.

В данной задаче необходимо сравнить два целых числа.

Входные данные В двух строчках входного файла INPUT.TXT записаны числа A и B, не превосходящие по абсолютной величине 2*109.

Выходные данные Запишите в выходной файл один символ “ ”, если A > B и “=”, если A=B.

Примеры № INPUT.TXT OUTPUT.TXT 5 -13 = Разбор В этой задаче нужно считать два числа и произвести их сравнение с помощью условного оператора if, можно даже без else. Заметим, что при чтении целых чисел можно не обращать внимание на то, что они записаны в разных строках: при использовании записи scanf(«%d%d», &x, &y) или read(x,y) числа будут считаны так же успешно, как если бы они были записаны через пробел.

026. Две окружности (Время: 1 сек. Память: 16 Мб Сложность: 17%) На плоскости даны две окружности. Требуется проверить, пересекаются ли они.

Входные данные Входной файл INPUT.TXT состоит из двух строк. На каждой строке записана информация об одной окружности – координаты ее центра x и y (целые числа, по модулю не превосходящие 5000) и радиус (целое число 1 r 1000).

Выходные данные В выходной файл OUTPUT.TXT выведите «YES», если окружности пересекаются, и «NO» в противном случае.

Примеры № INPUT.TXT OUTPUT.TXT 0 0 2 YES 0 3 1 1 1 NO 4 4 Разбор Для начала определимся с тем, что нам известны радиусы окружностей и они равны r1 и r2. Так же по формуле расстояния между точками мы можем вычислить расстояние между центрами данных окружностей:

r = sqrt( (x2-x1)2 + (y2-y1)2 ) Заметим так же, что окружности будут пересекаться тогда и только тогда, когда возможен треугольник со сторонами r1, r2 и r.

Фигуру, две стороны которой лежат на третьей или одна из сторон имеет нулевую длину так же будем считать треугольником, т.к.

окружности могут друг друга касаться(r=r1+r2), либо полностью совпадать (r=0).

Треугольник считается возможным если сумма двух любых его сторон не меньше третьей. Т.е. в нашем случае достаточно проверить, что r1+r2 r и r+r2 r1 и r+r1 r2. При этом желательно использовать вещественные типы данных. Так же можно провести аккуратное сравнение с учетом возможных погрешностей при вычислениях.

027. Художник (Время: 1 сек. Память: 16 Мб Сложность: 31%) Известный художник решил написать новый шедевр. После многих дней усердной работы он захотел исследовать свое творение. Художник вспомнил, что картина писалась следующим образом: сначала был взят белый холст, имеющий форму прямоугольника шириной w и высотой h. Затем художник нарисовал на этом холсте n прямоугольников со сторонами, параллельными сторонам холста и вершинами, расположенными в целочисленных координатах. Помогите художнику определить площадь незакрашенной части холста.

Входные данные Первая строка входного файла INPUT.TXT содержит два натуральных числа w и h (1 w, h 100). Во второй строке записано целое число n (1 n 5000) – количество прямоугольников. Следующие n строк содержат информацию о всех прямоугольниках. Каждая строка описывает один прямоугольник в виде четырех чисел x1, y1, x2, y2, где (x1, y1) и (x2, y2) – координаты левого верхнего и правого нижнего угла прямоугольника соответственно.

Выходные данные Выведите в выходной файл OUTPUT.TXT одно целое число – площадь незакрашенной части холста.

Примеры № INPUT.TXT OUTPUT.TXT 5 5 1 1 3 2 2 4 6 7 2 0 0 5 1 1 4 2 2 3 Разбор В этой задаче необходимо понять, что координаты закрашиваемых прямоугольников определяются не координатами ячеек, а координатами сетки, т.е. левая верхняя координата имеет значение (0, 0) в то время как правая нижняя — (w, h). Это следует из примеров, первый из которых представлен на рисунке справа, где видно, что действительно 18 клеток таблицы не закрашены. В этой задаче необходимо понять, что координаты закрашиваемых прямоугольников определяются не координатами ячеек, а координатами сетки, т.е. левая верхняя координата имеет значение (0, 0) в то время как правая нижняя – (w, h). Это следует из примеров, первый из которых представлен на рисунке справа, где видно, что в этой задаче необходимо понять, что координаты закрашиваемых прямоугольников определяются не координатами ячеек, а координатами сетки, т.е. левая верхняя координата имеет значение (0, 0) в то время как правая нижняя – (w, h).

Это следует из примеров, первый из которых представлен на рисунке справа, где видно, что действительно 18 клеток таблицы не закрашены.

Данная задача решается «в лоб». Можно определить матрицу a[1..n][1..m] и пошагово считывать координаты противоположных вершин прямоугольника и сразу же заполнять единицами этот прямоугольник в матрице. Предварительно матрицу необходимо обнулить.

По завершении процесса можно подсчитать число оставшихся нулей в матрице, это и будет ответом на задачу. Максимальное число простых операций может быть равно 50 000 000.

Несмотря на такое, казалось бы огромное число решение задачи укладывается в 1 секунду.

Дело в том, что проводимые операции – это заполнение элементов массива числами, которые выполняются очень быстро. Если бы столько же раз нам нужно было выполнить серию умножений, то мы вряд ли смогли бы рассчитывать на успех.

Приведем пример решения данной задачи на алгоритмическом языке:

028. Симметрия (Время: 1 сек. Память: 16 Мб Сложность: 19%) Многие из вас, вероятно, знакомы с понятием симметрии относительно прямой. Пусть на плоскости расположена прямая L и точка A. Точка B называется симметричной точке A относительно прямой L, если отрезок АВ перпендикулярен прямой L и делится пополам точкой пересечения с ней. В частности, если точка А лежит на прямой L, то точка B совпадает с точкой А.