Информатика

2 621 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Номер максимального и минимального числа#28327
Дано число N и N различных целых чисел. Необходимо вывести позицию минимального и максимального чисел среди всех N чисел.

Входные данные
В первой строке вводится число N - количество чисел  (\(N<=100\)). Далее идут N чисел, по одному в строке  (все числа целые, не превышающие по модулю 10 000).

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

 

Примеры
№ Входные данные Выходные данные
1 5
-2
1
2
3
0		 1 4

При сложностях:
Теоретическая карточка содержит подсказку.
Цикл for
✓ 4 958✗ 11 775400лёгкаяВойти и решать
Минимальное не из всех#28326
Дано число N и последовательность из N чисел. Необходимо вывести минимальное четное число среди заданных N чисел.

Входные данные
В первой строке вводится число N - количество чисел  (\(N<=100\)). Далее идут N чисел по одному в строке (все числа целые, не превышающие по модулю 10 000). Среди N чисел имеется хотя бы одно четное число.

Выходные данные
Вывести на экран минимальное четное число среди всех N чисел.

 

Примеры
№ Входные данные Выходные данные
1 5
-2
1
2
3
0		 -2
Цикл for
✓ 5 807✗ 16 050300лёгкаяВойти и решать
Максимальное число в последовательности#28325
Вводится число N и затем N чисел по одному в строке. Необходимо вывести максимальное число среди всех вводимых чисел.

Входные данные
В первой строке вводится число N - количество чисел  (\(N<=100\)). Далее по одному в строке идут N чисел (все числа целые, не превышающие по модулю 10 000).

Выходные данные
Вывести на экран максимальное число из всех N чисел.

 
Примеры
№ Входные данные Выходные данные
1 5
0
1
2
3
4		 4
Цикл for
✓ 6 606✗ 16 207300лёгкаяВойти и решать
Ближайшее число#28311
Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.
 
Формат входных данных
В первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке содержатся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000). В третьей строке вводится одно целое число x, не превосходящее по модулю 1000.
 
Формат выходных данных
Вывести значение элемента массива, ближайшее к x. Если таких чисел несколько, выведите любое из них.
 
Бинарный поиск
✓ 1 514✗ 4 921400лёгкаяВойти и решать
Шахматная доска#27315
Требуется найти число способов расставить на шахматной доске NxN K ладей так, чтобы они не били друг друга. Все ладьи считаются одинаковыми.
 
Входные данные
Во входном файле записаны натуральные числа N и K (\(1 <= N, K <= 8\)).
 
Выходные данные
В выходной файл выведите одно целое число - ответ задачи.
 

 

Примеры
№ Входные данные Выходные данные
1 8 8 40320
Сочетания
✓ 80✗ 206700средняяВойти и решать
Разность#27314
Вывести разность между количеством двоичных деревьев с N листьями и количеством разбиений N-угольника на треугольники.
 
Входные данные
На вход подаётся одно число - N (\(1 <= N <= 10\))
 
Выходные данные
Выведите одно число - искомую разность
 

 

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

 

Комбинаторные структуры
✓ 71✗ 40500лёгкаяВойти и решать
Количество чисел Каталана#27313
Вывести N-ное число Каталана

Входные данные
Первая строка входных данных содержит одно число N (\(1 <= N <= 20\)).
 
Выходные данные
Выведите одно число - N-ное число Каталана
 

 

Примеры
№ Входные данные Выходные данные
1 1 1
Комбинаторные структуры
✓ 73✗ 182700средняяВойти и решать
Деление пополам#27290
Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a.
 
Для решения используйте метод деления отрезка пополам.
 
 
Входные данные
Число a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после запятой. Число n – натуральное, не превосходящее 10. Каждое число вводится в отдельной строке.
 
Выходные данные
Программа должна вывести единственное число: ответ на задачу с точностью не менее 6 знаков после запятой.
 

Примеры
№ Входные данные Выходные данные
1 
2
2
 
