Решения задач с «ACMP - Школа программиста»






На нашем сайте представлены решения задач по программированию с сайта acmp.ru на языке C++, по таким темам как:

  • Условные операторы и операторы цикла
  • Строковые типы данных, строки
  • Одномерные и двумерные массивы
  • Функции
  • Сортировки
  • Рекурсия
  • Целочисленная арифметика, длинная арифметика
  • Теория графов
  • Структуры данных


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

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

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

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – длину искомого пути.
1368Флойд вместо ДейкстрыДан ориентированный взвешенный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти длину кратчайшего пути из вершины S в вершину T.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – минимальную длину пути. Если пути не существует, выведите -1.
136Алгоритм Флойда - 2Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.

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

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

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

Входные данные
В первой строке входного файла INPUT.TXT находятся два целых числа N и M – количество зданий и количество дорог, соединяющих здания (1 ≤ N ≤ 100, 0 ≤ M ≤ N∙(N−1)/2). Далее в M строках расположены описания дорог: 3 целых числа si, ei, li – здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1 ≤ si, ei ≤ N, 0 ≤ li ≤ 100, дороги двунаправленные).

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

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

Входные данные
В первой строке входного файла INPUT.TXT находятся два целых числа N и M – количество зданий и количество дорог, соединяющих здания (1 ≤ N ≤ 100, 0 ≤ M ≤ N∙(N−1)/2). Далее в M строках расположены описания дорог: 3 целых числа si, ei, li – здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1 ≤ si, ei ≤ N, 0 ≤ li ≤ 100, дороги двунаправленные).

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – номер искомого здания. Если есть несколько зданий удовлетворяющих поставленным критериям, выберите среди них здание с наименьшим номером.
138Алгоритм Форда-БеллманаДан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

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

Входные данные
В первой строке входного файла INPUT.TXT записаны целые числа N и M - количество вершин и количество ребер графа (1 ≤ N ≤ 100, 0 ≤ M ≤ 10000). В каждой из последующих M строк записана тройка чисел, описывающих ребра: начало ребра, конец ребра и вес (вес - целое число от -100 до 100).

Выходные данные
В выходной файл OUTPUT.TXT выведите N чисел - расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.
1377Алгоритм Форда-Беллмана - 2В ориентированном взвешенном графе вершины пронумерованы числами от 1 до N. Если i < j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле:

w(i,j) = (179∙i+719∙j) mod 1000 – 500

Определите вес кратчайшего пути, ведущего из вершины 1 в вершину N.

Входные данные
Входной файл INPUT.TXT содержит целое число N (2 ≤ N ≤ 104).

Выходные данные
В выходной файл OUTPUT.TXT выведите единственное целое число – вес кратчайшего пути из вершины 1 в вершину N в описанном графе.
132Алгоритм ДейкстрыДан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от вершины S до вершины F.

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

Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести искомое расстояние или -1, если пути между указанными вершинами не существует.
1381Алгоритм Дейкстры - 2 Дан ориентированный взвешенный граф. Найдите кратчайший путь от одной заданной вершины до другой.

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

Выходные данные
В выходной файл OUTPUT.TXT выведите последовательно все вершины одного (любого) из кратчайших путей, или одно число -1, если пути между указанными вершинами не существует.
142Минимальный каркасОт вас требуется определить вес минимального остовного дерева для неориентированного взвешенного связного графа.

Входные данные
В первой строке входного файла INPUT.TXT находятся числа N и M (1 ≤ N ≤ 100; 1 ≤ M ≤ 6000), где N - количество вершин в графе, а M - количество рёбер. В каждой из последующих M строк записано по тройке чисел A, B, C, где A и B - номера вершин, соединённых ребром, а C - вес ребра (натуральное число, не превышающее 30000).

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число - искомый вес.
1387Остовное деревоТребуется найти в связном неориентированном графе остовное дерево минимального веса.

Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество вершин и ребер графа соответственно (1 ≤ N ≤ 20 000, 0 ≤ M ≤ 100 000). Следующие M строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами Bi, Ei и Wi – номера концов ребра и его вес соответственно (1 ≤ Bi, Ei ≤ N, 0 ≤ Wi ≤ 100 000).

Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – вес минимального остовного дерева.
1088Шахматные фигурыПо заданным координатам двух клеток шахматной доски необходимо определить список шахматных фигур, которые могут перемещаться при игре за «белых» по правилам шахмат из первой координаты во вторую без взятия фигуры соперника.

Напомним, что для игры в шахматы используется доска размером 8х8. При этом горизонтальная координата нумеруется английскими буквами от «A» до «H», а вертикальная – цифрами от 1 до 8 снизу вверх. Таким образом, координата клетки состоит из буквы и цифры. Например, «H1» и «A8» – правый нижний и левый верхний углы соответственно.

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

