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

Столовая#27231

Сегодня у студентов праздник! В одном из новых зданий университета решили открыть столовую. Для этих целей требуется выбрать одно из зданий, в котором и будет располагаться столовая. Чтобы студенты как можно меньше отвлекались от учёбы, было решено выбрать такое здание, чтобы максимальное расстояние от него до всех остальных зданий было как можно меньше.

Помогите найти такое здание!

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

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

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

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

Ввод	Вывод
3 2 1 2 1 2 3 2	2
3 1 1 2 10	1

Алгоритм Флойда кратчайшие пути

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

Два профессора#27230

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

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

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

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

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

Необходимо вывести одно число - искомое расстояние.

Ввод	Вывод
3 2 1 2 1 2 3 2	3
3 0	0

Алгоритм Флойда

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

Флойд: Начало №2#27228

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

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

В первой строке вводится единственное число N (1 <= N <= 100) – количество вершин графа. В следующих N строках по N чисел задается матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы – всегда нули.

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

Выведите N строк по N чисел – матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.

Ввод	Вывод
4 0 5 9 100 100 0 2 8 100 100 0 7 4 100 100 0	0 5 7 13 12 0 2 8 11 16 0 7 4 9 11 0

Алгоритм Флойда

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

Флойд №2#27227

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

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

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

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

Выведите искомое максимальное кратчайшее расстояние.

Ввод	Вывод
6 0 6 8 -1 -1 -1 5 0 5 -1 -1 -1 1 7 0 -1 -1 -1 -1 -1 -1 0 6 -1 -1 -1 -1 -1 0 3 -1 -1 -1 2 -1 0	9

Алгоритм Флойда кратчайшие пути

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

Флойд - существование#27226

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

Комментарий: Кратчайший путь может не существовать по двум причинам:

Нет ни одного пути
Есть пути сколь угодно маленького веса

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

В первой строке входного файла записано единственное число: N (1 <=N <=100) — количество вершин графа. В следующих N строках по N чисел — матрица смежности графа (j-е число в i-й строке соответствует весу ребра из вершины i в вершину j): число 0 обозначает отсутствие ребра, а любое другое число — наличие ребра соответствующего веса. Все числа по модулю не превышают 100.

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

Выведите N строк по N чисел. j-е число в i-й строке должно соответствовать кратчайшему пути из вершины i в вершину j. Число должно быть равно 0, если пути не существует, 1, если существует кратчайший путь, и 2, если пути существуют, но бывают пути сколь угодно маленького веса.

Примеры

№	Входные данные	Выходные данные
1	5 0 1 2 0 0 1 0 3 0 0 2 3 0 0 0 0 0 0 0 -1 0 0 0 -1 0	1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 2 2 0 0 0 2 2

Алгоритм Флойда

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

Bovine Genomics №3#27224

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

За большие деньги ФД выписал геномы своих коров. Каждый геном есть строка длины M, построенная из четырёх символов A, C, G, T. Когда он выписал их, у него получилась такая таблица (для N=3):

Позиция: 1 2 3 4 5 6 7 ... M

Пятнистая корова 1: A A T C C C A ... T

Пятнистая корова 2: G A T T G C A ... A

Пятнистая корова 3: G G T C G C A ... A

Без пятен корова 1: A C T C C C A ... G

Без пятен корова 2: A C T C G C A ... T

Без пятен корова 3: A C T T C C A ... T

Внимательно проанализировав эту таблицу, он предположил, что позиция 2 есть потенциальное место в геноме, которое отвечает за пятнистость. Потому что в этой позиции у коров без пятен находится один и тот же символ С, а у пятнистых коров находятся символы A или G. Причём G больше никогда не появлялось на позиции 2. Позиция 1 не может объяснять пятнистость, поскольку A в этой позиции есть и у пятнистых коров.

По заданным геномам коров ФД, посчитайте количество позиций, которые потенциально могли бы объяснять пятнистость.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N и M, оба - положительные целые числа не более 100. Каждая из следующих N строк содержит по M символов. Они описывают геномы пятнистых коров. Следующие N строк описывают геномы коров без пятен.

