Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Треугольник Пети#37558

Пятиклассник Петя любит решать различные математические задачи. Последняя его задача заключалась в том, чтобы по целым числам a, b, найти такие целые x и y, которые бы помогли построить треугольник ABC минимальной (ненулевой) площади. Треугольник Пети должен иметь следующие координаты \(A = (0, 0)\), \(B = (a, b)\), \(C = (x, y)\).
Помогите ему определить какую минимальную площадь может иметь треугольник ABC?

Входные данные
Даны два целых числа a и b, по модулю не превосходящие 10⁹ (\(a^2 + b^2 > 0\)).

Выходные данные
Выведите одно число - минимальную возможную площадь треугольника ABC с точностью 10^- 6.

Примеры

№	Входные данные	Выходные данные
1	4 0	2.0

НОД и алгоритм Евклида

✓ 353✗ 642700средняяВойти и решать

Задача для Пети и Вани#37555

Пятиклассники Петя и Ваня изучили на уроках математики следующий алгоритм Евклида:

Пусть a, b — числа, НОД которых надо найти.
Если b = 0, то число a — искомый НОД.
Если b > a, то необходимо поменять местами числа a и b.
Присвоить числу a значение a – b.
Вернуться к шагу 2.

Маша придумала для них задачу на закрепление. Она попросила мальчиков придумать такие числа a, b, c и d, что в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) наступает такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Напишите для Маши программу, которая проверит, удовлетворяют ли числа a, b, c, d условиям Маши.

Входные данные: Первая строка входных данных содержит количество наборов входных данных K (\(1 <= K <= 100\)). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (\(1 <= a,\ b <= 10^{18}\)). Вторая строка – два целых числа: c, d (\(1 <= c,\ d <= 10^{18}\)).
Все числа в строках разделены пробелом.

Выходные данные: Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».

Примеры

№	Входные данные	Выходные данные
1	2 20 10 10 10 10 7 2 4	YES NO

Вывод формулы НОД и алгоритм Евклида

✓ 106✗ 1 7501 000средняяВойти и решать

Вьетнамские умельцы#37554

Вьетнамские народные умельцы из кусочков рисовой соломки делают декоративные панно, наклеивая их на досточки. Какой наименьшей длины (в мм) должна быть соломка, чтобы ее можно было разрезать на равные части по А мм и В мм, не получая обрезков?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры

№	Входные данные	Выходные данные
1	20 27	540

НОД и алгоритм Евклида

✓ 62✗ 236500лёгкаяВойти и решать

Объем информации#37553

Студент на первом курсе скачивал из интернета в среднем А Кбайт информации в день, а на втором курсе – В Кбайт, оплачивая одну и ту же сумму денег за полученный интернетный трафик в неделю. Какой наименьший объем информации в Кбайтах он скачивал за неделю?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры

№	Входные данные	Выходные данные
1	60 75	300

НОД и алгоритм Евклида

✓ 42✗ 212700средняяВойти и решать

Орхидеи#37552

В теплице посадили в 2 ряда разные сорта орхидей. Цветы одного сорта разместили на расстоянии А см между растениями, а другого - на В см. Через какое расстояние орхидеи обоих сортов окажутся рядом?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры

№	Входные данные	Выходные данные
1	15 18	90

НОД и алгоритм Евклида

✓ 36✗ 92500лёгкаяВойти и решать

Математический конкурс#37551

На математическом конкурсе ребята играли в увлекательную древнюю китайскую головоломку Танграм. В одном игровом комплекте было А остроугольных, а в другом - В тупоугольных треугольников. Какое наименьшее число участников могут пользоваться комплектами из одинакового количества каждого вида треугольников?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры

№	Входные данные	Выходные данные
1	12 15	60

НОД и алгоритм Евклида

✓ 16✗ 21600лёгкаяВойти и решать

Папа и дочь#37550

Длина шага папы – А см, а у маленькой дочери – В см. Они начинают идти, поставив ноги на одну отметку. Какое расстояние они пройдут, чтобы их ноги опять встали вровень?

