Информатика

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

У Громозеки есть его любимая строка S и другая строка T.  Он внимательно посмотрел на свои строки и понял, что первая строка (S) может содержать в себе несколько раз вторую строку (T). Громозека подсчитал все вхождения строки T в строку S и написал себе в порядке возрастания список индексов, начиная с которых строка T входит в строку S. Однако, путешествуя по Галактике, Громозека потерял этот список и пришел в уныние. Помогите Громозеке восстановить потерянный список. 


Формат входных данных
Первые две строки входных данных содержат строки S  и T, соответственно. Длины строк больше 0 и меньше 50000, строки содержат только строчные латинские буквы.

Формат выходных данных
Выведите в порядке возрастания индексы символов, начиная с которых строка T входит в строку S (в одной строке должно быть записано одно число).
Строки
✓ 6✗ 8700средняяВойти и решать
Столбцы с min/max#48047
Дана матрица numsi,j размером nxm. Вывести те столбцы матрицы, в которых имеется хотя бы один элемент, равный минимальному элементу матрицы.

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -105 <= numsi,j<=105)

Формат выходных данных
Выведите столбцы матрицы, которые удовлетворяют условию задачи. Элементы столбцов необходимо выводить в одной строке, столбцы выводить в том же порядке, в котором они записаны в матрице.
Двумерные массивы
✓ 19✗ 50700средняяВойти и решать
Строки с min/max#48045
Дана матрица numsi,j размером nxm. Вывести те строки матрицы, в которых имеется хотя бы один элемент, равный минимальному элементу матрицы.

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -105 <= numsi,j<=105)

Формат выходных данных
Выведите строки матрицы, которые удовлетворяют условию задачи. Строки необходимо выводить в том же порядке, в котором они записаны в матрице.
Двумерные массивы
✓ 21✗ 31600лёгкаяВойти и решать
min/max в матрице - 2#48044
Дана матрица numsi,j размером nxm. Заменить каждый элемент матрицы, оканчивающийся на 43, на максимальный элемент матрицы. 

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -105 <= numsi,j<=105)

Формат выходных данных
Выведите измененную матрицу на экран. Элементы в троке должны разделяться одним пробелом.
 
Двумерные массивы
✓ 13✗ 36500лёгкаяВойти и решать
min/max в матрице - 1#48043
Дана матрица numsi,j размером nxm. Заменить каждый элемент матрицы, оканчивающийся на 12, на минимальный элемент матрицы. 

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -105 <= numsi,j<=105)

Формат выходных данных
Выведите измененную матрицу на экран. Элементы в строке должны разделяться одним пробелом.
 
Двумерные массивы
✓ 15✗ 36500лёгкаяВойти и решать
Ферзь#48040
Пётр любит шахматы и математику. Он знает, что самая мощная фигура в шахматах - это ферзь, потому что он ходит и как ладья, на все клетки на одной с ним вертикали или горизонтали, и как слон, на все клетки по диагоналям. Ферзя можно поставить на доску 8 X 8 так, чтобы он контролировал (то есть мог переместиться в эти клетки за один ход) целых 27 клеток доски!

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

Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 109) - размер доски по вертикали.
Вторая строка входных данных содержит целое число m (1 ≤ m ≤ 109) - размер доски по горизонтали.
Формат выходных данных

Программа должна вывести одно целое число - максимальное количество клеток, которое может контролировать ферзь на доске n x m.

Обратите внимание на то,  что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).

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

 
Вывод формулы
✓ 75✗ 240600лёгкаяВойти и решать
Вывод столбца#47972
Формат входных данных
В первой строке вводятся через пробел количество строк N (1<=N<=20) и количество столбцов M (1<=M<=20) двумерного массива.
Далее идет N строк по M элементов в строке - элементы двумерного массива. Все элементы двумерного массива по модулю не превышают 50.
Далее идет число k (1<=k<=N) 

Формат выходных данных
Вывести на экран k-й столбец (считая, что нумерация элементов массива начинается с 1, т.е. для первого столбца k=1).
Все элементы выводить в одну строку через 1 пробел между элементами.
Двумерные массивы
✓ 33✗ 49300лёгкаяВойти и решать
0-1 Рюкзак#47745
Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно.

Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?

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

Выходные данные
Выведите наибольшую стоимость рюкзака.
Задача о рюкзаке
✓ 34✗ 73400лёгкаяВойти и решать
Артефакты Максимуса#47741
У Магистра Максимуса в руках три артефакта с последовательностями символов. Чтобы раскрыть их тайны, нужно открыть все три артефакта одновременно с помощью одинаковых последовательностей символов. Для этого Максимус может удалять только самый правый символ из каждой последовательности сколько угодно раз. Обратите внимание, что для того, чтобы Максимус мог удалить символ из последовательности, ее длина должна быть не менее двух символов. 
Определите минимальное количество операций, которые необходимо выполнить Максимусу, чтобы привести три последовательности к одинаковому виду. Если такое невозможно, ответ должен быть -1.

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

Constraints:

  • 1 <= |s1|, |s2|, |s3| <= 100
  • s1, s2 и s3 состоят только из строчных английских букв
|s|  означает длину последовательности s

Выходные данные
Выведите ответ на задачу.
 
