Информатика

2 621 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Изменение элемента#47971
В двумерном массиве NxM замените значение элемента, расположенного на пересечении строки n1 и столбца m1, на значение A. Нумерация строк и столбцов начинается с 1.

Формат входных данных
В первой строке вводятся через пробел количество строк N (1<=N<=20) и количество столбцов M (1<=M<=20) двумерного массива. Далее идет N строк по M элементов в строке - элементы двумерного массива. Все элементы двумерного массива по модулю не превышают  50. В N+1 строке идут два числа n1, m1 (1<=n1<=N, 1<=m1<=M). В N+2 строке записано число A. 

Формат выходных данных
Выведите измененный двумерный массив на экран. Элементы в строке должны разделяться одним пробелом.
 
Алгоритмы обработкиДвумерные массивы
✓ 62✗ 76300лёгкаяВойти и решать
Шнурки#47969

Обувная фабрика собирается начать выпуск элитной модели ботинок. Дырочки для шнуровки будут расположены в два ряда, расстояние между рядами равно a, а расстояние между дырочками в ряду b. Количество дырочек в каждом ряду равно N. Шнуровка должна происходить элитным способом “наверх, по горизонтали в другой ряд, наверх, по горизонтали и т.д.” (см. рисунок). Кроме того, чтобы шнурки можно было завязать элитным бантиком, длина свободного конца шнурка должна быть l. Какова должна быть длина шнурка для этих ботинок?
Запрещено использовать операторы if, while, for, repeat-until (Паскаль)

Входные данные: Программа получает на вход четыре натуральных числа a, b, l и N.

Выходные данные: Программа должна выводить одно число – искомую длину шнурка.

Примеры
входные данные
2
1
3
4
выходные данные
26
Вывод формулыЦелые числа
✓ 49✗ 110700средняяВойти и решать
Все сочетания из n по k#47937
Даны два целых числа n и k, выведите все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Порядок элементов в одной комбинации не важен. То есть комбинация (1, 2, 3) и (3, 2, 1) считается одинаковой.
Выведите на экран все такие комбинации в лексикографическом порядке. 

Входные данные
В первой строке записано целое число n, во второй - целое число k.
 

Ограничения

  • 1 <= n <= 20
  • 1 <= k <= n


Выходные данные
Выведите в лексикографическом порядке все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Каждая комбинация чисел должна выводиться в отдельной строке, числа в одной комбинации разделяются одним пробелом.
 
Перебор с возвратомРекурсия
✓ 61✗ 50700средняяВойти и решать
Фишки-палочки#47746

Алиса и Громозека играют в фишки-палочки. У каждого из них есть набор фишек, на каждой фишке записано одно целое число. Каждый из них  выкладывает свои фишки вдоль двух параллельных горизонтальных линий. Следующим шагом Алиса соединяет палочкой две фишки, расположенные на разных горизонтальных линиях, то есть соединяет одну свою фишку с одной из фишек Громозеки по следующим правилам:

  1. числа, на фишке Алисы и на фишке Громозеки равны;
  2. соединяющая палочка не должна пересекать другие палочки;
  3. две палочки не могут указывать на одну и ту же фишку.

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

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


Входные данные
Первая строка входных данных содержит число n - количество фишек Алисы. Вторая строка содержит n чисел nums1i - числа на фишках Алисы, в том порядке, в котором она их выложила. Третья строка содержит число m - количество фишек Громозеки. Четвертая строка содержит m чисел nums2j - числа на фишках Громозека, в том порядке, в котором он их выложил. 

Ограничения

  • 1 <= n, m <= 500
  • 1 <= nums1[i], nums2[j] <= 2000


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

Примечание
Рисунок к первому тестовому примеру

Динамическое программированиеДинамическое программирование: последовательности
✓ 45✗ 47600лёгкаяВойти и решать
Айвен собирает кристаллы#47744

Юный волшебник Айвен отправляется в волшебный лес, чтобы набрать  волшебных кристаллов. Каждый кристалл, растущий в данном лесу, обладает своей массой. Айвен имеет рюкзак, который может выдержать определенный вес M. Айвен хочет использовать свой рюкзак по максимуму и набрать  кристаллов такое количество, чтобы суммарно их вес равнялся в точности весу, который может выдержать его рюкзак. 
Вам стали известны массы кристаллов, которые растут в волшебном лесу. Выведите "YES",  если Айвен сможет набрать кристаллов суммарным весом ровно M, иначе выведите "NO".


Входные данные
В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 104. Во второй строке вводятся N натуральных чисел mi, не превышающих 100.

Выходные данные
Выведите YES или NO.
 
Динамическое программированиеЗадача о рюкзаке
✓ 37✗ 60600лёгкаяВойти и решать
Магическая подпоследовательность Айвена#47742
Юный волшебник Айвен считает последовательность символов магической, если она является палиндромом (то есть читается одинаково как слева направо, так и справа налево). Айвену попалась в руки последовательность символов s. Он хочет удалить из нее любое (возможно нулевое) количество символов, чтобы получить из нее самую длинную магическую подпоследовательность. 
Определите длину самой длинной магической подпоследовательности, которую сможет получить Айвен.