Оформите решение задачи в виде функции solve(A, B), которая возвращает ответ. Ничего вводить и выводить Вам не нужно!

Примеры

№	Входные данные	Выходные данные
1	70 15	210

НОД и алгоритм Евклида

✓ 48✗ 117600лёгкаяВойти и решать

Учитель математики Юрий Петрович#34916

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число \(19_{10} = 1\cdot2^4+0\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0 \) в двоичной системе запишется как 10011₂.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:

...
и результатом игры, следовательно, окажется число \(1\cdot2^4+1\cdot2^3+1\cdot2^2+0\cdot2^1+0\cdot2^0 = 28_{10} \)

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

Решите эту задачу с использованием битовых операций!

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

Входной файл содержит одно целое число N (0<=N<=32767).

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

Ваша программа должна вывести в выходной файл одно целое число, равное результату игры.

Примеры

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

Битовые операции Двоичная система счисления

✓ 132✗ 276800средняяВойти и решать

Длинный НОД#34852

Даны два числа. Найти их наибольший общий делитель.

Входные данные
Вводятся два натуральных числа, не превышающих 10⁹.

Выходные данные
Выведите НОД введенных чисел.

Примеры

№	Входные данные	Выходные данные
1	42 12	6

НОД и алгоритм Евклида

✓ 1 103✗ 781200лёгкаяВойти и решать

Дружественные числа#34842

Дружественные числа -– это два натуральных числа, таких, что сумма всех делителей одного числа (меньших самого этого числа) равна другому числу, и наоборот. Напишите программу, которая проверяет пару чисел на "дружественность". Используйте функцию, которая вычисляет сумму делителей числа.

Входные данные: Входная строка содержит два натуральных числа.

Выходные данные: Программа должна вывести слово 'YES', если полученные числа – дружественные, и слово 'NO' в противном случае.

Примеры

№	Входные данные	Выходные данные
1	220 284	YES
2	1210 1092	NO

Задачи на процедуры и функции Остатки

✓ 2 541✗ 6 868500лёгкаяВойти и решать

Обработка вводимых чисел - 13#34804

Дана последовательность целых чисел. Найти в ней минимальное число, не кратное 3. В последовательности имеется как минимум одно число не кратное 3

Входные данные: В первой строке вводится число N - количество чисел в последовательности, а затем N целых чисел, по одному в строке.
Выходные данные: Выведите ответ на задачу

Примеры

№	Входные данные	Выходные данные
1	7 4 6 5 -3 -4 3 -2	-4

Алгоритмы обработки Остатки Цикл for

✓ 151✗ 275500лёгкаяВойти и решать

Обработка вводимых чисел - 12#34803

Дана последовательность целых чисел. Найти в ней минимальное число, кратное 3. В последовательности имеется как минимум одно число кратное 3

Входные данные: В первой строке вводится число N - количество чисел в последовательности (N - положительное число, не превышающее 100) , а затем N целых чисел, по одному в строке (каждое число не превышает по модулю 1000).
Выходные данные: Выведите ответ на задачу

Примеры

№	Входные данные	Выходные данные
1	7 4 6 5 -3 -4 3 -2	-3

Алгоритмы обработки Остатки Цикл for

✓ 130✗ 184500лёгкаяВойти и решать

Обработка вводимых чисел - 10#34801

Дана последовательность целых чисел. Найти в ней максимальное число, кратное 3. В последовательности имеется как минимум одно число кратное 3

Входные данные: В первой строке вводится число N - количество чисел в последовательности, а затем N целых чисел, по одному в строке.
Выходные данные: Выведите ответ на задачу

Примеры

№	Входные данные	Выходные данные
1	7 4 6 5 -3 -4 3 -2	6

Алгоритмы обработки Остатки Цикл for

✓ 64✗ 112600лёгкаяВойти и решать

Выбрать числа Фибоначчи#33723

Дан массив чисел. Необходимо записать в другой массив, все числа Фибоначчи исходного массива. Если в исходном массиве нет чисел Фибоначчи, программа должна вывести число 0.