ФОРМАТ ВВОДА:

Вычислите количество позиций генома (целое число в интервале от 0…M), которые потенциально могут объяснять пятнистость. Такие позиции можно предсказывать по заданной информации.

Ввод	Вывод
3 8 AATCCCAT GATTGCAA GGTCGCAA ACTCCCAG ACTCGCAT ACTTCCAT	1

Двумерные массивы

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

Modern Art#27215

Picowso - новый гений!
Picowso рисует особым способом. Она начинает на пустом холсте размером N×N ячеек, представленном решёткой из N×N нолей, где ноль обозначает пустую ячейку холста. Затем она рисует N² прямоугольников на холсте каждым из N² цветов последовательно пронумерованных 1…N². Например, она может начать рисовать прямоугольник цветом 2 и получится такой холст:

2 2 2 0

0 0 0 0

Затем она может нарисовать прямоугольник цветом 7:

2 2 2 0

2 7 7 7

0 0 0 0

А затем она может нарисовать маленький прямоугольник цветом 3:

2 2 3 0

2 7 3 7

2 7 7 7

0 0 0 0

Каждый прямоугольник имеет стороны, параллельные сторонам холста, и прямоугольник может быть таким большим как весь холст или таким маленьким как одна ячейка. Каждый цвет из 1…N² используется ровно один раз, хотя более поздние цвета могут полностью перекрыть более ранние цвета.

По заданному финальному состоянию холста определите сколько из N² цветов могли быть первым, использованным при рисовании.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, размер холста (1≤N≤1000). Следующие N строк описывают финальную картину на холсте, каждая строка содержит N целых чисел в интервале 0…N². Гарантируется, что картина была нарисована способом описанным выше, рисованием прямоугольников различных цветов.

ФОРМАТ ВЫВОДА:

Выведите количество цветов, которые могли быть использованы первыми.

Ввод	Вывод
4 2 2 3 0 2 7 3 7 2 7 7 7 0 0 0 0	14

В этом примере цвет 2 мог быть использован первым. Цвет 3 был использован после цвета 7, а цвет 7 был использован после цвета 2. Поскольку мы не видим других цветов, мы делаем вывод, что они также могли быть использованы первыми (а потом перекрашены).

Префиксные суммы(минимумы, ...)

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

Самый короткий путь#27211

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

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

В первой строке задано число вершин N≤50. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от -1000000 до 1000000. Гарантируется, что на главной диагонали матрицы стоят нули.

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

Выведите одно число – искомый минимум. Если его не существует, выведите -1.
Примеры

№	Входные данные	Выходные данные
1	3 0 42 18468 6335 0 26501 19170 15725 0	42
2	3 0 -7 3 -2 0 10 2 215 0	-1

Алгоритм Флойда

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

Самый длинный путь#27210

Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Надо найти две вершины, кратчайший путь между которыми имеет наибольшую длину.

Формат входных данных

В первой строке задано число вершин N ≤50. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от от 0 до 1000000. Гарантируется, что на главной диагонали матрицы стоят нули.

Формат выходных данных

Выведите одно число – длину искомого пути.

Алгоритм Флойда

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

Флойд#27209

Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти длину кратчайшего пути из вершины s в вершину t.

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

В первой строке заданы три числа: число вершин в графе N ≤50, номера вершин s и t. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от 0 до 1000000, число -1 означает отсутствие соответствующего ребра. Гарантируется, что на главной диагонали матрицы стоят нули.

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

Выведите одно число – минимальную длину пути. Если пути не существует, выведите -1.

Ввод	Вывод
3 1 2 0 -1 3 7 0 1 2 215 0	218

Алгоритм Флойда

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

Дейкстра: кратчайший путь через наибольшее число узлов#27208

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

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

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

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

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

Ввод	Вывод
3 1 0 1 1 4 0 1 2 1 0	2 3 1

