Информатика

2 621 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Палиндром#29473
Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо. 
 
На вход программы поступает набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется из данных букв по указанным правилам составить палиндром наибольшей длины, а если таких палиндромов несколько, то выбрать первый из них в алфавитном порядке.
 
Входные данные
В первой строке входных данных содержится число N (1 <= N <= 100000). Во второй строке задается последовательность из N больших латинских букв (буквы записаны без пробелов).
 
Выходные данные
В единственной строке выходных данных выдайте искомый палиндром.
 
Ввод Вывод
3
AAB
 ABA
6
QAZQAZ
 AQZZQA
6
ABCDEF
 A
Алгоритмы обработкиИспользование сортировки
✓ 294✗ 532700средняяВойти и решать
Анаграммы#29469
Слово называется анаграммой другого слова, если оно может быть получено перестановкой его букв.
 
Формат входных данных
Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.
 
Формат выходных данных
Требуется вывести "YES"  – если введенные слова являются анаграммами друг друга, "NO"  – если нет.
Использование сортировкиСтроки
✓ 288✗ 366600лёгкаяВойти и решать
Спортсмен-победитель#29438
Имеется информация о времени (в секундах) прохождения трассы 25 спортсменов, участвовавших в лыжной гонке. Выведите результат спортсмена-победителя гонки.

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

Выходные данные
Выведите на экран результат спортсмена-победителя гонки. Гарантируется, что победитель гонки единственный.
 
Пример
№ Входные данные Выходные данные
1 78 35 79 47 104 53 58 86 108 94 90 27 33 88 17 15 37 98 14 67 76 45 94 97 46  14
Алгоритмы обработкиОдномерные массивы
✓ 6 246✗ 8 530200лёгкаяВойти и решать
Точки на прямой#28417
Маленький Петя очень любит точки. Недавно мама подарила ему n точек, лежащих на прямой OX. Пете стало интересно, сколькими способами он может выбрать три различные точки так, чтобы расстояние между двумя самыми удаленными из выбранных точек не превышало d.
Обратите внимание, что порядок точек внутри выбранной тройки значения не имеет.

Входные данные
Первая строка содержит два целых числа: n и d (1 ≤ n ≤ 105; 1 ≤ d ≤ 109). Следующая строка содержит n целых чисел x1, x2, ..., xn, по модулю не превосходящих 109 — x-координаты точек, подаренных Пете.
Гарантируется, что координаты точек во входных данных строго возрастают.

Выходные данные
Выведите единственное целое число — количество троек точек, в которых расстояние между двумя самыми удаленными точками не превосходит d.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
 
Ввод Вывод
4 3
1 2 3 4
 4
4 2
-3 -2 -1 0
 2
5 19
1 10 20 30 50
 1
 
В первом примере нам подходит любая тройка различных точек.
Во втором примере нам подходят всего 2 тройки: {-3, -2, -1} и {-2, -1, 0}.
В третьем примере нам подходит одна тройка: {1, 10, 20}.
 
"Два указателя"Комбинаторика
✓ 354✗ 711600лёгкаяВойти и решать
Таблица умножения#28405
Дано число N (0 < N < 100)Напишите программу, которая выводит на экран таблицу умножения на заданное число.

Входные данные
С клавиатуры задается одно число N.

Выходные данные 
Необходимо вывести таблицу умножения (см примеры). Для знака умножения используйте английскую букву x. Знаки равенства (=) и умножения (x) отделяется с двух сторон одним пробелом. Других пробелов нет.
 
Примеры
Входные данные 
7

Выходные данные 
7 х 1 = 7
7 х 2 = 14
7 х 3 = 21
7 х 4 = 28
7 х 5 = 35
7 х 6 = 42
7 х 7 = 49
7 х 8 = 56
7 х 9 = 63
Ввод, вывод данныхЦикл for
✓ 223✗ 695200лёгкаяВойти и решать
Два одинаковых массива#28345
На вход подаются два массива A и В, отсортированных по неубыванию. Вам нужно узнать, существует ли такое число, которое содержится в обоих массивах. Если такое число существует, выведите 1, иначе выведите 0.

Входные данные
В первой строке записано натуральные числа N и M– количество элементов первого и второго массива соответственно,  (1 <= N, M <= 108). В следующих двух строках записаны элементы массива A и B. Во второй строке - элементы массива A, в третьей - элементы массива B. Все элементы массива неотрицательные числа, не превышающие 1018.

Выходные данные
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 4 4
1 2 3 4
2 4 7 8		 1
"Два указателя"Хеш
✓ 807✗ 1 970500лёгкаяВойти и решать
Пары точек#28344
На прямой находятся N точек. Требуется подсчитать количество пар индексов (i, j) таких, что i не равно j и |ai - aj|  <= D.

Формат входных данных
В первой строке находятся два числа N и D (1 <= N <= 105, 1 <= D <= 109). Во второй строке находится N неотрицательных чисел, каждое из котороых не более чем 2*109.

