Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Суммарная длина дорог#33227

Найдите суммарную длину всех дорог в городе Новые Васюки. Схема дорог задана в виде весовой матрицы графа. На некоторых дорогах введено одностороннее движение. Если длины дорог из пункта А в пункт Б разные, это означает, что есть две разные дороги.

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

В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – длины дорог между каждой парой перекрёстков. Ноль означает, что дороги между этими перекрёстками нет.

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

Программа должна вывести одно число – суммарную длину дорог. Дороги с двусторонним движением нужно считать только один раз.

Ввод	Вывод
5 0 2 3 4 0 2 0 5 0 7 3 6 0 8 0 0 0 0 0 0 0 7 0 9 0	44

Алгоритмы на графах

✓ 498✗ 364500лёгкаяВойти и решать

Количество дорог#33226

Напишите программу, которая считает количество дорог в городе Новые Васюки. Схема дорог задана как матрица смежности графа. На некоторых дорогах введено одностороннее движение.

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

В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему дорог.

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

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

Ввод	Вывод
5 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0	7

Алгоритмы на графах

✓ 473✗ 335500лёгкаяВойти и решать

Сортировка по цифрам числа 2#33207

Дано N трехзначных чисел (1<=N<=1000). Необходимо вывести их в порядке возрастания.

Нельзя использовать встроенную сортировку

Пример
Входные данные

639 265 915 993 436 202 573 906 490

Выходные данные
202 265 436 490 573 639 906 915 993

Квадратичные сортировки Одномерные массивы

✓ 49✗ 144600лёгкаяВойти и решать

Сортировка по цифрам числа 1#33206

Дано N двузначных положительных чисел. Необходимо вывести их в порядке увеличения первой цифры. Если первые цифры одинаковы, то вывести их в порядке следования в исходном массиве.

Формат входных данных
В первой строке записано натуральное число N (1<=N<=1000). Вторая строка содержит n двузначных положительных чисел nums_i (1 ≤ i ≤ n, 10 ≤ nums_i ≤ 99).

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

Квадратичные сортировки Одномерные массивы

✓ 64✗ 88600лёгкаяВойти и решать

Пятый самый легкий#33205

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел m_i - вес i-го предмета (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵).

Формат выходных данных
Напечатайте массу предмета, являющегося "пятым самым легким предметом".

Квадратичные сортировки Одномерные массивы

✓ 167✗ 324400лёгкаяВойти и решать

Средние в шеренге#33203

Формат входных данных
В первой строке записано натуральное число n (n < 100, n - четное). Вторая строка содержит n положительных целых чисел m_i - рост i-го учащегося (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵).

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

Квадратичные сортировки Одномерные массивы

✓ 340✗ 409400лёгкаяВойти и решать

Использование сортировки 2#33202

В каждом из двух классов учатся по n человек (10 <= n <= 30). Известны средний балл каждого ученика каждого класса, подсчитанные по ряду предметов (все значения целые). Определить, в каком классе у "третьего из самых успевающих учеников" средняя оценка больше. Вывести цифру "1" - для первого класса, "2" - для второго. Если оценки равны, вывести эту оценку.

Формат входных данных
В первой строке записано натуральное число n (n < 100) - количество учеников в каждом классе . Вторая строка содержит n положительных целых чисел class1_i - средний балл i-го ученика первого класса (1 ≤ i ≤ n, 1 ≤ class1_i ≤ 10⁵). Третья строка содержит n положительных целых чисел class2_i - средний балл i-го ученика первого класса (1 ≤ i ≤ n, 1 ≤ class2_i ≤ 10⁵).

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

Квадратичные сортировки Одномерные массивы

✓ 51✗ 132700средняяВойти и решать

Банкет#33147

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

Входные данные: В первой строке входных данных содержатся два числа: N и M (1 <= N,M <= 100), где N – количество ОВП, а M – количество пар ОВП, которые не могут сидеть за одним столом. В следующих M строках записано по 2 числа – пары ОВП, которые не могут сидеть за одним столом.

Выходные данные: Если способ рассадить ОВП существует, то выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.

Примеры

№	Входные данные	Выходные данные
1	3 2 1 2 1 3	YES 1

Обход в глубину

✓ 440✗ 503600лёгкаяВойти и решать