Строки
✓ 56✗ 209600лёгкаяВойти и решать
Парад#47702
В параде принимают участие M военных. Командование парада решило, что наиболее эффектное построение военных – в форме квадрата, то есть число участников построения должно быть точным квадратом. Но поскольку число M может не быть точным квадратом, разрешается разбить военных на несколько полков, каждый из которых строится в форме квадрата. Для красоты все полки должны быть одинакового размера, также командование парада хочет, чтобы размер каждого полка был как можно больше. Определите максимально возможный размер полка.

Входные данные
Программа получает на вход одно целое положительное число M, не превосходящее 2×109, – количество участников парад.

Выходные данные
Программа должна вывести одно число – максимально возможный размер полка. 
 
Примеры
№ Входные данные Выходные данные
1 
180
 
36

 
Циклы
✓ 55✗ 60700средняяВойти и решать
Идентичные строки#47639

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


Входные данные
Программа получает на вход две строки s1 и s2.

Ограничения

  • 1 <= длина s1 и s2 <= 500;
  • s1 и s2 состоят из маленьких английских букв.

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 
sea
eat
 
2
 Вам нужно сделать один шаг, чтобы превратить "sea" в "ea", и еще один шаг, чтобы превратить "eat" в "ea".
Динамическое программирование по подстрокам
✓ 35✗ 40700средняяВойти и решать
Паровозики на числовой прямой#47637

Паровозики стоят на железной дороге параллельно друг другу на параллельных участках пути. Условно весь участок железной дороги можно представить в виде числовой прямой. В этом случае i-й паровозик на данной числовой прямой покрывает некоторое количество заданных целых точек (от точки starti до точки endi, включая данные точки).

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

Входные данные
В первой строке записано число N - количество паровозиков на железной дороге. В следующих N строках записаны по 2 числа (starti, endi)  - тоски начала и конца i-го паровозика. 

Ограничения

1 <= N <= 100
1 <= starti <= endi <= 100


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

Примеры
№ Входные данные Выходные данные Примечания
1 
3
3 6
1 5
4 7
 
7
 Все точки от 1 до 7 покрыты хотя бы одним паровозиком. Поэтому ответ 7.
Множества
✓ 26✗ 23500лёгкаяВойти и решать
Перестановка двух элементов - 5#47574
В числовом массиве из N чисел поменять местами первый отрицательный и последний положительный элементы. Учесть возможность того, что отрицательных или положительных элементов в массиве может не быть. В этом случае, никакие элементы местами менять не нужно.


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

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

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

1 2 -1 -2 -2
Одномерные массивы
✓ 26✗ 79600лёгкаяВойти и решать
Перестановка двух элементов - 2#47572
В числовом массиве из N чисел переставьте местами элемент с индексом first с элементом, который имеет минимальное значение. Если минимальных элементов несколько, то необходимо взять последний из них (минимальный элемент с большим индексом). Индексация элементов начинается с 0.

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

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

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

1 -2 -2 -1 2
Одномерные массивы
✓ 46✗ 181300лёгкаяВойти и решать
Перестановка двух элементов - 2#47571
В числовом массиве из N чисел переставьте местами элемент с индексом first с элементом, который имеет минимальное значение. Если минимальных элементов несколько, то необходимо взять первый из них (минимальный элемент с меньшим индексом). Индексация элементов начинается с 0.

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

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

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

1 2 -2 -1 0
Одномерные массивы
✓ 96✗ 176500лёгкаяВойти и решать
Перестановка двух элементов - 1#47570
В числовом массиве из N чисел переставьте местами элемент с индексом first с элементом, который имеет максимальное значение. Если максимальных элементов несколько, то необходимо взять первый из них (максимальный элемент с меньшим индексом). Индексация элементов начинается с 0.

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

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

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

1 2 3 -1 0
Одномерные массивы
✓ 33✗ 59300лёгкаяВойти и решать
Эпическое соревнование#47532
Эпическое соревнование проводится по почти олимпийской системе. Среди n команд, в несколько туров определяют единственную команду-победительницу по следующим правилам.
  • Если количество команд, участвующих в очередном туре, четное, то команды разбиваются по парам. Эти пары соревнуются между собой (т.е. проводится n/2 матчей) и в следующий раунд выходит ровно половина команд (команды всегда соревнуются между собой до победы какой-либо команды);
  • Если количество команд, участвующих в очередном туре нечетное, то перед началом этого тура проводится лотерея, которая определит ту одну удачливую команду, которая получит пропуск в следующий раунд. Оставшиеся команды опять разбиваются на пары и соревнуются между собой (т.е. сыграют между собой n/2 матчей).
Вас же просят определить количество матчей, сыгранных в соревновании до определения победителя.


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

Выходные данные
Выведите единственное число - ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные
1 7 6
Циклы
✓ 12✗ 8500лёгкаяВойти и решать
Списочные выражения - 4.2#47504
Программа получает на вход строку s, содержащую как буквенные символы так и цифровые,
Дополните приведенный код, используя списочное выражение так, чтобы получить новый список, содержащий только не цифровые символы данной строки s.
Одномерные массивы
✓ 79✗ 112400лёгкаяВойти и решать
Списочные выражения - 4.1#47503
Программа получает на вход строку s, содержащую как буквенные символы так и цифровые,
Дополните приведенный код, используя списочное выражение так, чтобы получить новый список, содержащий только цифровые символы данной строки s.
Одномерные массивы
✓ 64✗ 47500лёгкаяВойти и решать
Поделиться
Класснуть