Информатика

15 732 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Гвоздики#23408
На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
 
Входные данные: 
- в первой строке записано число N - количество гвоздиков (\(2 <= N <= 100\));
- в следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
 
Выходные данные: выведите единственное число - минимальную суммарную длину всех ниточек.
Динамическое программирование: один параметр
✓ 650✗ 1 357600лёгкаяВойти и решать
Минимальный путь в таблице#23407
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке.
За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено).
При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).
 
Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.
 
Входные данные
В первой строке записаны два числа N и M - размеры таблицы (\(1<=N<=20\), \(1<=M<=20\)). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).
 
Выходные данные
Выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.
 
 
Примеры
№ Входные данные Выходные данные
1
3 4
1 1 1 1
5 2 2 100
9 4 2 1
 8
Динамическое программирование: два параметра
✓ 722✗ 746400лёгкаяВойти и решать
Распаковка строчки#23406
Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки. 
 
Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.
 
Выходные данные
Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n - количество повторений символа (целое число от 2 до 99), а A - заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.
 
Выходные данные
В выходной файл выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).
 
Примеры
 
Ввод Вывод
3A4B7D                      AAABBBBDDDDDDD
22D7AC18FGD
DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF
FFFFFFFFGD
95AB
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAB
40AB39A
 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
 
Алгоритмы на строках
✓ 70✗ 211700средняяВойти и решать
Статистика#23404
Дан текст. Напишите программу, которая посчитает статистику - сколько раз встречается буква A, сколько - B и т.д. При этом большие и маленькие латинские буквы считать одинаковыми. В тексте могут быть сколь угодно длинные строки. Длина текста не превышает 100 Кб.
 
Входные данные
На вход подается текст, состоящий из английских букв (больших и маленьких), знаков препинания, цифр и т.д.
 
Выходные данные
Выведите 26 строк. Каждая строка должна соответствовать латинской букве, буквы должны идти в алфавитном порядке.Каждая строка должна содержать сначала большую латинскую букву, которой она соответствует, пробел, символ - (тире), пробел и число: сколько раз буква встречается во входном файле.
 
Примеры
№ Входные данные Выходные данные
1 Ab - a
A - 2
B - 1
C - 0
D - 0
<...здесь в выходном файле перечисляются все буквы...>
Z - 0
 
Строки
✓ 108✗ 364800средняяВойти и решать
Поиск подстроки#23403
Сколько раз встречается?
 
Входные данные
Вам дается две строки. Длина каждой из строк не превышает 255 символов.

Выходные данные
Посчитайте и выведите на экран, сколько раз первая строка встречается в качестве подстроки во второй.
 

 

Примеры
№ Входные данные Выходные данные
1
abab
abababcab
 2

Пояснение: подстрока abab встречается во второй строке дважды, начиная с 1-го и 3-го символа.

Поиск подстроки в строке
✓ 106✗ 124400лёгкаяВойти и решать
Арифметическое выражение#23402

В первой строке входных данных записано арифметическое выражение в виде:

<число> <операция> <число> =

<Число> - это натуральное число, не превышающее 10000.

<Операция> - один из знаков +, -, *.

В начале строки, в конце строки, а также между числами и знаком операции, числом и символом =, может быть любое число пробелов (а может пробелов и не быть).

Гарантируется, что длина строки не превышает 200 символов.

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

 

Примеры
№ Входные данные Выходные данные
1 154    +3   = 157
 
Строки
✓ 350✗ 452600лёгкаяВойти и решать
Найти 1543#23401
Найдите в тексте 1543.

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

Выходные данные
Если в нем встречается число 1543, выведите слово URA, если же 1543 в файле не встречается, выведите NO.
 
Примеры
№ Входные данные Выходные данные
1 hgdfjgkdghkdjgkgkd1543gjdlgkdjlg URA
2 1=5 4=3 NO
Поиск подстроки в строке
✓ 145✗ 569700средняяВойти и решать
Метро#23399

В мегаполисе, испытывающем большие транспортные проблемы, построили легкое метро. Оно состоит из 6 радиальных линий, которые расходятся от центра города, и k кольцевых линий в форме правильных шестиугольников.  Станции метро располагаются на пересечении кольцевых и радиальных линий. На любой станции разрешено делать пересадки с кольцевых линий на радиальные и обратно. Радиальные линии последовательно нумеруются по часовой стрелке от 1 до 6. Кольцевые линии нумеруются от центра города (центр считается кольцевой линией с номером ноль, состоящей из одной станции). 

Расстояние между двумя соседними станциями на одной радиальной линии равно 1 км. Расстояние между соседними станциями на кольцевой линии с номером i составляет i км. Любая станция обозначается парой чисел - номером радиальной линии r (\(1<=r<=6\)) и номером кольцевой линии k (\(0<=k<=32000\)), на пересечении которых она находится. 

