Процедуры и функции

145 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Разложение на слагаемые#31803
Требуется вывести все различные представления натурального числа N в виде суммы натуральных чисел. Представления, отличающиеся друг от друга порядком слагаемых, не являются различными.

 
Входные данные
Входная строка содержит целое число N (2 ≤ N ≤ 40).

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

Примеры
№ Входные данные Выходные данные
1 4
1 1 1 1
1 2 1
1 3
2 2
4
2 5
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3
1 4
5
Рекурсия
✓ 70✗ 201700средняяВойти и решать
Сумма кубов#31795
Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов натуральных чисел. Вася решил придумать аналогичное утверждение для кубов - он хочет узнать, сколько кубов достаточно для представления любого числа. Его первая рабочая гипотеза - восемь.

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

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

Входные данные
Вводится натуральное число N <= 2*109.

Выходные данные
Требуется вывести не более восьми натуральных чисел, кубы которых в сумме дают N. Если искомого представления не существует, то в выходной файл необходимо вывести слово IMPOSSIBLE.
 
Примеры
№ Входные данные Выходные данные
1 239 IMPOSSIBLE
2 17  2 2 1
Рекурсия
✓ 8✗ 491 100средняяВойти и решать
Монетки#31794
В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы  сначала поступает число N (1 <= N <= 109), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 109).

Выходные данные
Сначала выведите K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
 
Ввод Вывод
100 6
11 20 30 40 11 99		 3
40 30 30
Рекурсивный переборРекурсия
✓ 19✗ 721 000средняяВойти и решать
Функция - 2*#31793
Описана рекурсивная функции с тремя параметрами F(a, b, c):
 
F(a, b, c) = 1, если a ≤ 0 или b ≤ 0 или c ≤ 0;
F(a, b, c) = F(20, 20, 20), если a > 20 или b > 20 или c > 20;
F(a, b, c) = F(a, b, c-1) + F(a, b-1, c-1) - F(a, b-1, c), если a < b и b < c;
F(a, b, c) = F(a-1, b, c) + F(a-1, b-1, c) + F(a-1, b, c-1) - F(a-1, b-1, c-1), во всех остальных случаях.

 
Входные данные
Входные данные содержат три целых числа a, b, c - параметры функции F (-104 ≤ a,b,c ≤ 104).
 