Входные данные
Первая строка содержит размер массива N. Во второй строке через пробел задаются N чисел – элементы массива (целые неотрицательные числа, не превышающие 1000). Гарантируется, что 0 < N ≤ 10000.

Выходные данные
Программа должна вывести в одну строчку все элементы построенного массива, разделив их пробелами. Если ни одного подходящего элемента в массиве не было, программа должна вывести число 0.

Примеры

№	Входные данные	Выходные данные
1	6 4 14 5 8 12 13	5 8 13

Алгоритмы обработки Арифметические алгоритмы (Теория чисел)

✓ 2 376✗ 3 998500лёгкаяВойти и решать

Выбрать простые#33722

Дан массив чисел. Необходимо записать в другой массив все простые числа исходного массива. Если в исходном массиве нет простых чисел, программа должна вывести число 0.

Входные данные
Первая строка содержит размер массива N. Во второй строке через пробел задаются N натуральных чисел – элементы массива (все числа не превышают 1000). Гарантируется, что 0 < N ≤ 10000.

Выходные данные
Программа должна вывести в одну строчку все элементы нового массива, разделяя их пробелами. Если ни одного подходящего элемента в массиве не было, программа должна вывести число 0.

Примеры

№	Входные данные	Выходные данные
1	6 1 2 3 4 5 6	2 3 5

Алгоритмы обработки Простые числа и разложение на множители

✓ 2 738✗ 7 155400лёгкаяВойти и решать

Функция Эйлера#33687

Дано натуральное число \(n <= 10^9,\) определите количество натуральных чисел, меньших \(n\) и взаимно простых с \(n\). Это число обозначается \( f(n) \)и называется фи-функцией Эйлера. Сложность алгоритма должна быть \( O(\sqrt{n})\) .

Входные данные
На вход подается натуральное число n.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	2	1

Функция Эйлера

✓ 255✗ 442500лёгкаяВойти и решать

Диофантовы уравнения#33656

Даны натуральные числа a, b, c. Если уравнение \(ax+by=c\) имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите слово Impossible.

Входные данные
Вводятся три натуральных числа.

Выходные данные
Выведите ответ на задачу.

Примечание
Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.

Примеры

№	Входные данные	Выходные данные
1	1 2 3	1 1
2	10 6 8	2 -2

Расширенный алгоритм Евклида

✓ 170✗ 1 153800средняяВойти и решать

И снова яблоки!#33599

n школьников делят k яблок “поровну”, то есть так, чтобы количество яблок, доставшихся любым двум школьникам, отличалось бы не более, чем на 1.
Запрещено использовать какие-либо алгоритмические конструкции (if, while, for и т.п.), кроме арифметических операций

Входные данные: Программа получает на вход числа n и k (по одному в строке).
Выходные данные: Программа должна вывести количество школьников, которым достанется яблок меньше, чем некоторым из их товарищей.
Примеры

№	Входные данные	Выходные данные
1	7 30	5

Остатки

✓ 96✗ 364600лёгкаяВойти и решать

Число 2 в степени N#33587

Дано натуральное число N (вводится с клавиатуры). Вычислите \(2^N\). Выведите на экран вычисленное значение (\(1<=N<=15\)).

Входные данные
На вход подается одно число N.

Выходные данные
Выведите на экран результат выражения \(2^N\).

Примеры

№	Входные данные	Выходные данные
1	3	8

Быстрое возведение в степень Линейные алгоритмы

✓ 17 526✗ 25 494100лёгкаяВойти и решать

Гипотеза Гольдбаха#33572

Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.

Входные данные
Программа получает на вход одно натуральное четное число n (\(3<n<2 \cdot 10^5\)).

Выходные данные
Программа должна вывести два числа, разделенные пробелом. Числа должны быть простыми и давать в сумме n.

Примеры

№	Входные данные	Выходные данные
1	4	2 2
2	6	3 3

Простые числа и разложение на множители

✓ 495✗ 673400лёгкаяВойти и решать