Напишите программу, определяющую длину кратчайшего пути между станциями.

 

Входные данные: Вводятся четыре числа: r1, k1, r2, k2 - координаты начальной и конечной станции. 

Выходные данные: Необходимо вывести расстояние (в км), которое потребуется проехать пассажиру, чтобы попасть c начальной станции на конечную.


Примеры
№ Входные данные Выходные данные
1 1 5 1 4 1
2 1 5 2 4 5
3 2 0 6 3 3

 
кратчайшие путиРазбор случаев
✓ 220✗ 1 064800средняяВойти и решать
Под побочной диаганалью#23390
Дан двумерный массив размером nxn (n<=10). Сформировать одномерный массив из элементов заданного массива, расположенных под побочной диагональю.


Входные данные 
Программа получает на вход число n <= 10, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по n чисел, являющихся элементами массива.
 

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

 
Примеры
№ Входные данные Выходные данные
1
3
888 29 37 
92 888 57 
73 75 888
 57 75 888
Двумерные массивы
✓ 93✗ 125600лёгкаяВойти и решать
Под главной диагональю#23389
Дан двумерный массив размером nxn (n<=10). Сформировать одномерный массив из элементов заданного массива, расположенных под главной диагональю.


Входные данные 
Программа получает на вход число n <= 10, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по n чисел, являющихся элементами массива.
 

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

 
Примеры
№ Входные данные Выходные данные
1
3
888 29 37 
92 888 57 
73 75 888 
 92 73 75
Двумерные массивы
✓ 88✗ 88500лёгкаяВойти и решать
Над побочной диагональю#23388
Дан двумерный массив размером nxn (n<=10). Сформировать одномерный массив из элементов заданного массива, расположенных над побочной диагональю.


Входные данные 
Программа получает на вход число n <= 10, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по n чисел, являющихся элементами массива.


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

 
Примеры
№ Входные данные Выходные данные
1
3
888 29 37 
92 888 57 
73 75 888 
 888 29 92
Двумерные массивы
✓ 127✗ 101500лёгкаяВойти и решать
Над главной диагональю#23387
Дан двумерный массив размером nxn (n<=10). Сформировать одномерный массив из элементов заданного массива, расположенных над главной диагональю.


Входные данные 
Программа получает на вход число n <= 10, являющееся числом строк и столбцов в массиве. Далее во входном потоке идет n строк по n чисел, являющихся элементами массива.


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

 
Примеры
№ Входные данные Выходные данные
1
3
888 29 37 
92 888 57 
73 75 888  
 29 37 57
Двумерные массивы
✓ 158✗ 187400лёгкаяВойти и решать
Увеличение чисел - 1#23385

В первой строке входных данных записано число N (от 1 до 100).

В каждой из последующих N строк записано сначала некоторое целое число (из диапазона от 0 до 10000), затем пробел, и затем некоторый текст (не более 20 символов).

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

 
Примеры
№ Входные данные Выходные данные
1
2
14 Start
42 Stop
2
15 Start
43 Stop
 
Строки
✓ 1 561✗ 3 609400лёгкаяВойти и решать
**Столовские котлеты#23380
Главный повар решил устроить в лицее День Уважения к Повару. Для этого он приготовил лицеистам N необычайно вкусных котлет и втайне постановил, что первый пожаловавший отведать поварское кушанье школьник должен получить наибольшее количество вкусных котлет, а каждый последующий - строго меньше, чем предыдущий (повару очень не нравилось, когда к приготовленному им обеду опаздывали и тот вынужден был остывать).
 
Конечно, введенное правило оставляет существенный произвол в числе котлет, получаемых очередным явившимся лицеистом, и это число не в последнюю очередь  будет зависеть от предыдущего поведения лицеиста в столовой, а также от волшебных слов, произносимых им. Например, 6 котлет могут быть в  результате распределены по одной из следующих четырех схем: 3+2+1 (три котлеты первому из пришедших школьников, две - второму и одну - третьему), 4+2, 5+1 и 6 (все котлеты съедает счастливчик, пришедший первым).
 
Напишите программу, определяющую, каким количеством различных способов повар может распределить приготовленное лакомство среди школьников.
 
Входные данные
Входной файл содержит одно целое число N - количество приготовленных поваром котлет (0<=N<=200).
 
Выходные данные
Выходной файл должен содержать одно целое число, равное количеству возможных распределений котлет.

 

Примеры
№ Входные данные Выходные данные
1 6 4
 
Задача о рюкзаке
✓ 416✗ 937800средняяВойти и решать
Наименьшее число#23378
Дана последовательность чисел. Найти в ней наименьшее число.
 
Входные данные.
Задано сначала число N (количество чисел в последовательности), а затем
N чисел. Все числа - из диапазона Integer. N<=100
 