король ходит на расстояние 1 по вертикали, горизонтали или диагонали;
ферзь ходит на любое расстояние по вертикали, горизонтали или диагонали;
ладья ходит на любое расстояние по вертикали или горизонтали;
слон ходит на любое расстояние по диагонали;
конь ходит буквой «Г», т.е. на поле, находящееся на расстоянии 2 по вертикали и 1 по горизонтали или 1 по вертикали и 2 по горизонтали;
пешка ходит на 1 поле вперед по вертикали, начиная свое движение со второй линии, при первом ходе пешка может перемещаться на 2 поля вперед по вертикали.
Следующие рисунки отражают возможные перемещения шахматных фигур (в скобках указаны англоязычные названия фигур):


Шахматная доска Ладья (Rook) Слон (Bishop)

Конь (Knight) Ферзь (Queen) Король (King) Пешка (Pawn)
Входные данные
В первой строке входного файла INPUT.TXT через пробел записаны начальная и конечная координаты шахматной доски. Каждая координата состоит из заглавной английской буквы от «A» до «H» и цифры от 1 до 8. Гарантируется, что начальная и конечная координаты не совпадают.

Выходные данные
В выходной файл OUTPUT.TXT выведите по-английски названия шахматных фигур, которые могут совершить свободный ход из первой координаты во вторую по правилам шахмат. Если ни одна из фигур не может выполнить такой ход, то следует вывести «Nobody». Фигуры следует выводить без повторов в произвольном порядке.
66КлавиатураДля данной буквы английского алфавита нужно вывести справа стоящую букву на стандартной клавиатуре. При этом клавиатура замкнута, т.е. справа от буквы «p» стоит буква «a», от буквы «l» стоит буква «z», а от буквы «m» — буква «q».

Входные данные
Входной файл INPUT.TXT содержит один символ — маленькую букву английского алфавита.

Выходные данные
В выходной файл OUTPUT.TXT следует вывести букву стоящую справа от заданной буквы, с учетом замкнутости клавиатуры.
46Число EВыведите в выходной файл округленное до n знаков после десятичной точки число E. В данной задаче будем считать, что число Е в точности равно 2.7182818284590452353602875.

Входные данные
Входной файл INPUT.TXT содержит целое число n (0 ≤ n ≤ 25).

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
283Рунные словаРуны — это древние магические знаки, которые наши предки использовали как буквы. Говорят, что рунные знаки обладают магическими свойствами, а при сложении рун в слова их магическая сила многократно возрастает. Если кузнец изготовит доспехи и начертит там определенные руны в определенном порядке, то доспехи будут наделены необычайными магическими силами.

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

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

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

Выходные данные
В выходной файл OUTPUT.TXT выведите «Yes», если слово является рунным и «No» в противном случае.
493Морской бой - 2«Морской бой» - игра для двух участников, в которой игроки по очереди называют координаты на неизвестной им карте соперника. Если у соперника по этим координатам имеется корабль, то корабль или его часть «топится», а попавший получает право сделать еще один ход. Цель игрока - первым поразить все корабли противника.

«Морской бой» очень популярен среди учеников одной физико-математической школы. Ребята очень любят в него играть на переменах. Вот и сейчас ученики Иннокентий и Емельян начали новую партию.

Правила, по которым ребята расставляют корабли перед началом партии, несколько отличаются от классических. Во-первых, игра происходит на поле размером N×M, а не 10×10. Во-вторых, число кораблей, их размер и форма выбираются ребятами перед партией - так играть намного интереснее.

Емельян уже расставил все свои корабли, кроме одного однопалубного. Такой корабль занимает ровно одну клетку.

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

Входные данные
Первая строка входного файла INPUT.TXT содержит два числа: N и M (1 ≤ N, M ≤ 100). Последующие N строк описывают игровое поле - каждая из них содержит M символов. Символом «.» (точка) обозначена свободная клетка, символом «*» (звездочка) - занятая кораблем.

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
371Дружественные числаДва различных натуральных числа называются дружественными, если первое из них равно сумме делителей второго числа, за исключением самого второго числа, а второе равно сумме делителей первого числа, за исключением самого первого числа. Требуется найти все пары дружественных чисел, оба из которых принадлежат промежутку от M до N.

Входные данные
Входной файл INPUT.TXT в первой строке содержит натуральные числа M и N, разделенные пробелом, не превышающие 106.

Выходные данные
В выходной файл OUTPUT.TXT выведите в каждой строке по паре чисел через пробел. Первое число пары должно быть меньше второго. Строки должны быть отсортированы в порядке возрастания первого числа пары. Если пар дружественных чисел в промежутке нет, то следует вывести "Absent".
36Постулат БертранаПостулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого n > 1 найдется простое число p в интервале n < p < 2n. Такая гипотеза была выдвинута в 1845 году французским математиком Джозефем Бертраном (проверившим ее до n=3000000) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.

Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала n < p < 2n.

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

Входные данные
Входной файл INPUT.TXT содержит целое число n (2 ≤ n ≤ 50000).

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – ответ на задачу.
363Длинное произведениеДаны целые неотрицательные числа M и N. Требуется найти произведение этих чисел.

Входные данные
Входной файл INPUT.TXT содержит в первой строке число M, а во второй строке – число N. (0 ≤ M, N ≤ 102500)

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

Входные данные
Во входном файле INPUT.TXT записано натуральное число N (1 ≤ N ≤ 100) – количество кубиков в лесенке.

Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести число лесенок, которые можно построить из N кубиков.