Информатика

15 724 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Количество способов топологической сортировки#29453
Дан связный ациклический ориентированный граф. Каждая вершина данного графа кроме листьев имеет по 2 сына.
Найдите количество способов топологически отсортировать, зная только количество вершин.
 
Входные данные
Входная строка содержит одно натуральное число n - кол-во вершин (n <= 1000).

Выходные данные  
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 7 48
Топологическая сортировка
✓ 76✗ 293800средняяВойти и решать
Лексикографически минимальная топологическая сортировка#29452
Дан связный ациклический ориентированный граф. Найдите его лексикографически минимальную топологическую сортировку.
 
Входные данные
В первой строке вводится количество вершин n (1 <= n <= 10000). Во второй строке водится n чисел ai (0 <= ai <= n, ai != i). Значение ai - предок вершины с номером i (вершины нумеруются с 1). Если ai = 0, то вершина i является корнем и не имеет предков, гарантируется, что таких вершин ровно 1.
 
Выходные данные
Решение должно вывести n чисел - лексикографически минимальную топологическую сортировку.
 
Примеры
№ Входные данные Выходные данные
1
4
2 0 1 2
 2 1 3 4
Топологическая сортировка
✓ 40✗ 136900средняяВойти и решать
Расписание для 9И#29451
В августе Владлена Александровна решила составить расписание для 9 «И» класса. Она считает, что уроков в один день должно быть N (2<=N<=8). От учителей она получила M (1<=N) запросов. Так как Владлена Александровна учитель географии, то с компьютером опыт работы у нее не такой как у вас, она просит вас о помощи, решите эту «невыполнимую» задачу, соблюдая запросы учителей.

Входные данные:  В первой строке входных данных содержится число N – кол-во уроков и число M – количество последовательных пар уроков наверное.
В следующих M строках задаются 2 слова, которые обозначают названия предметов.
Известно что, граф не может зациклиться и предметы не могут быть в расписании 2 раза
Слова, которые можно вводить: PE,Math, Russian, Biology,Geometry, Literature, Science, Geography
 
Выходные данные: Задача — выстроить предметы в подходящем для всех пар порядке.
 
Ввод Вывод
3 2
PE Math
Math Literature		 PE
Math
Literature

(c) Бганцова А., 2018 г.
Топологическая сортировка
✓ 14✗ 19700средняяВойти и решать
Спасти новобранцев#29450
Группа солдат-новобранцев прибыла в армейскую часть N777. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо. 
 
Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине. 
 
После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен. 
 
Входные данные 
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны. 
 
Выходные данные 
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений. 
Примеры
№ Входные данные Выходные данные
1
4 5 
1 2 
2 3 
3 4 
1 4 
4 1
 No

(c) Пасынков С., 2018 г.
Топологическая сортировка
✓ 29✗ 25500лёгкаяВойти и решать
Дороги королевства#29449
В одном королевстве n городов и m дорог. У каждого города есть своё название, состоящее из строчных латинских букв. Но королю не нравится, что есть дороги, ведущие из города с названием, являющимся лексикографически меньшим названия конечного. Он захотел это исправить, поменяв города, к которым относятся те или иные названия. Сам он, конечно, не справится. Помогите ему в этом! 
 
Формат файла входных данных: 
Первая строка содержит два целых числа n и m (2 <= n <= 1000; 1 <= M <= 10000) - количество городов и дорог в королевстве соответственно. 
 
Вторая строка содержит n строк, описывающих города. Описание задаётся строкой из строчных латинских букв - названия города. 
 
Далее в m строках перечислены дороги. Каждая дорога задаётся парой чисел - номерами начального и конечного городов соответственно. Дороги односторонние. 
 
Формат файла выходных данных: 
Вывести n чисел, каждое из которых обозначает номер названия, соответствующего i-ому городу. Если решения не существует, вывести -1.
 
Ввод Вывод
4 4 
aaa bacc cqe de 
1 4 
4 2 
4 3 
3 2
 1 4 3 2
3 3 
fi bru a 
1 2 
2 3 
3 1
 -1
(с) Филимонов И.
Топологическая сортировка
✓ 19✗ 8600лёгкаяВойти и решать
OLD or YOUNG#29447
Известен возраст группы людей в списке. Какой человек указан в списке раньше: самый старый или самый молодой? Если самых старых (молодых) несколько, то учитывайте того, кто встретился раньше.

Входные данные
В первой строке вводится число N - количество людей в списке (1<N<=100). Во второй строке вводятся N чисел - возраст людей в списке (каждое число в диапазоне от 0 до 120).

