Задача 18 на числа и их свойства на ЕГЭ-2022 по математике
В этой статье мы расскажем, какие задачи встретились на ЕГЭ-2022 по математике под номером 18. Это последняя в варианте, самая сложная задача ЕГЭ. Тема – числа и их свойства.
В этом году они действительно были непростыми, нестандартными. Но есть и хорошая новость: в каждой из них пункт (а) решался за 3 минуты.
Начнем с наиболее стандартной из них, задачи 18 из московского варианта. Здесь мы можем ввести переменные и сделать «заготовку», то есть математическую модель для всех пунктов задачи.
С натуральным трехзначным числом проводят следующую операцию: из числа вычитают его сумму цифр и полученный результат делят на 3.
а) Может ли результатом выполнения операции быть число 201?
б) Может ли результатом выполнения быть число 251?
в) Сколько различных результатов можно получить, если применить данную операцию для всех трехзначных чисел от 600 до 999 включительно?
Сделаем «заготовку» для всех пунктов задачи.
Запишем число А в виде: .
а) Да, может быть
Пусть . Заметим, что с – любое.
б) Нет, не может быть , так как а 251 не делится на 3, пришли к противоречию.
Выясним, какие значения может принимать m.
Так как a, b и с – цифры числа А,
то есть
то есть
Значит,
Числа m являются членами арифметической прогрессии, где
Найдем n – количество членов этой прогрессии.
Мы получили, что чисел вида не более 43, и они являются членами арифметической прогрессии где всего таких чисел не более 43.
Проверим, может ли быть
возможно при любое.
Получаем числа всего 10 чисел, для которых
Случай также возможен. Тогда
11 a + b = 108, подходят а = 9, b = 9, с – любое.
Проверим, может ли m быть равным любому члену арифметической прогрессии
Пусть . С другой стороны,
По условию, , то есть .
Так как b – цифра,
Это значит, что k может делиться на 11 без остатка. Или давать остаток от 1 до 9 от деления на 11. Но k не может давать остаток 10 от деления на 11.
Раньше мы нашли, что Исключим числа, дающие остаток 10 от деления на 11. Это 10, 21, 33, всего 3 числа. Получаем, что m может принимать не более 43 – 3 = 40 различных значений. Это оценка.
Для каждого m можно подобрать такие a и b, что условие задачи выполняется. Так, как мы сделали для m = 198 и m= 324.
Ответ: а) да; б) нет; в) 40.
В следующей задаче нет ни переменных, ни уравнений. А решение – это текст, сочинение-рассуждение на заданную тему : -) Напомним, что если в каком-либо пункте задачи 18 ответ «да», то нужно написать: «Да, может, вот пример». Если ответ «нет» — надо привести доказательство, почему не может такого быть.
2. ЕГЭ-2022, Санкт-Петербург В трех коробках лежат камни: в первой 101 камень, во второй 102, в третьей 104, в четвертой коробке камней нет.
За 1 ход берут по 1 камню из любых трех коробок и кладут в оставшуюся.
а) Может ли в 1 коробке получиться 101 камень, во второй 102, в третьей 100, в четвертой 4 камня?
б) Может ли оказаться 306 камней в четвертой коробке через некоторое количество ходов?
в) какое наибольшее количество камней может оказаться в первой коробке?
Сделаем следующие действия:
б) Приведем решение И. В. Яковлева:
Такого случиться не может.
Допустим, такое произошло.
Всего камней 307. Если в четвертой коробке 306 камней, то значит, еще в какой-либо коробке находится 1 камень, и 2 коробки пустые.
После каждого хода четность числа камней в каждой коробке меняется на противоположную, поскольку либо в коробку добавляют 2 камня, либо убирают 1 камень.
Поэтому количества камней в коробках 1 и 2 не смогут стать равными (у них изначально была разная четность). Аналогично, не могут стать равными количества камней в коробках 1 и 3.
Значит, финальная ситуация обязательно 1, 0, 0, 306. Но после каждого хода количества камней в коробках 2 и 3 либо одновременно уменьшаются на 1, либо в одной из них -1, а в другой +3, так что количества камней в коробках 2 и 3 всегда отличаются не менее чем на 2. Противоречие.
Другой способ доказательства:
После каждого хода для количеств камней в любых двух коробках имеем -1, -1 или -1, +3. В обоих случаях остаётся неизменной разность остатков от деления этих чисел на 4. Исходно в первых трёх коробках эти остатки разные (а именно, 1, 2 и 0), то есть все три разности –- ненулевые. Значит, они будут ненулевыми после каждого хода, так что числа камней в первых трёх коробках всегда будут попарно различны. Следовательно, мы никогда не придём к ситуации, когда в двух из этих коробок нули (чтобы в четвёртой было 306).
в) Найдем наибольшее количество камней, которое может оказаться в первой коробке.
Все 307 камней не могут в ней оказаться, потому что тогда в остальных коробках будет 0 камней. В пункте (б) доказано, что это невозможно.
Предположим, что в 1-й коробке 306 камней. Тогда во 2-й коробке 1 камень, в 3-й и 4-й 0 камней. Другие случаи невозможны, поскольку только в 3-й и 4-й коробках количество камней изначально делилось на 4.
Но ситуация 306; 1; 0; 0 также невозможна, поскольку количества камней в коробках 2 и 3 всегда отличаются не менее чем на 2.
В первой коробке может быть 305 камней. Приведем пример, как это получить.
Первоначально в коробках: (101; 102; 104; 0).
Переложим 25 раз по одному камню из первых трех коробок в четвертую. Получим:
(76; 77; 79; 75). Следующие действия:
Ответ: а) да; б) нет; в) 305.
Еще одна задача, про числа на круге, была предложена на Дальнем Востоке и в других регионах России. Обратите внимание, что сюжеты задач разные, но во всех так или иначе используются понятия: делимость, четность, деление с остатком.
3. ЕГЭ-2022, Дальний Восток
По кругу расставлены N чисел так, что сумма трех последовательных чисел не делится на 3, а сумма четырех последовательных делится на 3.
а) Может ли N быть равно 240?
б) Может ли N быть равно 219?
в) Найдите наибольшее N, если числа различны и каждое меньше 340.
а) Да, может N = 240.
Например, по кругу расположены 60 четверок вида 1,1,2,2 или 1,2,1,2.
Сумма чисел в каждой тройке не делится на 3, а в каждой четверке делится на 3.
Возможен и такой вариант:
И в том, и в другом случае мы не ставим подряд три единицы или три двойки.
Посмотрим, какие вообще числа могут находиться на круге.
Пусть а, b, с и d – последовательные числа на круге, такие
что а + b + с — не делится на 3. Тогда а + в + с при делении на 3 дает остаток 1 или 2.
Сумма делится на 3, тогда где
Получаем систему
Если из уравнения (3) вычесть уравнение (1), то получим – это означает, что при делении числа d на 3 получается остаток 2.
Если из уравнения (3) вычесть уравнение (2), то получим – это означает, что при делении числа d на 3 получается остаток 1.
Значит, число d при делении на 3 дает остаток 1 или 2.
Так как d – любое число на круге, то все числа на круге при делении на 3 дают остаток 1 или 2, то есть на круге все числа вида 3m + 1 или 3m + 2.
Так как по условию любые три подряд идущие числа не делятся на 3, значит, числа вида 3m + 1 не стоят три подряд, а стоят через одно или через два.
Аналогично, числа вида 3m + 2 не стоят три подряд, а стоят через одно или через два.
Обозначим числа, дающие при делении на 3 остаток 1, как (1).
Числа, дающие при делении на 3 остаток 2, обозначим как (2).
Других вариантов нет, так как сумма чисел в четверке должна быть кратна трем. Это значит, что если в ней 2 числа типа (1), то должно быть и 2 числа типа (2).
Предположим, что N = 129.
то есть на круге 32 четверки чисел и еще одно число, причем это может быть либо число типа (1), либо число типа (2). Где же оно может быть расположено?
А вот нигде не может!
Рассмотрим сначала первый вариант. Пусть наше число типа (1). Чтобы три числа типа (1) не стояли подряд, мы можем поставить его только между двумя числами типа (2). Но теперь вместе с тремя соседями слева или с тремя соседями справа оно дает четверку, в которой сумма не делится на 3.
Аналогично – если мы попытаемся добавить число типа (2).
Так же и во втором варианте. Куда бы мы ни добавили новое число, вместе с тремя соседями слева или с тремя соседями справа оно дает четверку, в которой сумма не делится на 3. Значит, 129 чисел на круге быть не может.
в) Найдем наибольшее количество чисел на круге при условии, что все они различны и не превосходят 340. Мы сказали, что это должны быть числа, которые при делении на 3 дают остаток 1 или остаток 2. В пункте (б) мы определили, как они должны быть расположены на круге.
Мы сказали также, что если N – количество чисел на круге, то N делится на 4.
Пусть n = 4р, то есть на круге р четверок чисел, в каждой из которых 2 числа типа (1) и 2 числа типа (2). Числа типа (1), которые при делении на 3 дают остаток 1, — это 1, 4, 7, 10 .
Числа типа (2), которые при делении на 3 дают остаток 2, — это 2, 5, 8, 11 .
Наибольшее число на круге – это число типа (2), и по условию, оно меньше 340. Числа типа (2) образуют арифметическую прогрессию
Так как , получим: , отсюда
Значит, на круге не более 113 чисел типа (2). Но тогда и чисел типа (1) столько же, то есть тоже не более 113. Всего на круге не более 113 + 113 = 226 чисел. Это оценка.
Приведем пример для 226 различных чисел на круге.
Ответ: а) да; б) нет; в) 226.
И еще одна задача из Санкт-Петербурга.
4. ЕГЭ-2022, Санкт-Петербург
На доске написано N различных натуральных чисел, каждое из которых не превосходит 27. Для каждых двух написанных чисел a и b таких, что а < b ни одно из написанных чисел не делится на b – а и ни одно из написанных чисел не является делителем числа b – a.
а) Могли ли на доске быть написаны какие-то два числа из чисел 4, 5, 6?
б) Среди написанных на доске чисел есть 5. Может ли N быть равным 7?
в) Найдите наибольшее значение N.
а) Нет, не может. Если на доске числа 4 и 5, то их разность равна 1. Но 5 делится на 1 – противоречие.
Аналогично, если на доске числа 5 и 6.
Если на доске числа 4 и 6, то их разность равна 2, но 4 делится на 2 – противоречие.
б) Если два числа дают одинаковые остатки при делении на число р, то их разность делится на р.
Остатки от деления на 5 – это 1, 2 . 4, всего 4 остатка. Поскольку на доске 7 чисел, среди них найдутся два, дающие одинаковые остатки от деления на 5. Их разность делится на 5, что противоречит условию.
в) Из пункта (а) мы получили, что среди чисел на доске не может быть подряд идущих (например, 4 и 5 не могут быть на доске).
Если на доске только нечетные числа, разность любых двух из них четна, и ни одно из них не делится на эту разность.
От 1 до 27 ровно 14 нечетных чисел.
Есть еще одно условие: разность любых двух из них не должна делиться ни на одно из этих чисел.
Пусть на доске не менее 14 нечетных чисел. Если на доске есть число а ≤ 9, то хотя бы два из написанных чисел дают одинаковый остаток при делении на а, следовательно, их разность делится на а – противоречие.
Аналогично, если на доске не менее 10 чисел.
Поскольку все числа не превосходят 27, среди этих 10 чисел должно быть число а ≤ 9.
Но тогда не менее двух чисел на доске дают одинаковые остатки от деления на а, значит, их разность делится на а – противоречие. Значит, на доске не более 9 чисел. Это оценка.
Приведем пример для 9 чисел на доске.
11, 13, 15, 17, 19, 21, 23, 25, 27.
Разность любых двух из них четна и не делится ни на одно из этих чисел. Также ни одно из чисел не делится на разность каких-либо двух из них.
Ответ: а) нет, не может; б) нет, не может; в) 9.
Подробно о том, как решать задачи на числа и их свойства, читайте здесь. Это целый раздел сайта, посвященный нестандартным задачам.
А если хотите сами так же легко их решать – приходите на мой онлайн-курс и я вас научу.
Спасибо за то, что пользуйтесь нашими материалами. Информация на странице «Задача 18 на числа и их свойства на ЕГЭ-2022 по математике» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам. Чтобы успешно сдать необходимые и поступить в высшее учебное заведение или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из данного раздела.
Публикация обновлена: 05.10.2023
Сколько среди целых чисел от 1 до 50 включительно таких которые записаны только нечетными цифрами
Дан массив, состоящий из целых чисел. Нумерация элементов начинается с 0. Напишите программу, которая выведет элементы массива, номера которых четны (0, 2, 4. ).
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 100\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.
Выходные данные
Необходимо вывести все элементы массива с чётными номерами.
Входные данные
6 4 5 3 4 2 3
Выходные данные
4 3 2
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Дан массив, состоящий из целых чисел. Напишите программу, которая выводит те элементы массива, которые являются чётными числами.
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 100\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.
Выходные данные
Необходимо вывести все четные элементы массива (то есть те элементы, которые являются четными числами).
Входные данные
5 1 2 3 4 5
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Дан массив, состоящий из целых чисел. Напишите программу, которая подсчитывает количество положительных чисел среди элементов массива.
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 10000\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.
Выходные данные
Необходимо единственное число — количество положительных элементов в массиве.
Входные данные
5 1 2 3 -1 -4
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Дан массив, состоящий из целых чисел. Напишите программу, которая подсчитает количество элементов массива, больших предыдущего (элемента с предыдущим номером).
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 10000\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.
Выходные данные
Необходимо вывести единственное число — количество элементов массива, больших предыдущего.
Входные данные
5 1 2 3 4 5
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Дан массив, состоящий из целых чисел. Напишите программу, которая определяет, есть ли в массиве пара соседних элементов с одинаковыми знаками.
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 10000\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел не равных 0.
Выходные данные
Необходимо вывести слово YES, если существует пара соседних элементов с одинаковыми знаками. В противном случае следует вывести слово NO.
Входные данные
5 1 -3 4 -2 1
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Дан массив, состоящий из целых чисел. Напишите программу, которая в данном массиве определит количество элементов, у которых два соседних и, при этом, оба соседних элемента меньше данного.
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 100\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.
Выходные данные
Необходимо вывести количество элементов массива, у которых два соседа и которые при этом строго больше обоих своих соседей.
Входные данные
5 1 2 3 4 5
Выходные данные
Входные данные
5 1 5 1 5 1
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Напишите программу, которая переставляет элементы массива в обратном порядке без использования дополнительного массива. Программа должна считать массив, поменять порядок его элементов, затем вывести результат (просто вывести элементы массива в обратном порядке – недостаточно!)
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 35\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.
Выходные данные
Необходимо вывести массив, полученный после перестановки элементов.
Входные данные
6 4 5 3 4 2 3
Выходные данные
3 2 4 3 5 4
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Напишите программу, которая переставляет соседние элементы массива (1-й элемент поменять с 2-м, 3-й с 4-м и т.д. Если элементов нечетное число, то последний элемент остается на своем месте).
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 35\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.
Выходные данные
Необходимо вывести массив, полученный после перестановки элементов.
Входные данные
6 4 5 3 4 2 3
Выходные данные
5 4 4 3 3 2
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Напишите программу, которая циклически сдвигает элементы массива вправо (например, если элементы нумеруются, начиная с нуля, то 0-й элемент становится 1-м, 1-й становится 2-м, . последний становится 0-м, то есть массив превращается в массив ).
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 35\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.
Выходные данные
Необходимо вывести массив, полученный после сдвига элементов.
Входные данные
6 4 5 3 4 2 3
Выходные данные
3 4 5 3 4 2
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Вводится массив, состоящий из целых чисел. Найти наибольшее среди них.
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 35\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.
Выходные данные
Необходимо вывести значение наибольшего элемента в массиве.
Входные данные
3 1 2 3
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Дан массив, состоящий из целых чисел. Известно, что числа упорядочены по неубыванию (то есть каждый следующий элемент не меньше предыдущего). Напишите программу, которая определит количество различных чисел в этом массиве.
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 100\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел, находящихся в пределах от \(-2^\) до \(2^-1\)
Выходные данные
Необходимо вывести единственное число — количество различных чисел в массиве.
Входные данные
5 1 1 1 1 1
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Измените регистр символа, если он был латинской буквой: сделайте его заглавным, если он был строчной буквой и наоборот. Для этого напишите отдельную функцию, меняющую регистр символа.
Входные данные
Задан единственный символ C.
Выходные данные
Необходимо вывести получившийся символ.
Входные данные
Выходные данные
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Входные данные
В единственной строке входных данных записано натуральное число n (1≤n ≤ 45).
Выходные данные
Вывести одно число Fn
Входные данные
Выходные данные
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Переведите натуральное число из двоичной системы в десятичную (в двоичном числе не более 10 цифр).
Входные данные
Вводится натуральное число, записанное в двоичной системе.
Выходные данные
Выведите число, записанное в десятичной системе.
Входные данные
1001
Выходные данные
Входные данные
Выходные данные
Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2008, Задача B ]
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Лавочки в парке устроены следующим образом. Несколько одинаковых кубических гранитных блоков ставятся в ряд, а на них кладется гранитная плита (см. рисунок). Архитектор-модернист решил, что будет интереснее, если у всех лавочек расположение гранитных блоков-ножек будет разным (и не обязательно симметричным). При этом они располагаются так, чтобы плита не падала: для этого достаточно, чтобы и слева, и справа от центра плиты был хотя бы один гранитный блок или его часть (в частности, если центр плиты приходится на середину какого-нибудь блока, то и слева, и справа от центра плиты находится часть блока, и плита не падает).
Грабители обнаружили, что можно по одному вытаскивать гранитные блоки, находящиеся с краю (как слева, так и справа). Они хотят вытащить из-под лавочки как можно больше блоков так, чтобы она при этом не упала (передвигать оставшиеся блоки нельзя). Определите, какие блоки они должны оставить.
Входные данные
В первой строке входных данных содержатся два числа: L — длина лавочки и K — количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.
Во второй строке следуют K различных целых неотрицательных чисел, задающих положение каждой ножки. Положение ножки определяется расстоянием от левого края плиты до левого края ножки (ножка — это куб размером 1×1×1). Ножки перечислены слева направо (то есть начиная с ножки с меньшим расстоянием до левого края).
Выходные данные
Требуется перечислить ножки, которые грабителям нужно оставить. Для каждой ножки нужно выдать ее положение, как оно задано во входных данных. Ножки следует перечислять слева направо, в том порядке, в котором они встречаются во входных данных.
Пример
| Входные данные | Выходные данные |
| 5 2 0 2 |
2 |
| 13 4 1 4 8 11 |
4 8 |
| 14 6 1 6 8 11 12 13 |
6 8 |
Второй пример соответствует лавочке на рисунке.
Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2006, Задача B ]
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.
Входные данные
Сначала вводится число \(N\) — количество элементов исходной последовательности (1 ≤ \(N\) ≤ 100). Далее идут \(N\) чисел — элементы этой последовательности, натуральные числа от 1 до 9.
Выходные данные
Выведите сначала число \(M\) — минимальное количество элементов, которое надо дописать к последовательности, а потом \(M\) чисел (каждое — от 1 до 9) — числа, которые надо дописать к последовательности.
Входные данные
9 1 2 3 4 5 4 3 2 1
Выходные данные
Входные данные
5 1 2 1 2 2
Выходные данные
3 1 2 1
Входные данные
5 1 2 3 4 5
Выходные данные
4 4 3 2 1
Источники: [ Командные олимпиады, ВКОШП, 2002, Задача G ]
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Требуется сгенерировать перестановку, которая при применении к массиву 1..N возвращает его в исходное состояние за наибольшее количество применений.
Ваня и Петя играют в следующую игру. Ваня пишет на бумаге какую-либо перестановку чисел от 1 до \(N\) (то есть выписывает все числа от 1 до \(N\) в некотором порядке) и расставляет на столе в ряд \(N\) предметов. После этого Петя переставляет предметы в соответствии с Ваниной перестановкой. А именно, Петя выполняет следующие действия: если i-ое число в Ваниной перестановке равно \(a_i\), то Петя ставит предмет, который стоит на i-ом месте, на место с номером \(a_i\).
Обозначим предметы числами от 1 до \(N\). Тогда начальное расположение предметов можно обозначить последовательностью чисел (1, 2, . \(N\)). К примеру, если \(N\) = 5, то начальное расположение предметов есть (1, 2, 3, 4, 5). Пусть Ваня написал перестановку . Это значит, что после перемещения предметов они окажутся расставлены в следующем порядке: (5, 1, 4, 3, 2).
Однако, переставив предметы, Петя не останавливается на достигнутом и вновь переставляет их в соответствии с Ваниной перестановкой. Снова, если i-ое число в Ваниной перестановке равно \(a_i\), то Петя ставит предмет, который стоит на i-ом месте на место с номером \(a_i\). Так, если в приведенном выше примере повторно применить перестановку, предметы окажутся расположены в следующем порядке: (2, 5, 3, 4, 1).
Таким образом, Петя переставляет предметы в соответствии с Ваниной перестановкой, пока их расположение не окажется таким же, как исходное. В нашем примере Пете потребуется сделать еще 4 действия, порядок предметов после каждого из них будет следующим: (1, 2, 4, 3, 5), (5, 1, 3, 4, 2), (2, 5, 4, 3, 1), (1, 2, 3, 4, 5). Всего Пете потребовалось применить перестановку 6 раз.
Добрый Ваня хочет, чтобы Пете пришлось выполнить как можно больше действий. Помогите ему выбрать соответствующую перестановку.
Входные данные
Вводится единственное целое число \(N\) — количество предметов (1
ограничение по памяти на тест
64 megabytes
Есть куб состоящий из единичных кубиков. Заданы наборы кубиков, проткнутые спицей вдоль одной из осей. Требуется подсчитать количество оставшихся кубиков.
Петя склеил из \(N^3\) единичных кубиков большой куб размером \(N\) × \(N\) × \(N\). Устав от этой сложной работы, он отправился спать, а утром, проснувшись, с ужасом обнаружил, что его младший брат Ваня \(K\) раз проткнул куб спицей.
При этом Ваня действовал очень аккуратно, каждый раз установив конец спицы точно в центр грани какого-нибудь граничного единичного кубика, он протыкал куб параллельно соответствующей оси координат, при этом целый ряд из \(N\) кубиков оказывался испорчен.
Немного успокоившись после этого тяжелого потрясения, Петя заинтересовался, сколько кубиков в его творении осталось неповрежденными. Помогите ему ответить на этот сложный вопрос.
Входные данные
В первой строке вводятся числа \(N\) и \(K\) (1
Сколько среди целых чисел от 1 до 50 включительно таких которые записаны только нечетными цифрами
Дан массив, состоящий из целых чисел. Напишите программу, которая выводит те элементы массива, которые являются чётными числами.
Входные данные
Сначала задано число \(N\) — количество элементов в массиве (\(1 \le N \le 100\)). Далее через пробел записаны \(N\) чисел — элементы массива. Массив состоит из целых чисел.
Выходные данные
Необходимо вывести все четные элементы массива (то есть те элементы, которые являются четными числами).
Входные данные
5 1 2 3 4 5
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Выведите все точные квадраты натуральных чисел, не превосходящие данного числа N.
Входные данные
Задано единственное целое число N
Выходные данные
Необходимо вывести все точные квадраты натуральных чисел, не превосходящие данного числа N.
Входные данные
Выходные данные
1 4 9
Дано натуральное число N. Напишите функцию int SumOfDigits (int n) (C/C++), function SumOfDigits (n:longint):integer (Pascal), вычисляющую сумму цифр числа N.
Входные данные
Задано единственное число N
Выходные данные
Необходимо вывести сумму цифр числа N.
Входные данные
Выходные данные
Дано натуральное число N. Напишите функцию int NumberOfZeroes(int n) (C/C++/Java), function NumberOfZeroes(n: longint): integer (Pascal), определяющую количество нулей среди всех цифр числа N.
Входные данные
Задано единственное число N
Выходные данные
Необходимо вывести количество нулей среди всех цифр числа N.
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Дано натуральное число N. Напишите функцию int MinDigit (int n) (C/C++), function MinDigit (n:longint):integer (Pascal) и int MaxDigit (int n) (C/C++), function MaxDigit (n:longint):integer (Pascal), определяющую наименьшую и наибольшую цифры данного числа.
Входные данные
Задано единственное число N
Выходные данные
Необходимо вывести наименьшую и наибольшую цифры данного числа через пробел.
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Дано натуральное число N. Выведите его представление в двоичном виде в обратном порядке.
Входные данные
Задано единственное число N
Выходные данные
Необходимо вывести требуемое представление числа N.
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Напишите функцию int reverse(int n) (C/C++), function reverse (n:integer):integer (Pascal), которая переставляет цифры числа в обратном порядке .
Входные данные
Задано единственное число N
Выходные данные
Необходимо вывести цифры данного числа в обратном порядке.
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
По данному натуральному числу N найдите сумму чисел 1+1/1!+1/2!+1/3!+. +1/N!. Количество действий должно быть пропорционально N.
Входные данные
Задано единственное число N
Выходные данные
Необходимо вывести результат вычисления в виде действительного числа c точностью до 5 знаков после запятой.
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Входные данные
На вход программы поступает сначала число N (1N<=100), а затем N пар чисел. Первое число каждой пары – натуральное, не превышающее 30000. Второе число каждой пары – 0 или 1.
Выходные данные
Требуется найти пары, в которых второе число равно 1, а из всех таких пар выбрать ту, в которой первое число максимально (если таких пар несколько, выберите любую из них).
Программа должна вывести номер выбранной пары. Если пар, у которых второе число равно 1, нет, то выведите -1 .
Входные данные
3 30000 1 2 1 3 1
Выходные данные
300 1 0
Входные данные
4 25 1 70 1 100 0 3 1
Выходные данные
235 0 1 5
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
| Максимальное время работы на одном тесте: | 5 секунд |
Входные данные
Сначала вводится число N (1 N N чисел от 1 до 100 – элементы массива A[i]. Далее записаны два числа q и w (от 1 до N, не обязательно различные).
Требуется все элементы, которые равны A[q], сделать равными A[w]. Постарайтесь сначала считать данные, потом сделать то, что требуется, и только потом вывести результат (а не делать преобразование на этапе вывода). Постарайтесь не пользоваться допoлнительными массивами.
Выходные данные
Выведите N чисел — элементы массива A[i] после преобразования.
Входные данные
5 1 4 2 2 5 3 2
Выходные данные
1 4 4 4 5
ограничение по времени на тест
ограничение по памяти на тест
128 megabytes
Напишите программу, которая определяет, сколько раз встречается заданное число x в данном массиве.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива.
Во второй строке вводятся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).
В третьей строке содержится одно целое число x , не превосходящее по модулю 1000.
Выходные данные
Вывести одно число – сколько раз встречается x в данном массиве.
Входные данные
5 1 2 3 4 5 3
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Вася записывает в клетки квадратной таблицы NxN натуральные числа по порядку, сначала заполняя первую строку слева направо, затем вторую и т.д. (см. рисунок слева). Петя заполняет такую же таблицу, расставляя числа сначала в первый столбец сверху вниз, затем во второй столбец и т.д.
При этом оказалось, что некоторые числа и Вася, и Петя записали в одну и ту же клетку (например, число 6 записано во вторую строку второго столбца обеих таблиц).
Вам требуется написать программу, выводящую все числа, которые в обеих таблицах записаны в одних и тех же клетках.
Входные данные
Вводится одно число — размер таблицы.
Выходные данные
Программа должна вывести все числа, которые в обеих таблицах стоят на одном и том же месте, в порядке возрастания, через пробел.
Размер таблицы — натуральное число, не превосходящее 100.
Входные данные
Выходные данные
1 6 11 16
Входные данные
Выходные данные
Дан набор из N отрезков различной длины. Сколькими способами можно выбрать из этих отрезков три, из которых можно составить (невырожденный) треугольник?
Входные данные
Сначала вводится количество отрезков, затем длины этих отрезков (еще N чисел).
Выходные данные
Программа должна вывести одно число — искомое количество способов.
Количество отрезков — не менее 3 и не более 20. Длина каждого отрезка — натуральное число, не превосходящее 1000. Все отрезки имеют разную длину.
Входные данные
4 1 3 2 4
Выходные данные
Входные данные
3 10 100 1000
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
По данному натуральному n вычислите сумму 1 2 +2 2 +. +n 2 .
Входные данные
Вводится единственное натуральное число n, не превосходящее 100
Выходные данные
Необходимо вывести вычисленную сумму.
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
По данному натуральному n вычислите значение n!.
Входные данные
Вводится единственное число n.
Выходные данные
Необходимо вывести значение n!.
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
По данному действительному числу a и целому неотрицательному n вычислите величину a n .
Входные данные
Вводятся 2 числа — a и n.
Выходные данные
Необходимо вывести значение a n .
Входные данные
Выходные данные
По данному действительному числу a и натуральному n вычислите сумму 1+a+a 2 +. +a n , не используя формулу суммы геометрической прогрессии. Время работы программы должно быть пропорционально n.
Входные данные
Вводятся 2 числа — a и n.
Выходные данные
Необходимо вывести значение суммы.
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
По данному числу n вычислите сумму 1+1/2 2 +1/3 2 +. +1/n 2 .
Входные данные
Вводится одно число n, не превосходящее 100000.
Выходные данные
Необходимо вывести значение суммы.
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
По данному числу n вычислите сумму 4(1-1/3+1/5-1/7+. +(-1) n /(2n+1)).
Входные данные
Вводится одно число n, не превосходящее 100000.
Выходные данные
Необходимо вывести значение выражения.
Входные данные
Выходные данные
2.66667
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Входные данные
Вводятся целые числа a и b. Гарантируется, что a не превосходит b
Выходные данные
Выведите (через пробел) все четные числа от a до b (включительно).
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Входные данные
Выходные данные
Выведите все числа на отрезке от a до b, дающие остаток c при делении на d. Если таких чисел не существует, то ничего выводить не нужно.
Входные данные
2 5 0 2
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Входные данные
Вводятся целые числа a и b. Гарантируется, что a не превосходит b.
Выходные данные
Выведите все числа на отрезке от a до b, являющиеся полными квадратами. Если таких чисел нет, то ничего выводить не нужно.
Входные данные
Выходные данные
Выведите все натуральные делители числа x в порядке возрастания (включая 1 и само число).
Входные данные
Вводится натуральное число x
Выходные данные
Выведите все делители числа x
Входные данные
Выходные данные
1 2 4 8 16 32
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Подсчитайте количество натуральных делителей числа x (включая 1 и само число; \(x \le 2 * 10^9\)).
Входные данные
Вводится натуральное число x.
Выходные данные
Выведите единственное число — количество делителей числа x.
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Вычислите сумму данных 100 натуральных чисел.
Входные данные
Вводятся 100 чисел, сумму которых необходимо посчитать.
Выходные данные
Программа должна вывести единственное число — полученную сумму.
Вычислите сумму данных N натуральных чисел.
Входные данные
Вводится число N, а затем N чисел, сумму которых необходимо вычислить.
Выходные данные
Выведите единственное число — сумму введенных чисел.
Входные данные
3 9 5 1
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Входные данные
Вводится число N, а затем N чисел.
Выходные данные
Подсчитайте и выведите, сколько среди данных N чисел нулей.
Входные данные
3 1 2 3
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Подсчитайте, сколько среди данных N чисел нулей, положительных чисел, отрицательных чисел.
Входные данные
Вводится число N, а затем N целых чисел.
Выходные данные
Необходимо вывести сначала число нулей, затем число положительных и отрицательных чисел.
Входные данные
5 28 0 0 0 0
Выходные данные
4 1 0
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Вычислите N! («эн-факториал») – произведение всех натуральных чисел от 1 до N ( N!=1∙2∙3∙…∙ N ).
Входные данные
Вводится единственное число N – натуральное, не превосходит 12.
Выходные данные
Выведите полученное значение N!
Входные данные
Выходные данные
Напишите программу, вычисляющую 2 N .
Входные данные
Вводится целое неотрицательное число N, которое не превосходит 30.
Выходные данные
Выведите число 2 N .
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Входные данные
Вводится натуральное число N, которое не превосходит 30.
Выходные данные
Вычислите 1+2+2 2 +2 3 +…+2 N .
Входные данные
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Спонсоры олимпиады предоставили оргкомитету N призов для победителей олимпиады. Стоимости всех призов различны и выражаются натуральными числами от 1 до N
Перед оргкомитетом возникла задача распределить эти призы между K участниками так, чтобы все участники получили одинаковое количество призов, и, кроме того, суммарные стоимости призов, полученных разными участниками, совпадали.
Гарантируется, что N делится на K
Входные данные
На вход программы поступают два числа: N и K (1≤
ограничение по памяти на тест
64 megabytes
Уставшие от необычно теплой зимы, москвичи решили узнать, действительно ли это самая длинная оттепель за всю историю наблюдений за погодой. Они обратились к синоптикам, а те, в свою очередь, занялись исследованиями статистики за прошлые годы. Их интересует, сколько дней длилась самая длинная оттепель.
Оттепелью они называют период, в который среднесуточная температура ежедневно превышала 0 градусов Цельсия. Напишите программу, помогающую синоптикам в работе.
Входные данные
Cначала вводится число \(N\) – общее количество рассматриваемых дней (1 ≤ \(N\) ≤ 100). В следующей строке задается \(N\) целых чисел, разделенных пробелами. Каждое число – среднесуточная температура в соответствующий день. Температуры – целые числа, принадлежащие диапазону от –50 до 50.
Выходные данные
Требуется вывести одно число – длину самой продолжительной оттепели, то есть наибольшее количество последовательных дней, на протяжении которых среднесуточная температура превышала 0 градусов. Если температура в каждый из дней была неположительной, выведите 0.
Пояснения к примерам
1) Рассматриваются 6 дней. Самая продолжительная оттепель была на 4-й и 5-й день (50 и 10 градусов соответственно)
2) Самая продолжительная оттепель была в первые 4 дня
3) Дней с положительной температурой не было
Входные данные
6 -20 30 -40 50 10 -10
Выходные данные
Входные данные
8 10 20 30 1 -10 1 2 3
Выходные данные
Входные данные
5 -10 0 -10 0 -10
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Требуется сравнить два 100-значных числа.
Входные данные
На вход программы поступают два 100-значных натуральных числа \(A\) и \(B\). Каждое число вводится на отдельной строке.
Выходные данные
Если \(A\)>\(B\), то выведите “>” (один символ без кавычек).
Если \(A\)
ограничение по памяти на тест
64 megabytes
Сколько понадобится парт, чтобы рассадить \(A\) школьников, если за одну парту можно посадить одного или двух человек? За каждой партой должен сидеть хотя бы один человек. Укажите все варианты.
Входные данные
Вводится одно натуральное число — \(A\) ( 1 ≤ \(A\) ≤ 10000)
Выходные данные
Выведите упорядоченный по возрастанию набор чисел – все возможные значения количества необходимых парт.
Входные данные
Выходные данные
3 4 5 6
В некоторой сверхсекретной лаборатории изучаются физические возможности животных. Любой живой организм нуждается в трех компонентах пищи – белках, жирах и углеводах. Известен набор продуктов, имеющийся в распоряжении лаборатории, и меню животных – сколько единиц каждого продукта они получают. Известно также, сколько белков, жиров и углеводов необходимо для нормальной жизнедеятельности животного. Необходимо определить, получает ли животное достаточное количество питательных веществ. Известно, что животному требуется в сутки \(X\) белков, \(Y\) жиров и \(Z\) углеводов.
Известно также, что всего животное получает в сутки \(N\) продуктов питания, и для каждого из них известны \(A_i\), \(B_i\), \(C_i\) и \(Q_i\) – соответственно, энергетическая ценность единицы продукта в белках, жирах и углеводах и количество единиц этого продукта. Все числа – действительные, заданные с точностью до 5 знаков после запятой.
Входные данные
На первой строке входных данных записаны числа \(X\) , \(Y\) и \(Z\) . На второй строке записано число \(N\). Далее на \(N\) строках записаны, соответственно, \(A_i\), \(B_i\), \(C_i\) и \(Q_i\).
Выходные данные
Выведите YES , если данный пищевой рацион является достаточным по всем параметрам, и NO в противном случае.
Входные данные
1.0 1.0 1.0 3 1 0 0 1 0 0.5 0 2 0 0 0.25 4
Выходные данные
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Если в Microsoft Excel выделить две соседние клетки с числами, а потом “потянуть” за правый нижний уголок мышью, то следующие клетки заполнятся числами, образуя арифметическую прогрессию.
Входные данные
Вводятся сначала два натуральных числа, по модулю не превышающие 100 – числа в первых двух клетках, а затем число N (натуральное, 2 ≤ N ≤ 100) – общее количество чисел в арифметической прогрессии (включая два первых числа). Числа вводятся через пробел.
Выходные данные
Выведите N членов арифметической прогрессии, разделяя их пробелом.
Входные данные
2 5 8
Выходные данные
2 5 8 11 14 17 20 23
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Колоду карт раздают по кругу, по одной карте каждому за раз, пока колода не кончится. Известен порядок карт в колоде. С кого должен начинать сдающий, чтобы первый игрок получил себе как можно больше тузов?
Входные данные
В первой строке вводятся два числа: количество игроков и количество карт в колоде (оба числа натуральные и не превосходят 100, количество карт делится на количество игроков).
Во второй строке через пробел перечислены достоинства карт в том порядке, в котором они идут в колоде (6 – шестерка, 7 – семерка, 8 – восьмерка, 9 – девятка, 10 – десятка, 11 – валет, 12 – дама, 13 – король, 14 – туз). В колоде может быть произвольное число карт каждого достоинства.
Выходные данные
Выведите одно число – номер игрока, с которого следует начинать сдавать, чтобы первый игрок получил как можно больше тузов (игроки нумеруются числами 1, 2, 3, . ; сдача происходит по возрастанию номеров начиная с некоторого до последнего, и затем продолжается с первого). Если вариантов ответа несколько, выведите любой из них.
Входные данные
5 10 9 9 9 14 8 7 11 6 14 6
Выходные данные
Входные данные
3 3 14 14 14
Выходные данные
Источники: [ Командные олимпиады, Турнир Архимеда, 2008, Задача C ]
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Вводится натуральное число. Требуется разделить запятыми тройки его цифр (считая справа).
Входные данные
Вводится одно натуральное число, не превышающее 10 100 .
Выходные данные
Вывести то же число, разделяя тройки цифр запятыми.
Входные данные
1000
Выходные данные
1,000
Входные данные
12345678
Выходные данные
12,345,678
Входные данные
Выходные данные
Источники: [ Личные олимпиады, Олимпиады сайта, 2009, Задача B ]
Вместо того чтобы делать уроки, Петя смотрел футбольный матч и записывал счет, который показывался на табло, после каждого забитого гола.
Например, у него могла получиться такая запись:
После этого он сложил все записанные числа : 1+0+1+1+1+2+2+2+2+3=15.
По сумме, получившейся у Васи, определите, сколько всего мячей было забито в матче.
Входные данные
Вводится одно натуральное число, не превосходящее 1000 – сумма, полученная Васей.
Выходные данные
Выведите одно число – общее количество забитых мячей.
Входные данные
Выходные данные
Входные данные
Выходные данные
Источники: [ Личные олимпиады, Олимпиады сайта, 2009, Задача C ]
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Вася хочет узнать, какую оценку он получит в четверти по информатике. Учитель придерживается следующей системы: вычисляется среднее арифметическое всех оценок в журнале, и ставится ближайшая целая оценка, не превосходящая среднего арифметического.
При этом если у школьника есть двойка, а следующая за ней оценка – не двойка, то двойка считается закрытой, и при вычислении среднего арифметического не учитывается.
Входные данные
Вводится десять натуральных чисел от 2 до 5 через пробел – оценки Васи.
Выходные данные
Выведите натуральное число (от 2 до 5) – ег о четвертную оценку.
Входные данные
2 5 2 5 2 5 2 5 2 5
Выходные данные
Входные данные
2 2 2 2 2 2 2 2 2 5
Выходные данные
Входные данные
5 5 5 5 5 5 5 5 5 2
Выходные данные
Источники: [ Личные олимпиады, Олимпиады сайта, 2009, Задача G ]
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Есть кучка спичек. Играют двое. Сначала первый берет из кучки любое количество спичек от одной до пяти. Затем то же самое делает второй. Затем первый берет столько спичек, сколько есть у второго, затем второй берет столько спичек, сколько есть у первого и т. д. Выигрывает тот, кто не может сделать хода. Кто выигрывает при правильной игре?
Входные данные
Вводится одно число, не превосходящее 1000 – изначальное количество спичек.
Выходные данные
Вывести число 1, если первый игрок может выиграть независимо от действий второго, или число 2, если второй может выиграть независимо от действий первого. В остальных случаях вывести 0.
Входные данные
Выходные данные
Требуется заполнить массив числами от 2 до N+1 так, чтобы каждое из них делилось на индекс элемента (нумерация элементов с 1).
Требуется заполнить N элементов массива, пронумерованных числами от 1 до N ( A [1]… A [ N ]), натуральными числами от 2 до N +1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A [ i ] делилось бы на i ).
Напишите программу, которая для заданного N заполнит массив согласно описанному правилу.
Входные данные
Вводится одно натуральное число N (1≤ N ≤1000).
Выходные данные
Выведите заполненный массив. Если вариантов заполнения несколько, выведите любой из них. Если заполнить массив невозможно, выведите одно число 0.
Источники: [ Личные олимпиады, Олимпиады сайта, 2009, Задача M ]
Даны две таблицы. В первой записана информация о школьниках (фамилия, имя и номер школы), а во второй – информация о результатах экзамена (фамилия, имя школьника и его оценка за экзамен). Требуется составить сводную таблицу, в которой будет указан номер школы и средняя оценка за экзамен всех учеников из этой школы (средняя оценка – это среднее арифметическое всех оценок, округленное до ближайшего сверху числа).
Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 50 – количество школьников.
В следующих N строках вводится информация о школьниках в формате
Фамилия Имя Номер_Школы
Фамилия и имя не содержат пробелов, а номер школы – натуральное число, не превосходящее 2007.
В следующих N строках вводится информация об экзамене в формате
Фамилия Имя Оценка
Порядок учеников может быть иным, но имена и фамилии школьников такие же, как в предыдущем списке. Оценка – натуральное число от 2 до 5.
Гарантируется, что любые два школьника отличаются именем или фамилией.
Выходные данные
Вывести список, отсортированный по возрастанию номера школы, каждая строка которого имеет формат
Входные данные
4 Pete Ivanov 2 Vasya Petrov 2007 Nic Vasiliev 2 Ivan Nikolaev 2007 Ivan Nikolaev 5 Nic Vasiliev 4 Pete Ivanov 3 Vasya Petrov 5
Выходные данные
2 4 2007 5
Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2003, Задача A ]
ограничение по времени на тест
ограничение по памяти на тест
64 megabytes
Решение каждой задачи заочного тура проверяется на наборе заранее заготовленных тестов. По результатам работы программы на каждом тесте участнику либо начисляются баллы за этот тест (когда программа выдала правильный ответ), либо не начисляются (когда во время работы программы произошли ошибки или выданный ответ не верен). Тесты могут иметь разную стоимость.
Дополнительные баллы начисляются участнику, если его программа прошла все тесты.
Участник может исправлять свое решение, и посылать его на проверку повторно (при этом решение проверяется на том же наборе тестов). При этом за каждую попытку из количества набранных по задаче баллов вычитается штраф, который равен 0 при 1-й попытке, а при каждой следующей возрастает на 2 (то есть 2 при второй, 4 — при третьей, 6 — при четвертой и т.д.).
Из баллов, полученных участником за каждую из попыток (с учетом начисленных штрафов), выбирается максимальный результат, который и засчитывается как результат данного участника по этой задаче. Это нужно, в частности, для того, чтобы последующие попытки не ухудшали уже полученный участником результат по задаче.
Например, если участник делает первую попытку и набирает 10 баллов, его результат по задаче равен 10 баллов. Пусть на второй попытке участник посылает решение, которое набирает 8 баллов. С учетом штрафа за эту попытку участник имеет 6 баллов, однако результат команды по задаче остается равным 10. Пусть с 3-й попытки решение набрало 20 баллов, тогда (с учетом штрафа) результат участника по задаче становится равен 16 баллам. Наконец, пусть с 4-й попытки решение проходит все тесты, тогда участник получает сумму баллов за все тесты, плюс призовые баллы за прохождение всех тестов, минус 6 баллов штрафа (если, конечно, эта величина не меньше 16 баллов, которые уже были у данного участника).
Напишите программу, которая определяет результат данного участника по этой задаче.
Входные данные
Во входном файле записано сначала число N — количество тестов, на которых проверяются решения данной задачи (1≤ N ≤100). Далее идет N натуральных чисел, не превышающих 100, — баллы, которые начисляются за прохождение каждого из тестов. Далее идет целое число из диапазона от 0 до 100 — количество баллов, которое дополнительно начисляется за прохождение всех тестов.
Далее идет натуральное число M — количество попыток сдачи задачи (1≤ M ≤100). После чего идет M наборов по N чисел в каждом, задающих результаты проверки каждой из M попыток сдачи задачи на тестах. 0 обозначает, что соответствующий тест не пройден, 1 — пройден.
Выходные данные
В выходной файл выведите M чисел. i -ое число должно соответствовать результату участника после совершения им первых i попыток.
Сумма и произведение цифр числа
Одной из часто используемых задач для начинающих изучать программирование является нахождение суммы и произведения цифр числа. Число может вводиться с клавиатуры или генерироваться случайно. Задача формулируется так:
Дано число. Найти сумму и произведение его цифр.
Например, сумма цифр числа 253 равна 10-ти, так как 2 + 5 + 3 = 10. Произведение цифр числа 253 равно 30-ти, так как 2 * 5 * 3 = 30.
В данном случае задача осложняется тем, что количество разрядов числа заранее (на момент написания программы) не известно. Это может быть и трехзначное число, как в примере выше, и восьмизначное, и однозначное.
Обычно предполагается, что данная задача должна быть решена арифметическим способом и с использованием цикла. То есть с заданным число должны последовательно выполняться определенные арифметические действия, позволяющие извлечь из него все цифры, затем сложить их и перемножить.
При этом используются операции деления нацело и нахождения остатка. Если число разделить нацело на 10, произойдет «потеря» последней цифры числа. Например, 253 ÷ 10 = 25 (остаток 3). С другой стороны, эта потерянная цифра есть остаток от деления. Получив эту цифру, мы можем добавить ее к сумме цифр и умножить на нее произведение цифр числа.
Пусть n – само число, suma – сумма его цифр, а mult – произведение. Тогда алгоритм нахождения суммы и произведения цифр можно словесно описать так:
- Переменной suma присвоить ноль.
- Переменной mult присвоить единицу. Присваивать 0 нельзя, так как при умножении на ноль результат будет нулевым.
- Пока значение переменной n больше нуля повторять следующие действия:
- Найти остаток от деления значения n на 10, то есть извлечь последнюю цифру числа.
- Добавить извлеченную цифру к сумме и увеличить на эту цифру произведение.
- Избавиться от последнего разряда числа n путем деления нацело на 10.
В языке Python операция нахождения остатка от деления обозначается знаком процента — % . Деление нацело — двумя слэшами — // .
Код программы на языке Python
n = int(input()) suma = 0 mult = 1 while n > 0: digit = n % 10 suma = suma + digit mult = mult * digit n = n // 10 print("Сумма:", suma) print("Произведение:", mult)
253 Сумма: 10 Произведение: 30
Изменение значений переменных можно записать в сокращенном виде:
. while n > 0: digit = n % 10 suma += digit mult *= digit n //= 10 .
Приведенная выше программа подходит только для нахождения суммы и произведения цифр натуральных чисел, то есть целых чисел больше нуля. Если исходное число может быть любым целым, следует учесть обработку отрицательных чисел и нуля.
Если число отрицательное, это не влияет на сумму его цифр. В таком случае достаточно будет использовать встроенную в Python функции abc , которая возвращает абсолютное значение переданного ей аргумента. Она превратит отрицательное число в положительное, и цикл while с его условием n > 0 будет работать как и прежде.
Если число равно нулю, то по логике вещей сумма его цифр и их произведение должны иметь нулевые значения. Цикл срабатывать не будет. Поскольку исходное значение mult — это 1, следует добавить проверку на случай, если заданное число — это ноль.
Программа, обрабатывающая все целые числа, может начинаться так:
n = abs(int(input())) suma = 0 mult = 1 if n == 0: mult = 0 .
Заметим, если в самом числе встречается цифра 0 (например, 503), то произведение всех цифр будет равно нулю. Усложним задачу:
Вводится натуральное число. Найти сумму и произведение цифр, из которых состоит это число. При этом если в числе встречается цифра 0, то ее не надо учитывать при нахождении произведения.
Для решения такой задачи в цикл добавляется проверка извлеченной цифры на ее неравенство нулю. Делать это надо до умножения на нее значения переменной-произведения.
n = int(input()) suma = 0 mult = 1 while n > 0: digit = n % 10 if digit != 0: suma += digit mult *= digit n = n // 10 print("Сумма:", suma) print("Произведение:", mult)
Обратим внимание, что заголовок условного оператора if digit != 0: в Python можно сократить до просто if digit: . Потому что 0 — это False . Все остальные числа считаются истиной.
Приведенный выше математический алгоритм нахождения суммы и произведения цифр числа можно назвать классическим, или универсальным. Подобным способом задачу можно решить на всех императивных языках, независимо от богатства их инструментария. Однако средства языка программирования могут позволить решить задачу другим, зачастую более простым, путем. Например, в Python можно не преобразовывать введенную строку к числу, а извлекать из нее отдельные символы, которые преобразовывать к целочисленному типу int :
a = input() suma = 0 mult = 1 for digit in a: suma += int(digit) mult *= int(digit) print("Сумма:", suma) print("Произведение:", mult)
Если добавить в код проверку, что извлеченный символ строки действительно является цифрой, то программа станет более универсальной. С ее помощью можно будет считать не только сумму и произведение цифр целых чисел, но и вещественных, а также цифр, извлекаемых из произвольной строки.
n = input() suma = 0 mult = 1 for digit in n: if digit.isdigit(): suma += int(digit) mult *= int(digit) print("Сумма:", suma) print("Произведение:", mult)
это3 чи3с9ло! Сумма: 15 Произведение: 81
Строковый метод isdigit проверяет, состоит ли строка только из цифр. В нашем случае роль строки играет одиночный, извлеченный на текущей итерации цикла, символ.
Глубокое знание языка Python позволяет решить задачу более экзотическими способами:
import functools n = input() n = [int(digit) for digit in n] suma = sum(n) mult = functools.reduce(lambda x, y: x*y, n) print("Сумма:", suma) print("Произведение:", mult)
Выражение [int(digit) for digit in n] представляет собой генератор списка. Если была введена строка «234» , будет получен список чисел: [2, 3, 4] .
Встроенная функция sum считает сумму элементов переданного ей аргумента.
Функция reduce модуля functools принимает два аргумента — лямбда-выражение и в данном случае список. Здесь в переменной x происходит накопление произведения, а y принимает каждое следующее значение списка.
X Скрыть Наверх
Решение задач на Python