Выходные данные
В ответе выведите значение функции F(a, b, c).

 
Примеры
№ Входные данные Выходные данные
1 1 1 1 2
2 2 2 2 4
3 10 4 6 523
4 50 50 50 1048576

 
Рекурсия
✓ 179✗ 540700средняяВойти и решать
Как поделить картошку#31792
Вася и Петя пошли копать картошку. В конце дня они накопали N мешков с картошкой весом W1, W2, ... WN. Как им поделить мешки с картошкой между собой, чтобы разница масс была минимальной.
Входные данные
В первой строке  записано число N – количество мешков (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы мешков W1, W2 , … WN (1 ≤ Wi ≤ 105).
 
Выходные данные
В единственную строку нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух куч с мешками.
 
Ввод Вывод
5
5 3 5 7 8		 2
Рекурсия
✓ 97✗ 191700средняяВойти и решать
Заполнение конем#31784
Дана шахматная доска nхn. Пусть конь стоит на клетке (1,1). Необходимо найти такую последовательность ходов коня, при которой он побывает на каждой клетке доски ровно по одному разу.
 
Входные данные
На вход программе подается натуральное число n (n ≤ 8).
 
Выходные данные
Если обход невозможен, то выведите в выходной файл 0, если возможен, то 1, а на следующих строчках выведите матрицу nn, иллюстрирующую порядок обхода. Выравнивать числа по столбцам не обязательно.
 
Примечание. Скорость работы рекурсивной программы в этой задаче существенно зависит от порядка, в каком будут рассматриваться варианты хода коня из очередной клетки. Одним из удачных порядков является размещение всех восьми вариантов хода "по кругу".
 
Ввод Вывод
3 0
5
1
1 20 17 12 3 
16 11 2 7 18 
21 24 19 4 13 
10 15 6 23 8 
25 22 9 14 5 
Обход в глубинуРекурсия
✓ 26✗ 1141 000средняяВойти и решать
Circular Barn#29547
У Фермера Джона круглый амбар. Амбар состоит из кольца из n комнат, пронумерованных 1…n по периметру (3≤n≤1,000). Каждая комната имеет двери в две соседние комнаты и одну дверь во внешний мир.
ФД хочет разместить ровно ri коров в комнате i (1≤ri≤1,000,000). Он планирует открыть k внешних дверей (1≤k≤7), через которые коровы будут входить в амбар. Каждая корова затем идёт по часовой стрелке, пока не добредёт до нужной комнаты. ФД хочет открыть двери так, чтобы все коровы вместе прошли как можно меньшее расстояние. Коровы предварительно могут собраться как им выгоднее перед этими незакрытыми дверями (эти перемещения не входят в общее расстояние, учитываемое в задаче). Определите минимальное суммарное расстояние, которое придётся пройти коровам, если ФД наилучшим образом выберет какие k открыть.
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит n и k. Последующие n строк содержат r1…rn.

ФОРМАТ ВВОДА:
Выведите минимальное суммарное расстояние пройденное коровами.
 
Ввод Вывод
6 2
2
5
4
2
6
2
 14


ФД может открыть двери 2 и 5. 11 коров войдут в двери 2 и пройдут суммарное расстояние 8 чтобы попасть в комнаты 2,3,4. 10 коров войдут в дверь 5 и пройдут общее расстояние 6, чтобы попасть в комнаты 5,6,1.



 
Динамическое программированиеДинамическое программирование: два параметраЗадача на реализациюРекурсия
✓ 1✗ 1—Войти и решать
Это Бомба#24906
Мише приснился страшный сон  как будто ему очень быстро необходимо разминировать бомбу! На большом дисплее бомбы он видит одно число, рядом есть клавиатура с цифрами (явно для экстренной отмены взрыва), а где-то внизу уже идёт обратный отсчёт. По удачному стечению обстоятельств у него с собой есть инструкция для разминирования, в которой ему нужно срочно разобраться. В такой тяжялой ситуации мозги у Миши совсем отказали и ему явно нужна помощь.
 
Инструкция:

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

1. Если число <= 2, то числовой код равен 1.

2. Если число заканчивается на 7, то нужно отнять от него 5. Посчитайте числовой код для нового числа и прибавьте 1.

3. Если число делится на 4 без остатка, его числовой код равен сумме кодов для числа,делённого на 4 и числа, делённого на 2.

4. Во всех остальных случаях к числу нужно прибавить 1.  Посчитайте числовой код для нового числа и прибавьте 2.
 
Какой числовой код нужно ввести Мише?
Формат входных данных
В единственной строке содержится одно число от 1 до 108, которое отображается на дисплее.

Формат выходных данных
Выведите в ответ одно число, которое Мише нужно срочно ввести.

Формат выходных данных
Выведите в ответ одно число, которое Мише нужно срочно ввести.

Ввод Вывод
1 1
10 12

 

Динамическое программирование: один параметрРекурсия
✓ 25✗ 16500лёгкаяВойти и решать
Лесенки#23410
Лесенкой называется набор кубиков, в котором каждый более верхний 
слой содержит кубиков меньше, чем предыдущий.
 
---
| |
---------
| | | | |
-----------
| | | | | |
-----------------
| | | | | | | | |
-----------------
 
Подсчитать число лесенок, которое можно построить из N кубиков.
 
Входные данные
Во входном файле записано число N (1<=N<=100).
 
Выходные данные
В выходной файл вывести искомое число лесенок.
 
Пример
Пример входного файла
3
 
Пример выходного файла
2
 
Рекурсия
✓ 36✗ 160800средняяВойти и решать
Прямоугольное поле чудес (В, А',A)#23372
Коля попал на телеигру "Прямоугольное поле чудес". В финале этой игры Коле показали прямоугольное поле размера n х m клеток, в каждое клетке которого записано целое число.  Коля может
заменить числа в некоторых клетках на противоположные (т.е. вместо числа x записать в клетку число −x). Коля выиграет автомобиль, если сумма чисел в каждой строке и в каждом столбце будет равна нулю. Помогите Коле найти нужную расстановку чисел, либо определите, что ее не существует и Коля не сможет выиграть.
 
Формат входных данных
В первой строке записано два целых числа n и m (1 <= n, m <= 5)  - размеры поля.
В следующих n строках записано по m целых чисел, разделенных пробелами - числа, записанные в клетках поля. Все числа по модулю не превосходят 106.
 
Формат выходных данных
Если ответ существует, в первой строке выведите YES, в следующих n строках выведите по m чисел через пробел - числа в клетках поля после изменений/
Если ответа не существует, в первой строке выведите NO.
Ввод Вывод
3 3
1 1 2
2 2 4
3 3 6		 YES
1 1 -2
2 2 -4
-3 -3 6
Задача на реализациюРекурсия
✓ 13✗ 511 200средняяВойти и решать
Овечка Толя (C, B')#23369
Овечка Толя умеет клонироваться - тогда рядом с ней появляется такая же овечка с той же логикой и привычками.
Когда овечка встречает n стогов сена то происходит следующее:

-  Если n меньше 4 то овечка выкидывает эти n стогов сена в ближайший овраг. Иначе:

-  Если n делится на 5, то овечка сбрасывает n/5 стогов сена в ближайший овраг; клонируется;
    сама обрабатывает 3n/5 стогов сена с помощью этой же процедуры, а ее клон обрабатывает 
     оставшиеся n/5 стогов сена с помощью этой же процедуры. Иначе:
 
- Овечка съедает 4 стога сена и обрабатывает оставшиеся n-4 стогов с помощью этой же процедуры.

Овечка Толя однажды увидела n стогов сена - это число вам дано. Сколько стогов сена будет
съедено ей и всеми е клонами при описанном процессе ?
 
Формат входных данных
 В первой строке содержится натуральное число n <= 6 n <= 106
 
Формат выходных данных
Выведите количество, стогов съеденных в итоге Толей и клонами
 
Ввод Вывод
29 8
Задача на реализациюРекурсия
✓ 23✗ 24900средняяВойти и решать
Коды Грея#23365
На занятиях по дискретной математике Сереже рассказали про двоичные коды Грея — это такое упорядочение всех 2n различных двоичных векторов длины n, что любые два соседних, а также первый и последний, вектора различаются ровно в одном разряде.

Для закрепления материала преподаватель задал им следующее задание: в коде Грея в каждом двоичном векторе ровно один бит заменен на знак вопроса «?». Требуется заменить обратно все знаки вопроса «?» на «0» или «1», чтобы получился код Грея.

Преподаватель обещал бонус на экзамене тому из студентов, кто первым справится с заданием. Помогите Сереже решить задачу или скажите, что это невозможно, и преподаватель задал нераз- решимое задание.

Формат входных данных
В первой строке содержится целое число n — длина двоичных векторов. Следующие 2n строк содержат двоичные вектора длины n, в каждом из которых ровно один символ заменен на знак вопроса «?».
Формат выходных данных
В первой строке выведите «YES», если решение существует, и «NO» — в противном случае. В случае положительного ответа выведите исходный код Грея, если возможных вариантов ответа несколько, выведите любой.
 
Ввод Вывод
2
0?
0?
1?
1?		 YES
00
01
11
10
3
?00
0?1
01?
0?0
?10
1?1
10?
1?1		 NO

Система оценки
 
Номер подзадачи Баллы Ограничения Комментарии
1 37 1<=n<=4 Баллы начисляются, если все тесты пройдены.
2 63 1<=n<=12 Баллы начисляются, если все тесты этой и предыду- щих подзадач пройдены.

 
КонструктивРекурсия
✓ 2✗ 261 100средняяВойти и решать
Число с максимальной суммой делителей#21835
Напишите функцию, вычисляющую сумму делителей числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальным суммой делителей
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно  число, в котором сумма делителей числа максимальна среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).
 

Пример

Ввод

Вывод
5
2
5
59
72
34
 72
2
78
81		 78
 
Алгоритмы обработкиЗадачи на процедуры и функцииЛинейные алгоритмы
✓ 82✗ 242700средняяВойти и решать
Число с максимальным количеством делителей#21834
Напишите функцию, вычисляющую количество делителей числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальным количеством делителей
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно  число, в котором количество делителей максимально среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод

Вывод
5
22790
94
66
18
18
 22790
2
21
46 
 21
 
Алгоритмы обработкиЗадачи на процедуры и функцииПростые числа и разложение на множители
✓ 112✗ 236700средняяВойти и решать
Число с максимальной первой цифрой#21833
Напишите функцию, вычисляющую первую цифру числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальной первой цифрой
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100)
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно  число, у которого первая цифра максимальна среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).
 