Баобаб#33146

Дан неориентированный невзвешенный граф. Необходимо определить, является ли он деревом.

Формат входных данных
В первой строке содержится одно натуральное число N (N ≤ 100) - количество вершин в графе. Далее в N строках по N чисел - матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.

Формат выходных данных
Вывести "YES", если граф является деревом, и "NO" иначе.

Обход в глубину

✓ 602✗ 878500лёгкаяВойти и решать

Ход конем - 2#33143

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

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

Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 15\)).

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

Примеры

№	Входные данные	Выходные данные
1	4 4	2
2	7 15	13309

Динамическое программирование: два параметра

✓ 241✗ 405700средняяВойти и решать

Ход конем_1#33142

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз (смотри рисунок).

Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 50\)).

Примеры

№	Входные данные	Выходные данные
1	4 4	2

Динамическое программирование: два параметра

✓ 509✗ 688500лёгкаяВойти и решать

Имена#33141

На далекой планете Тау Кита есть непонятные нам обычаи. Например, таукитяне очень необычно для землян выбирают имена своим детям. Родители так выбирают имя ребенку, чтобы оно могло быть получено как удалением некоторого набора букв из имени отца, так и удалением некоторого набора букв из имени матери. Например, если отца зовут «abacaba», а мать — «bbccaa», то их ребенок может носить имена «a», «bba», «bcaa», но не может носить имена «aaa», «ab» или «bbc». Возможно, что имя ребенка совпадает с именем отца и/или матери, если оно может быть получено из имени другого родителя удалением нескольких (возможно, ни одной) букв.

Пусть отец по имени X и мать по имени Y выбирают имя своему новорожденному ребенку. Так как в таукитянских школах учеников часто вызывают к доске в лексикографическом порядке имен учеников, то есть в порядке следования имен в словаре, то они хотят выбрать своему ребенку такое имя, чтобы оно лексикографически следовало как можно позже.

- Формально, строка S лексикографически больше строки T, если выполняется одно из двух условий: строка T получается из S удалением одной или более букв с конца строки S;

- первые (i - 1) символов строк T и S не различаются, а буква в i-й позиции строки T следует в алфавите раньше буквы в i-й позиции строки S.

Требуется написать программу, которая по именам отца и матери находит лексикографически наибольшее имя для их ребенка.

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

Первая строка входного файла содержит X — имя отца. Вторая строка входного файла содержит Y — имя матери. Каждое имя состоит из строчных букв латинского алфавита, включает хотя бы одну букву и имеет длину не более 105 букв.

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

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

Ввод	Вывод
abcabca abcda	ca
ccba accbbaa	ccba

"Два указателя"

✓ 3✗ 231 100средняяВойти и решать

Кассы#33140

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

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

Сначала вводится одно целое число N (0<N<=10000).

В каждой из следующих N строк через пробел расположены 6 целых чисел, первые три из которых обозначают время открытия кассы в часах, минутах и секундах (часы — целое число от 0 до 23, минуты и секунды — целые числа от 0 до 59), оставшиеся три — время закрытия в том же формате. Числа разделены пробелами.

Время открытия означает, что в соответствующую ему секунду касса уже работает, а время закрытия — что в соответствующую секунду касса уже не работает. Например, касса, открытая с 10 ч 30 мин 30 с до 10 ч 35 мин 30 с, ежесуточно работает 300 секунд.

Если время открытия совпадает с временем закрытия, то касса работает круглосуточно. Если первое время больше второго, то касса начинает работу до полуночи, а заканчивает — на следующий день.

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

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

Ввод	Вывод
3 1 0 0 23 0 0 12 0 0 12 0 0 22 0 0 2 0 0	7200
2 9 30 0 14 0 0 14 15 0 21 0 0	0
2 14 0 0 18 0 0 10 0 0 14 0 1	1

"Два указателя"

✓ 17✗ 90800средняяВойти и решать

Двудольный граф#33138

Граф называется двудольным, если его вершины можно раскрасить в два цвета так, что нет ребер, соединяющих вершины одинакового цвета (то есть каждое ребро идет из вершины 1-го цвета в вершину 2-го).

Дан граф. Требуется проверить, является ли он двудольным, и если да, то раскрасить его вершины.

