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

Нестандартное заполнение - 1. Диагонали#27235

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

Формат входных данных
Во входной строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M (1 <= N, M <= 100).

Формат выходных данных
Программа должна вывести полученную матрицу по строкам.

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

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

Простая задача#27234

Дан двумерный массив N*M (0 < N, M <= 20).
Значения элементов массива вводятся с клавиатуры
Вывести в первой строке все угловые элементы массива, начиная с левого верхнего угла и далее, двигаясь по часовой стрелке.

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

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

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

✓ 3 347✗ 4 538200лёгкаяВойти и решать

Pink Floyd#27233

Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.

Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным. Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.

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

Первая строка входного файла содержит три натуральных числа n, m и k - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (n≤100, m≤10⁴, 2≤k≤10⁴). Города пронумерованы числами от 1 до n. Следующие m строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами b_i, e_i и w_i - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1≤b_i,e_i≤n, −10⁵≤w_i≤10⁵). Последняя строка содержит числа a1, a2, ..., ak - номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1.Гарантируется, что группа может дать все концерты.

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

Первая строка выходного файла должна содержать число s - количество рейсов, которые должна сделать группа. Вторая строка должна содержать s чисел - номера используемых рейсов. Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку “infinitely kind”.

Ввод	Вывод
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 -10 1 3 1 2 4	6 5 6 5 7 2 3
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 10 1 3 1 2 4	infinitely kind

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

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

Опасный маршрут#27232

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

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

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

В первой строке находятся два числа N и M - количество зданий и количество улиц, соединяющих здания (1<=N<=100, 1<=M<= (N*(N−1))/2. В следующей строке находятся числа S и E -- номер дома, в котором живёт профессор и номер дома, в котором находится университет соответственно. Далее в M строках расположены описания дорог: 3 целых числа sieipi - здания, в которых начинается и заканчивается дорога и вероятность в процентах быть ограбленным, пройдя по дороге соответственно (1<=s_i, e_i<=N, 0<=p_i<=100 , дороги двунаправленные). Гарантируется, что существует хотя бы один путь от дома профессора до университета.

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

Необходимо вывести одно число - минимальную возможную вероятность быть ограбленным. Выведите ответ с максимально возможной точностью.

Ввод	Вывод
3 3 1 3 1 2 20 1 3 50 2 3 20	0.36

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

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

Столовая#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 пробел между элементами

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

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

Златопольский 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).

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

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

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

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

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