Пример

Ввод

Вывод
5
43
22
11
56
10		 56
2
14
22		 22
 
Алгоритмы обработкиЗадачи на процедуры и функции
✓ 159✗ 283600лёгкаяВойти и решать
Число с максимальной суммой цифр#21832
Напишите функцию, вычисляющую сумму цифр числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальной суммой цифр
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно  число, в котором сумма цифр максимальна среди всех чисел

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).
 

Пример

Ввод

Вывод
5
43
22
11
56
10		 56
2
34
12		 34
Алгоритмы обработкиЗадачи на процедуры и функции
✓ 120✗ 240600лёгкаяВойти и решать
Кратность 11#21831
Для делимости числа на 11, необходимо, чтобы разность между суммой цифр, стоящих на четных местах, и суммой цифр, стоящих на нечетных местах, делилась на 11. 
Напишите функцию, работающую по данному алгоритму, для проверки делимости числа n, вводимого с клавиатуры, на 11. 

Используя данную функцию, напишите программу, которая запрашивает у пользователя число n (0<=n<=100000) и выводит на экран фразу multiple of 11,  если число кратно 11 и фразу not multiple of 11, если число не кратно 11

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию или функция вычисляет кратность не по приведенному алгоритму!).

Пример

Ввод

Вывод
1 not multiple of 11
11 multiple of 11