Выходные данные
Вывести на экран слово OLD,  если самый старый человек встречается в списке раньше, иначе слово YOUNG, если раньше встречается самый молодой.
 
Примеры
№ Входные данные Выходные данные
1
10
67 99 43 95 32 107 65 104 1 31 
 OLD
2
10
1 99 43 95 32 107 65 104 1 31 
 YOUNG
Одномерные массивы
✓ 200✗ 342500лёгкаяВойти и решать
Первый самый младший#29445
В массиве хранится информация о годе рождения каждого из N человек. Определить порядковый номер первого самого младшего по возрасту человека. 

Входные данные
В первой строке задается число N - число человек (0<N<=50). Во второй строке задаются года рождения N человек (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер первого самого младшего человека.
 
Примеры
№ Входные данные Выходные данные
1 5
1904 1903 1905 1905 1903		 3
Одномерные массивы
✓ 116✗ 427500лёгкаяВойти и решать
Последний самый старший#29444
В массиве хранится информация о годе рождения каждого из N человек. Определить порядковый номер последнего самого старшего по возрасту человека. 

Входные данные
В первой строке задается число N - число человек (0<N<=50). Во второй строке задаются года рождения N человек (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер последнего самого старшего человека.
 
Примеры
№ Входные данные Выходные данные
1 5
1904 1903 1905 1905 1903		 5
Одномерные массивы
✓ 161✗ 345500лёгкаяВойти и решать
Первый самый старший#29443
В массиве хранится информация о годе рождения каждого из N человек. Определить порядковый номер первого самого старшего по возрасту человека. 

Входные данные
В первой строке задается число N - число человек (0<N<=50). Во второй строке задаются года рождения N человек (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер первого самого старшего человека.
 
Примеры
№ Входные данные Выходные данные
1 5
1904 1903 1905 1905 1903		 2
Одномерные массивы
✓ 101✗ 351500лёгкаяВойти и решать
Последний с минимальной премией#29442
В массиве хранится информация о годовой премии у N сотрудников фирмы. Определить порядковый номер последнего сотрудника с самой низкой годовой премией.

Входные данные
В первой строке задается число N - количество сотрудников фирмы (0<N<=50). Во второй строке задаются значения премий N сотрудников фирмы (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер последнего сотрудника с минимальной премией.
 
Примеры
№ Входные данные Выходные данные
1 5
4 3 5 3 5		 4
Одномерные массивы
✓ 197✗ 450400лёгкаяВойти и решать
Первый с минимальной премией#29441
В массиве хранится информация о годовой премии у N сотрудников фирмы. Определить порядковый номер первого сотрудника с самой низкой годовой премией.

Входные данные
В первой строке задается число N - количество сотрудников фирмы (0<N<=50). Во второй строке задаются значения премий N сотрудников фирмы (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер первого сотрудника с минимальной премией.
 
Примеры
№ Входные данные Выходные данные
1 5
4 3 5 5 3		 2
Одномерные массивы
✓ 123✗ 316400лёгкаяВойти и решать
Последний самый быстрый#29440
В массиве хранится информацию о максимальной скорости каждой из N марок легковых автомобилей. Определить порядковый номер последнего встретившегося автомобиля с самой высокой скоростью.

Входные данные
В первой строке задается число N - количество авомобилей (0<N<=50). Во второй строке задаются значения скоростей N автомобилей (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер последнего встретившегося автомобиля с самой высокой скоростью.
 
Примеры
№ Входные данные Выходные данные
1 5
4 3 5 5 3		 4
Одномерные массивы
✓ 84✗ 188500лёгкаяВойти и решать
Первый самый быстрый#29439
В массиве хранится информацию о максимальной скорости каждой из N марок легковых автомобилей. Определить порядковый номер первого встретившегося автомобиля с самой высокой скоростью.

Входные данные
В первой строке задается число N - количество авомобилей (0<N<=50). Во второй строке задаются значения скоростей N автомобилей (N чисел, каждое число положительное, не больше 105).

Выходные данные
Вывести номер первого самого быстрого автомобиля.
 
Примеры
№ Входные данные Выходные данные
1 5
4 3 5 3 5		 3
Одномерные массивы
✓ 103✗ 240400лёгкаяВойти и решать
Сигма 2015#29437

В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 100 000. Все числа не превышают 10 000. Временем, в течение которого происходит передача, можно пренебречь. Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным -1.
 

Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).


Входные данные  
В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что \(N>6\). В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.

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

 

Примеры
№ Входные данные Выходные данные
1 12
45
5
3
1
7
23
21
20
19
18
1
7		 18
ЕГЭ - вычислительные задачи
✓ 334✗ 1 368700средняяВойти и решать
Сокращение дроби#29423
Дана дробь \(a \over b\). Требуется ее сократить, то есть записать это же число в виде \(c \over d\), где c — целое число, d - натуральное число и d минимальное возможное.
 
Входные данные 
Вводятся два целых числа a и b (\(-100<=a<=100,\ 0<b<=100\)).

Выходные данные 
Выведите два числа c и d.
 
Примеры
№ Входные данные Выходные данные
1 3 6  1 2
2 -2 5 -2 5
НОД и алгоритм Евклида
✓ 1 331✗ 3 701400лёгкаяВойти и решать
Расстояние Дамерау-Левенштейна#28421
Одной из наиболее распространенных опечаток при наборе текста является перестановка двух соседних символов, например, вместо слова «программа» набрано слово «прогармма». Расстояние Левенштейна не учитывает такие опечатки: при вычислении расстояния Левенштейна одна перестановка будет считаться за два редактирования (например, удаление и вставка символа).
 
При вычислении расстояния Дамерау-Левенштейна, помимо операций замены, вставки и удаления символа допускается еще операция перестановки двух соседних символов. При этом между переставленными символами нельзя вставлять другие символы.
 
Определите расстояние Дамерау-Левенштейна для двух данных строк.

Входные данные
Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.
 
Выходные данные
Требуется вывести одно число – расстояние Дамерау-Левенштейна для данных строк.
 
Примеры
№ Входные данные Выходные данные
1
XABCDE
ACBYDF
 4
Динамическое программирование по подстрокам
✓ 200✗ 409700средняяВойти и решать
Проверка подпоследовательности#28420
Проверить, является ли последовательность подпоследовательностью заданного массива.
 
Входные данные
В первой строке входных данных содержится число N – длина заданной последовательности (1 ≤ N ≤ 10000). Во второй строке заданы члены исходной последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.
 
В третьей строке записано число M – длина подпоследовательности (1 ≤ M ≤ 10000). В четвертой строке задаются члены подпоследовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

Выходные данные
Вывести "YES" если последовательность заданная в 4-ой строке является подпоследовательность заданного массива и "NO", если не является.
 
Ввод Вывод
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 5 4 6 7 8 9 10		 NO
10
1 2 3 4 5 6 7 8 9 10
9
1 2 3 5 6 7 8 9 10		 YES

Пояснение.
Не путать "подпоследовательность" с "подстрокой".
"Два указателя"
✓ 364✗ 785500лёгкаяВойти и решать
Шаблон с ? и *#28419
Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.
 
Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выдать сообщение, что такой строки не существует.
 
Входные данные
Заданные шаблоны записаны в первых двух строках входных данных. Длина каждого шаблона не превосходит 80 символов.

Выходные данные
Выведите строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение "No solution!"
 
Примеры
№ Входные данные Выходные данные
1
AB?
*BC
 ABC
Динамическое программирование
✓ 21✗ 1741 200средняяВойти и решать
Расстояние по Левенштейну#28418
Дана текстовая строка. С ней можно выполнять следующие операции:
  1. Заменить один символ строки на другой символ.
  2. Удалить один произвольный символ.
  3. Вставить произвольный символ в произвольное место строки.
 
Например, при помощи первой операции из строки "СОК" можно получить строку "СУК", при помощи второй операции - строку "ОК", при помощи третьей операции - строку "СТОК.
Минимальное количество таких операций, при помощи которых можно из одной строки получить другую, называется стоимостью редактирования или расстоянием Левенштейна.
 
Определите расстояние Левенштейна для двух данных строк.
 
Входные данные
Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.
 
Выходные данные
Требуется вывести одно число – расстояние Левенштейна для данных строк.
 
 
Примеры
№ Входные данные Выходные данные
1
ABCDEFGH
ACDEXGIH
 3


 
Динамическое программирование по подстрокам
✓ 314✗ 483500лёгкаяВойти и решать
Наибольшая общая подпоследовательность с восстановлением ответа#28416
Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.
 
Входные данные
В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.
 
В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.
 
Выходные данные
Требуется вывести наибольшую общую подпоследовательность данных последовательностей, через пробел.
 
Примеры
№ Входные данные Выходные данные
1
3
1 2 3
3 
2 3 1
 2 3
Динамическое программирование: последовательности
✓ 332✗ 489500лёгкаяВойти и решать
Поделиться
Класснуть