Формат выходных данных
Выведите на экран ответ на задачу.
"Два указателя"Использование сортировки
✓ 529✗ 2 794600лёгкаяВойти и решать
Тильда-омега-лямбда-исчисление#27311
Тильда-омега-лямбда-исчисление - ещё более инновационная разработка "British Scientists, Inc" в сфере функционального программирования. Его отличие от омега-лямбда-исчисления только в возможности ставить квадратные и фигурные скобки. Планировались также скобки в форме слоников, но стандарт ЮНИКОД у компании изменить не получилось. 
На вход подаётся тильда-омега-лямбда-выражение длиной не более 10^7 символов. Нужно вывести результат его тильда-иззи-редукции, работающей так же, как и иззи-редукция для омега-лямбда-выражений, но с учётом квадратных и фигурных скобок.

Напомним, иззи-редукция - одна из операций над такими выражениями. При её выполнении проверяется, является ли скобочная последовательность в выражении правильной. Термы при этом игнорируются. Если последовательность правильная - она превращается в терм gg, если нет - в терм wp. 
 

 

Примеры
№ Входные данные Выходные данные
1 main{izzy[lol](ttt)} gg
Конечные автоматыСтроки
✓ 96✗ 43500лёгкаяВойти и решать
Омега-лямбда-исчисление#27310
Омега-лямбда-исчисление - инновационная разработка "British Scientists, Inc" в сфере формальной логики. Любое выражение омега-лямбда-исчисления состоит из круглых скобок и термов (термом может быть любая последовательность из букв латинского алфавита). 
Иззи-редукция - одна из операций над такими выражениями. При её выполнении проверяется, является ли скобочная последовательность в выражении правильной. Термы при этом игнорируются. Если последовательность правильная - она превращается в терм gg, если нет - в терм wp. 
На вход подаётся омега-лямбда-выражение длиной не более 107 символов. Нужно вывести результат его иззи-редукции.
 

 

Примеры
№ Входные данные Выходные данные
1 a(b(xx)f(g(x))m(y)) gg
Линейные алгоритмыСтроки
✓ 115✗ 197600лёгкаяВойти и решать
Квадратный корень и квадратный квадрат#27292
Найдите такое число x, что \(x^2 + \sqrt{x} = C\) , с точностью не менее 6 знаков после точки.
 
Входные данные
В единственной строке содержится вещественное число \(1 <=C <=10^{10}\).
 
Выходные данные
Выведите одно число — искомый \(x\).
 
Примеры
№ Входные данные Выходные данные
1 2.0000000000 1.000000000
2 18.0000000000 4.000000000
 
Бинарный поиск значения функцииБинарный поиск по ответу
✓ 415✗ 467500лёгкаяВойти и решать
Приближенный двоичный поиск#27279
Реализуйте алгоритм приближенного бинарного поиска.
 
Формат входных данных
В первой строке входных данных содержатся числа N и K (\(0< N,\ K <100001\)). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию. В третьей строке вводится K чисел второго массива.
Каждое число в обоих массивах по модулю не превосходит \(2 \cdot 10^9\).
 
Формат выходных данных
Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.
Бинарный поискБинарный поиск в массиве
✓ 793✗ 2 038600лёгкаяВойти и решать
Кладоискатель#27213
Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера N×M (1 ≤ N, M ≤ 100 , N×M ≤ 100). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).
 
В одной из клеток находится клад, который и хочет достать Вася. В лабиринте есть K входов, из которых Вася может начать свой путь.
 
Требуется определить, с какого входа Васе нужно начать свой путь, чтобы пройденное расстояние до клада было наименьшим. Если таких входов несколько, нужно вывести вход с наименьшим номером.
 
Входные данные
Первая строка содержит 2 числа N и M, задающие размеры лабиринта. Далее следует описание лабиринта: N строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
 