Алгоритм Дейкстры кратчайшие пути

—Войти и решать

ПТИЦЫ#27173

Всеволод Юрьевич устроился работать охранником на склад. Работа монотонная, и от скуки Всеволод Юрьевич считает ворон и других птиц, пролетающих мимо будки охраны. За годы работы он обнаружил следующую закономерность. Вороны летают поодиночке, начиная с 8:00 утра с периодичностью P1 минут, а после 8:00 вечера летать перестают. Утки пролетают стайками по N штук, начиная с 10:00 утра, с периодичностью P2 минут и перестают летать после 5:00 вечера. Голуби летают поодиночке с 7:00 утра до 8:00 вечера с периодичностью P3 минут. Три раза в день Всеволоду Юрьевичу приходится отвлечься от своего занятия ровно на полтора часа, чтобы принять на склад товар. Приемка начинается ровно в 11:00, 15:00 и 17:00. Сколько птиц (M) Всеволод Юрьевич насчитает за смену, если смена начинается в 6:00 утра и заканчивается в 6:00 утра на следующий день?

Во всех временных интервалах левый конец входит в него, а правый - нет. Например, одна из приемок начинается в 11:00 и Всеволод Юрьевич не считает птиц пролетающих в моменты с 11:00 до 12:29 включительно, а птиц, пролетающих в 12:30 - считает.

Формат входных данных
В строке указываются 4 целых положительных числа не превышающих 10000 каждое: P1, P2, N, P3, разделенные пробелом.
Формат выходных данных
В единственной строке указывается целое число M – количество птиц, которых Всеволод Юрьевич насчитает за смену при указанных условиях входа.

Ввод	Вывод
P1 P2 N P3	M
23 57 5 7	123

Разбор случаев

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

Площадь невырожденного треугольника#27172

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

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

язык программирования и его версию.

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

В первой строке задаётся N – количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа – координаты очередной точки.

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

Если искомый треугольник существует, программа должна напечатать одно число: максимальную возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «No solution».

Ввод	Вывод
3 6 6 -8 8 9 7	48

ЕГЭ - вычислительные задачи

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

Златопольский 12.5#27171

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

Формат выходных данных
Вывести на экран k-ю строку (считая, что нумерация элементов массива начинается с 1, т.е. для первой строки k=1).
Все элементы выводить в одну строку через 1 пробел между элементами

Двумерные массивы

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

Златопольский 12.3#27170

Формат входных данных
В первой строке вводятся через пробел количество строк N (1<=N<=20) и количество столбцов M (1<=M<=20) двумерного массива.
Далее идет N строк по M элементов в строке - элементы двумерного массива. Все элементы двумерного массива по модулю не превышают 50.
Далее, через пробел, идут два числа k и h (1<=k<=N, 1<=h<=M)

Формат выходных данных
Вывести на экран элемент, расположенный на позиции h в строке k (считая, что нумерация элементов массива начинается с 1, т.е. для левого верхнего элемента массива считается, что k=1 и h=1).

Двумерные массивы

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

Златопольский 12.2б#27169

Двумерные массивы

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

Златопольский 12.2а#27168

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

Формат выходных данных
Вывести на экран элемент, расположенный в правом нижнем углу.

Двумерные массивы

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

Златопольский 12.1б#27167

Двумерные массивы

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

Златопольский 12.1а#27166

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

Формат выходных данных
Вывести на экран элемент, расположенный в правом верхнем углу.

Двумерные массивы

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

Автобусы#27127

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

Марии Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).

Формат входных данных

Сначала вводится число N – общее число деревень (1 <= N <= 100), затем номера деревень d и v, за ними следует количество автобусных рейсов R (0 <= R <= 10000). Далее идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена – целые от 0 до 10000). Если в момент t пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с t.

Формат выходных данных

Выведите минимальное время, когда Мария Ивановна может оказаться в деревне v. Если она не сможет с помощью указанных автобусных рейсов добраться из d в v, выведите -1.

Алгоритм Дейкстры

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