1.41421356237
Бинарный поиск значения функции
✓ 376✗ 1 482500лёгкаяВойти и решать
Отрицательный цикл#27277
Дан ориентированный граф. Определить, есть ли в нем цикл отрицательного веса.

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

Примеры
№ Входные данные Выходные данные
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
 YES
Алгоритм Флойда
✓ 211✗ 398500лёгкаяВойти и решать
Количество релаксаций#27274
Дан взвешенный ориентированный граф. Необходимо найти минимальное количество фаз с релаксациями в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1. 

Входные данные
Программа получает на вход одно число количество вершин n (2 ≤ n ≤ 100) и количество ребер m (2 ≤m ≤ 10 000). В следующих m строках вводятся три числа: a, b и c, где a и b – начало ребра и его конец, а c – вес ребра (1 ≤ a, b ≤ n, 1 ≤ c ≤ 10 000).

Выходные данные
Программа должна вывести единственное целое число - минимальное количество релаксаций в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1. 

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


(с) Шалдин В., 2017г.

Алгоритм Форда-Беллмана
✓ 28✗ 35500лёгкаяВойти и решать
Домой на электричках#27273
Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут).
 
Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.
 
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома.
 
Формат входных данных
Во входных данных записаны сначала числа N (2 ≤ N ≤ 100) и E (2 ≤ E ≤ N). Затем записано число M (0 ≤ M ≤ 100), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki (2 ≤ K ≤ N) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.
 
Формат выходных данных
Выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.
 
Алгоритм Дейкстры
✓ 167✗ 174700средняяВойти и решать
Форд-Беллман - 2#27271
В ориентированном взвешенном графе вершины пронумерованы числами от 1 до n. Если i<j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле \(wt(i,j)=(179i+719j)\ mod \ 1000 - 500\). Определите вес кратчайшего пути, ведущего из вершины 1 в вершину n.
 
Входные данные:
Программа получает на вход одно число n (2≤n≤13000).
 
Выходные данные:
Программа должна вывести единственное целое число - вес кратчайшего пути из вершины 1 в вершину n в описанном  графе.

Примеры
№ Входные данные Выходные данные
1 2 117
2 3 -164
Алгоритм Форда-Беллмана
✓ 42✗ 271700средняяВойти и решать
Форд-Беллман: Начало (C++)#27268
Дополните программу, чтобы она верно решала следующую задачу.

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.
Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.
 
Входные данные
Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).
 
Выходные данные
Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.
 
Примеры
№ Входные данные Выходные данные
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000 
Алгоритм Форда-Беллмана
✓ 81✗ 184500лёгкаяВойти и решать
Форд-Беллман#27267
Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.
 
Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.
 
Входные данные
Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).
 
Выходные данные
Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

Примеры
№ Входные данные Выходные данные
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000 
Алгоритм Форда-Беллмана
✓ 129✗ 84300лёгкаяВойти и решать
Строка с минимальной суммой#27238

Напишите программу, которая находит в матрице строку с минимальной суммой.
 

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

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

Двумерные массивы
✓ 2 454✗ 2 549300лёгкаяВойти и решать
Магический квадрат?#27237

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

Формат входных данных
В первой строке вводится размер матрицы N (0 < N <= 100) . В следующих N строках вводятся строки матрицы, по N значений в каждой, разделённые пробелами.
 

Формат выходных данных
Программа должна вывести слово 'YES', если матрица является магическим квадратом, и слово 'NO', если не является.

Двумерные массивы
✓ 1 714✗ 1 843500лёгкаяВойти и решать
Нестандартное заполнение - 2. Змейка#27236

Напишите программу, которая заполняет матрицу из N строк и M столбцов натуральными числами змейкой, как показано в примере.
 

Формат входных данных
Входная строка содержит числа N и M, разделённые пробелом (5 <= N, M <= 20).
 

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

Двумерные массивы
✓ 1 683✗ 1 041400лёгкаяВойти и решать
Нестандартное заполнение - 1. Диагонали#27235

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

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

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

Двумерные массивы
✓ 1 792✗ 1 017400лёгкаяВойти и решать
Поделиться
Класснуть