Задача на реализациюЗадачи на процедуры и функции
✓ 238✗ 411500лёгкаяВойти и решать
Кратность 9#21830
Для делимости числа на 9, требуется, чтобы сумма цифр числа делилась на 9. 
Напишите функцию, работающую по данному алгоритму, для проверки делимости числа n, вводимого с клавиатуры, на 9. 

Используя данную функцию, напишите программу, которая запрашивает у пользователя число n (0<=n<=100000) и выводит на экран фразу multiple of 9,  если число кратно 9 и фразу not multiple of 9, если число не кратно 9

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию или функция вычисляет кратность не по приведенному алгоритму!).

Пример

Ввод

Вывод
3 not multiple of 9
9 multiple of 9

Задачи на процедуры и функцииУсловный оператор
✓ 240✗ 427500лёгкаяВойти и решать
Кратность 8#21829
Для делимости числа на 8, необходимо, чтобы число из трех последних цифр делилось на 8. 
Напишите функцию, работающую по данному алгоритму, для проверки делимости числа n, вводимого с клавиатуры, на 8. 

Используя данную функцию, напишите программу, которая запрашивает у пользователя число n (0<=n<=100000) и выводит на экран фразу multiple of  8,  если число кратно 8 и фразу not multiple of 8, если число не кратно 8

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию или функция вычисляет кратность не по приведенному алгоритму!).
 

Пример

Ввод

Вывод
3 not multiple of 8
8 multiple of 8
Вычисление по заданной формулеЗадачи на процедуры и функции
✓ 154✗ 259500лёгкаяВойти и решать
Поделиться
Класснуть