В (N+2)-й строке находится число K (1 ≤ K ≤ NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в xi-й строке и в yi-м столбце (1 ≤ xi ≤ N, 1 ≤ yi ≤ M). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.
 
Выходные данные
Необходимо вывести одно число - искомый номер входа (нумерация начинается с 1). Если до сокровища невозможно добраться, выведите -1.

Примеры
№ Входные данные Выходные данные
1
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
 1
2
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
 -1
Алгоритм ФлойдаОбход в ширину
✓ 144✗ 135700средняяВойти и решать
Есть ли цикл?#27212
Дан ориентированный граф. Требуется определить, есть ли в нем цикл.
 
Входные данные
В первой строке вводится число вершин N≤ 50. Далее в N строках следуют по N чисел, каждое из которых – 0 или 1. j-ое число в i-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из i-ой вершины в j-ую. Гарантируется, что на диагонали матрицы будут стоять нули.
 
Выходные данные
Выведите 0, если в заданном графе цикла нет, и 1, если он есть.

Примеры
№ Входные данные Выходные данные
1
3
0 1 0
0 0 1
0 0 0
 0
2
3
0 1 0
0 0 1
1 0 0
 1
Алгоритм ФлойдаОбход в глубину
✓ 814✗ 1 607500лёгкаяВойти и решать
Вычислитель#27121
Дана блок-схема алгоритма. Какое целое положительное число w необходимо подать на вход, чтобы после завершения алгоритма получилось значение s ? В ответе укажите целое число. Примечание. Операция mod вычисляет остаток от деления первого аргумента на второй. Операция div вычисляет частное от целочисленного деления первого аргумента на второй.
Задача на реализациюЗадачи на моделирование
✓ 41✗ 125600лёгкаяВойти и решать
Auxiliary Project#27115
Anna has just finished her course project. She has a lot of seven-segment LED displays as leftovers and a small power source. Each display consumes power proportionally to the number of lit segments, e.g. ‘9’ consumes twice more power than ‘7’.


Anna wonders what is the maximum possible sum of digits she is able to achieve, if her power source is able to light n segments, and she wants to light exactly n segments.
Input
The single line of the input contains one integer n — the number of segments that should be lit (2 ≤ n ≤ 106 ).
Output
Output a single integer — the maximum possible sum of digits that can be displayed simultaneously.
Input Output
4 4
7 11
6 14


In the first example, a single ‘4’ should be displayed (‘7’ has greater value, but has only three segments). In the second example ‘4’ and ‘7’ should be displayed, in the third one — two ‘7’s.
Вывод формулыРазбор случаев
✓ 20✗ 10700средняяВойти и решать
Двоичные строки заданной длины в обратном порядке#27090

По данному числу N выведите все строки длины N из нулей и единиц в обратном лексикографическом порядке.

Входные данные
Задано единственное число N (\(1 <= N <= 10\)).
 
Выходные данные
Необходимо вывести все строки длины N из нулей и единиц в обратном лексикографическом порядке.

 
Примеры
№ Входные данные Выходные данные
1 2 11
10
01
00
Простые задачи на переборРазмещения с повторениями
✓ 149✗ 83600лёгкаяВойти и решать
Опасные отходы#27085
При переработке радиоактивных материалов образуются отходы двух типов: А (неопасные) и B (особо опасные). Отходы каждого типа упаковываются в контейнеры, а затем контейнеры складываются в стопки. Стопка считается взрывоопасной, если в ней есть три или больше контейнеров с особо опасными отходами (типа B) расположены рядом. Для заданного количества контейнеров N определите, сколько есть способов составить безопасную стопку.
 
Входные данные
Входная строка содержит натуральное число – количество контейнеров N в стопке (1 <= N <= 35).
 
Выходные данные
Программа должна вывести одно число – количество способов составить безопасную стопку из N контейнеров.

 
Примеры
№ Входные данные Выходные данные
1 3 7
Динамическое программирование: один параметрРекуррентные последовательности
✓ 88✗ 156700средняяВойти и решать
Зоомагазин-2#27084
В зоомагазине нужно расставить в один ряд клетки с кошками и собаками. В ряд помещается N клеток, при этом есть одно ограничение: нельзя ставить подряд три клетки с животными одного вида (иначе они передерутся). Предполагается, что в магазине есть неограниченное количество клеток с кошками и собаками. Определите, сколькими безопасными способами можно расставить N клеток в ряд.
 
Входные данные
Входная строка содержит одно натуральное число – количество клеток в ряду N .
 
Выходные данные
Программа должна вывести количество безопасных способов расстановки N клеток в ряд.
 
Ввод Вывод
5 16


 
Динамическое программированиеДинамическое программирование: два параметра
✓ 49✗ 23700средняяВойти и решать
Площадь треугольника#27074
Входные данные
Шесть чисел – координаты трёх вершин треугольника.
 
Выходные данные
Одно число – величина площади треугольника.
 
Примеры
№ Входные данные Выходные данные
1 1 1 2 4 3 2 2.50000
Вычислительная геометрияЭлементарная геометрия
✓ 660✗ 1 268300лёгкаяВойти и решать
Легкая, вариант-1#27062
Сервер одной крупной аналитической компании делает резервное копирование всех данных каждые пол часа. Системный администратор Илья Филиппович Яковлев заступит сегодня на смену в известное время. Он знает, что сервер делает резервное копирование в полночь (00:00:00), но не может посчитать, когда же было последнее резервное копирование на момент его заступления на смену.

Ваша задача — написать программу, которая определит время последнего резервного копирования перед началом смены Ильи Филипповича. Считается, что резервное копирование происходит мгновенно. Таким образом, если Илья Филиппович заступает в момент резервного копирования, считается, что оно происходит уже в его смену
 
Формат входного файла
 
На вход программы подается строка, в которой находится время заступления Ильи Филипповича в формате hh:mm:ss, где hh обозначает часы в 24-часовом формате, mm — минуты, а ss — секунды. Гарантируется, что время корректно. 
 
Формат выходного файла
Требуется вывести время последнего резервного копирования в аналогичном формате. 
 
Пример входных и выходных данных
 
Ввод Вывод
12:55:00 12:30:00
00:00:00 23:30:00
18:30:03 18:30:00
Дата и времяЗадачи на моделирование
✓ 16✗ 43700средняяВойти и решать
Поделиться
Класснуть