Входные данные
В первой строке задано сначала число N - количество вершин графа (не превышает 100). Далее идет матрица смежности - матрица размером NxN из 0 и 1 (0 обозначает отсутствие ребра, 1 - наличие). Граф неориентированный, без петель.

Выходные данные
В первую строку выведите одно из сообщений YES или NO (в зависимости от того, является ли граф двудольным или нет). В случае ответа YES, во второй строке выведите N чисел - цвета, в которые нужно раскрасить вершины: для первого цвета используйте значение 1, для второго цвета - значение 2. Первая вершина должна иметь цвет 1.

Примеры

№	Входные данные	Выходные данные
1	3 0 1 1 1 0 1 1 1 0	NO
2	3 0 1 1 1 0 0 1 0 0	YES 1 2 2

Применение обхода в глубину

✓ 758✗ 1 459500лёгкаяВойти и решать

Долой списывание!#33137

Во время контрольной работы профессор Флойд заметил, что некоторые студенты обмениваются записками. Сначала он хотел поставить им всем двойки, но в тот день профессор был добрым, а потому решил разделить студентов на две группы: списывающих и дающих списывать, и поставить двойки только первым.

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

Входные данные: В первой строке находятся два числа N и M - количество студентов и количество пар студентов, обменивающихся записками (1<=N<=100, 0<=M<=(N(N−1))/2. Далее в M строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.

Выходные данные: Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.

Примеры

№	Входные данные	Выходные данные
1	3 2 1 2 2 3	YES
2	3 3 1 2 2 3 1 3	NO

Применение обхода в глубину

✓ 620✗ 617500лёгкаяВойти и решать

Поиск компонент сильной связности#33136

Вам задан ориентированный граф с N вершинами и M ребрами (1<=N<=20000, 1<=M<=200000). Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

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

Граф задан во входном файле следующим образом: первая строка содержит числа N и M. Каждая из следующих M строк содержит описание ребра — два целых числа из диапазона от 1 до N — номера начала и конца ребра.

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

На первой строке выведите число K — количество компонент сильной связности в заданном графе. На следующей строке выведите N чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Ввод	Вывод
10 19 1 4 7 8 5 10 8 9 9 6 2 6 6 2 3 8 9 2 7 2 9 7 4 5 3 6 7 3 6 7 10 8 10 1 2 9 2 7	2 1 2 2 1 1 2 2 2 2 1

Компоненты сильной связности

✓ 49✗ 51700средняяВойти и решать

От списка ребер к матрице смежности, неориентированный вариант#33132

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

Формат входных данных
В первой строке задаются числа n (\(1<=n<=100\)) – количество вершин в графе и m (\(1<=m<=n(n - 1)/2\)) – количество ребер. Далее следует m пар чисел – ребра графа (каждая пара чисел в отдельной строке).

Формат выходных данных
Выведите матрицу смежности заданного графа.

Способы задания графа

✓ 1 360✗ 876300лёгкаяВойти и решать

От матрицы смежности к списку ребер, неориентированный вариант#33131

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

Формат входных данных
Входные данные включают число n (\( 1<=n<=100\)) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрицу смежности.

Формат выходных данных
Выведите список ребер заданного графа (в любом порядке).

Способы задания графа

✓ 1 118✗ 605300лёгкаяВойти и решать

Проверка на неориентированность#33130

По заданной квадратной матрице n×n из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

Формат входных данных
В первой строке задается число n (\(1<=n<=100\)) – размер матрицы. Затем задается сама матрица - n строк по n чисел, каждое из которых равно 0 или 1.

Формат выходных данных
Выведите «YES», если приведенная матрица может быть матрицей смежности простого неориентированного графа, и «NO» в противном случае

Способы задания графа

✓ 1 267✗ 2 390400лёгкаяВойти и решать

Петли#33129

По заданной матрице смежности неориентированного графа определите, содержит ли он петли.

Формат входных данных
В первой строке задается число n (\(1<=n<=100\)) – количество вершин графа. Затем задается матрица смежности - n строк по n чисел, каждое из которых равно 0 или 1.

Формат выходных данных
Выведите «YES», если граф содержит петли, и «NO» в противном случае.

Способы задания графа

✓ 1 371✗ 879300лёгкаяВойти и решать