Выходные данные.
Выведите наименьшее число.
 
 
Линейный поиск
✓ 432✗ 305300лёгкаяВойти и решать
НВП на отрезке#23377
Нам дана числовая последовательность a1, ..., an . Напишите программу, отвечающую на запросы вида "найти длину наибольшей строго возрастающей подпоследовательности, все элементы которой находятся на отрезке с li-ого по ri-ый элемент".
Подпоследовательностью последовательности a1 , ..., an называется последовательность, которую можно получить путем удаления нескольких элементов ai (относительный порядок оставшихся элементов менять запрещается). Так, например, последовательность (2, 4) является подпоследовательностью последовательности (1, 2, 3, 4, 5) (можно удалить элементы 1, 3  и 5 ),  а последовательность (5, 1) - нет.
 
Входные данные
В первой строке записано целое число n  (1 <= n <= 3000 ) - число элементов в последовательности. Во второй строке записано n  чисел, разделенных пробелами - элементы последовательности. Все элементы не превосходят по модулю 109. В третьей строке записано одно целое число q  (1 <= q <= 105) - количество запросов. В следующих q  строках описаны запросы. Описание i -ого запроса - два числа li и rj (1 <= li <= ri <= n) ,  записанные через пробел.
 
Выходные данные
Выведите q чисел - ответы на запросы. Числа следует выводить по одному на строке в том же порядке, в котором запросы описаны во вводе.
 
Примеры
№ Входные данные Выходные данные
1 6
3 3 -5 7 4 9
6
1 4
1 2
2 3
1 5
3 5
2 5		 2
1
1
2
2
2
Динамическое программирование: последовательности
✓ 39✗ 4321 000средняяВойти и решать
По крышам!#23367
В городе будущего Иннополис еще во всю идет стройка, но уже сейчас построено n зданий. Крышу каждого здания можно представить как прямоугольник со сторонами, параллельными осям координат. Никакие здания не касаются и не пересекаются.

Инна любит гулять по крышам. Она стоит на крыше здания с номером 1 и хочет попасть на крышу здания с номером n.

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

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

Формат входных данных
В первой строке задано натуральное число n — число зданий в Иннополисе (n<= 105). В следующих n строках заданы крыши зданий. Каждая из этих строк содержит четыре целых числа xi1, yi1, xi2 и yi2 — координаты противоположных вершин прямоугольника, описывающего крышу здания (xi1 < xi2; yi1 < yi2) Гарантируется, что никакие два прямоугольника не имеют общих точек. Все координаты — неотрицательные целые числа и <= 109

Формат выходных данных
Выведите одно целое число — минимальное количество прыжков, которые Инна должна совер- шить, чтобы добраться с крыши здания 1 до крыши здания n. Если же Инна не может добраться до крыши n-го здания, выведите -1.
Ввод Вывод
4
0 0 3 2
1 6 4 8
1 3 4 5
7 7 10 9		 3
3
0 0 3 2
1 3 4 5
7 7 10 9		 -1
Динамическое программированиеДинамическое программирование
✓ 0✗ 71 200средняяВойти и решать
Монотонность#23363
Университет Иннополис готовится к проведению Летней школы олимпиадного программирования. Сейчас им нужно выбрать даты проведения.

Организаторы заметили, что школа проходит лучше, если настроение детей с каждым днем школы улучшается, также они заметили, что настро- ение школьников сильно зависит от погоды: в ясную погоду школьники веселее, чем в пасмурную. Организаторы запросили прогноз погоды на n дней, в которые можно провести школу. Для каждого дня они посчитали число ai — солнечность i-го дня. Теперь они хотят выбрать для про- ведения школы некоторый непрерывный отрезок дней, такой, что каждый следующий день школы солнечность строго больше, чем в предыдущий.

Помогите организаторам школы найти максимальное число дней, которые может идти школа.

Формат входных данных
В первой строке входного файла задано число n — число дней, в которые можно провести школу. Во второй строке заданы n ( 1<=n<=105) чисел ai — солнечности дней (0 <= ai <= 109 ).
Формат выходных данных
Выведите одно число: максимальное число дней, которое может идти школа так, чтобы каждый следующий день школы был солнечнее, чем предыдущий.
 
Вывод Ввод
6
2 0 3 7 4 5		 3
3
1 2 3		 3
4
1 1 1 1		 1
Линейный поиск
✓ 104✗ 239400лёгкаяВойти и решать
23361#23361
Выберите НЕверное утверждение:

1. Алгоритм приводит от исходных данных к результату
2. Алгоритм не должен обладать всеми свойствами сразу же
3. Алгоритм должен быть массовым
4. Алгоритм должен быть понятным
Линейные алгоритмы
—Войти и решать
Поделиться
Класснуть