Входные данные
Программа получает на вход последовательность символов s (1<= |s| <= 1000), состоящую из строчных английских букв. 

Выходные данные
Выведите одно число - длину самой длинной магической подпоследовательности.
 
 
Примеры
№ Входные данные Выходные данные
1 
bbbab
 
4
Динамическое программированиеДинамическое программирование: последовательности
✓ 34✗ 24500лёгкаяВойти и решать
Раздвоитель#47701
Исполнитель “Раздвоитель” преобразует натуральные числа. У него есть две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное, иначе происходит ошибка.

Входные данные
Программа получает на вход два натуральных числа A и B (по одному числу в строке).

Выходные данные
Напишите алгоритм для Развоителя, который преобразует число A в число B и при этом содержит минимальное число команд. Команды алгоритма нужно выводить по одной в строке, первая команда обозначается, как -1, вторая команда как :2.
 
 
Примеры
№ Входные данные Выходные данные
1 21
2		 -1
:2
:2
-1
:2
Жадный алгоритмЛинейные алгоритмы
✓ 38✗ 134500лёгкаяВойти и решать
Степень двойки#47700

Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае.

Операцией возведения в степень пользоваться нельзя!
 

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

Вводится натуральное число N (N < 109).

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

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

 
Примеры
№ Входные данные Выходные данные
1 1 YES
2 4 YES
3 5 NO
 
Двоичная система счисленияЦикл for
✓ 92✗ 157500лёгкаяВойти и решать
Кристаллы максимуса#47675
Максимус очень любит коллекционировать кристаллы. Среди всех кристаллов у него есть один самый любимый с магической силой равной n. Также у него есть коллекция совершенных кристаллов. Совершенный кристалл - это кристалл, магическая сила которого равна квадрату натурального числа.
У Максимуса выдался свободный вечер, и он задумался: сколько нужно ему совершенных кристаллов, чтобы сумма их магических сил равнялась бы магической силе его любимого кристалла?
Квадратом натурального числа является число, которое получается умножением натурального числа на себя. Например, 1, 4 и 9 - это квадраты натуральных чисел, а 2, 3 и 5 - нет.
Ваша задача - помочь Максимусу найти минимальное количество совершенных кристаллов, сумма магических сил которых равна n.

Входные данные
Программа получает на вход натуральное число n (n < 104).

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 
12
 
3
 12 = 4 + 4 + 4
2 13 2 13 = 4 + 9
Динамическое программированиеЗадача о рюкзаке
✓ 40✗ 71500лёгкаяВойти и решать
Перестановка двух элементов - 4#47573
В числовом массиве из N чисел переставьте местами элемент с индексом first с элементом, который имеет максимальное значение. Если максимальных элементов несколько, то необходимо взять последний из них (максимальный элемент с большим индексом). Индексация элементов начинается с 0.

Входные данные
В первой строке записаны через пробел два числа N - количество элементов одномерного массива и число first. Во второй строке записаны N чисел numsi - элементы массива.

Ограничения
1 <= N <= 105
-109 <= numsi <= 109
0 <= first < N

Выходные данные
Выведите в одну строку измененный массив, разделяя элементы одним пробелом.
 
 
Примеры
№ Входные данные Выходные данные
1 
5 2
1 -2 -1 2 -2

1 -2 2 -1 -2
Алгоритмы обработкиОдномерные массивы
✓ 33✗ 86300лёгкаяВойти и решать
Калькулятор с восстановлением ответа#46698
Имеется калькулятор, который выполняет три операции:
  1. Прибавить к числу X единицу.
  2. Умножить число X на 2.
  3. Умножить число X на 3.
Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N.
 
Входные данные
Программа получает на вход одно число X, не превосходящее 106.

Выходные данные
Выведите строку, состоящую из цифр "1", "2" или "3", обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них. 
 
 
Примеры
№ Входные данные Выходные данные
1 1  
2 5 121
3 562340 3333312222122213312
Динамическое программированиеДинамическое программирование: один параметр
✓ 434✗ 1 059600лёгкаяВойти и решать
Маршрут наименьшей стоимости#46697
Робот Сильвер движется по платному шоссе на планете Шелезяка. На каждом километре шоссе расположен пункт оплаты. Всего на шоссе n пунктов оплаты. Первый пункт оплаты находится в самом начале шоссе, n-й пункт оплаты находится в начале последнего километра шоссе. Заплатив нужную сумму в i-м пункте оплаты, робот может двигаться дальше либо до следующего пункта оплаты, либо же до того, который находится через 2 километра (то есть, если робот находится в пункте i, то он может двигаться либо до пункта i+1, либо до пункта i+2). Первую оплату можно сделать либо в первом пункте, либо во втором (на выбор). Если оплаты была произведена в предпоследнем (n-1) пункте, то можно просто доехать до конца  шоссе, не оплачивая проезд в последнем пункте.
Зная стоимость проезда через определенный пункт оплаты, помогите роботу Сильверу найти наименьшую стоимость проезда через все шоссе, которую должен будет заплатить Сильвер, а также пункты оплаты, на которых ему необходимо будет остановиться. 

Входные данные
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

Выходные данные
Выведите в первой строке наименьшую стоимость проезда через шоссе. 
Во второй строке выведите через пробел номера пунктов оплаты (по возрастанию), на которых роботу придется остановиться, чтобы оплатить проезд. Если вариантов маршрута с остановками в пунктах оплаты несколько, то выведите любой из них.
 
 
Примеры
№ Входные данные Выходные данные
1 3
10 15 20		 15
2
2 10
1 100 1 1 1 100 1 1 100 1		 6
1 3 5 7 8 10
Динамическое программированиеДинамическое программирование: один параметр
✓ 504✗ 1 093600лёгкаяВойти и решать
Стоимость проезда#46622
Дорога с семью станциями: слева въезд с монетой 0, затем пять пунктов оплаты с монетами 2, 1, 3, 1, 5, и справа съезд с монетой 0. На дороге у въезда стоит робот-машинка. Две стрелки показывают, что робот может прыгнуть на 1 или на 2 пункта. Платное шоссе робота Сильвера прыжок — на 1 или 2 пункта 0 ВЪЕЗД 2 1 3 1 5 0 СЪЕЗД 1 2 3 4 5 Платит там, где останавливается. Въезд и съезд — бесплатные (0). Робот Сильвер едет по шоссе. Вдоль дороги стоят n пунктов оплаты — по одному на каждый километр. На пункте i написана плата cost[i]: столько робот отдаёт, если останавливается у этого пункта. Пункт, мимо которого он проехал не останавливаясь, не оплачивается.
Перед шоссе есть бесплатный въезд, а после — бесплатный съезд. Робот стартует со въезда, едет только вперёд, и от каждой остановки до следующей проезжает 1 или 2 пункта. Доехать ему надо до съезда.
Найдите наименьшую сумму, которую заплатит робот.

Формат входных дынных
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

Формат выходных дынных
Выведите одно число - ответ на задачу.
Динамическое программированиеДинамическое программирование: один параметр
✓ 985✗ 995500лёгкаяВойти и решать
N-е число Трибоначчи (снизу-вверх)#46621

Последовательность чисел Трибоначчи (Tn) определяется следующим образом: 

T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.

Для заданного числа n, определите значение Tn.



Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 231 - 1.

Выходные данные
Выведите значение Tn.
 
Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).

 
Примеры
№ Входные данные Выходные данные
1 4 4
2 25 1389537
Динамическое программированиеДинамическое программирование: один параметр
✓ 773✗ 725300лёгкаяВойти и решать
Подняться на вершину горы (рекурсивно)#46620
Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницу, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

Выходные данные
Выведите одно число - количество способов добраться до вершины горы.
 
 
Примеры
№ Входные данные Выходные данные
1 2 2
2 3 3
Динамическое программированиеДинамическое программирование: один параметр
✓ 648✗ 987400лёгкаяВойти и решать
Числа Фибоначчи. Динамика снизу вверх#46619

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).
 

Примеры
№ Входные данные Выходные данные
1 2 1
2 3 2
3 4 3
Динамическое программированиеДинамическое программирование: один параметр
✓ 730✗ 1 322300лёгкаяВойти и решать
Подняться на вершину горы (снизу-вверху)#46618
Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницей, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

Выходные данные
Выведите одно число - количество способов добраться до вершины горы.
 
Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).
 
Примеры
№ Входные данные Выходные данные
1 2 2
2 3 3
Динамическое программированиеДинамическое программирование: один параметр
✓ 733✗ 700300лёгкаяВойти и решать
N-е число Трибоначчи (рекурсивно)#46617

Последовательность чисел Трибоначчи (Tn) определяется следующим образом: 

T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.

Для заданного числа n, определите значение Tn.



Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 231 - 1.

Выходные данные
Выведите значение Tn.
 
 
Примеры
№ Входные данные Выходные данные
1 4 4
2 25 1389537
Динамическое программированиеДинамическое программирование: один параметр
✓ 724✗ 1 601400лёгкаяВойти и решать
Числа Фибоначчи: Мемоизация рекурсии (Python)#46616

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

(в коде программы длина одного отступа равна 4 пробелам!)

Примеры
№ Входные данные Выходные данные
1 2 1
2 3 2
3 4 3
Динамическое программированиеДинамическое программирование: один параметр
✓ 701✗ 1 427400лёгкаяВойти и решать
(C++) Перестановка слов#46577
На вход подается одна строка, в которой записаны фамилия и имя человека (разделенные ровно одним пробелом).
 
Выведите эту же информацию, однако сначала имя, а потом фамилию.
 
Пример
№ Входные данные Выходные данные
1 Pupkin Vasya Vasya Pupkin
 
Ввод, вывод данныхСтроки
✓ 1 453✗ 1 604100лёгкаяВойти и решать
Поделиться
Класснуть