Алгоритмы

606 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Дейкстра: Расстояние до всех вершин#21776
Дан неориентированный взвешенный граф, необходимо найти расстояние от вершины 1 до всех остальных, используя алгоритм Дейкстры.
 
Входные данные:
В 1 строке даны 2 целых числа n и m (n>=1, m >= 0), число вершин и ребер в графе соответсвенно. В следующих m строках дается по 3 числа a и b - вершины которые соединяет ребро и c - вес этого ребра .
 
Выходные данные:
Необходимо вывести n-1 число через пробел - расстояния от вершины 1 до всех остальных, если нет возможного пути из 1 в i вершину, то необходимо вывести Impossible.
 
Ввод Вывод
5 5
1 2 3
2 3 1
3 4 3
1 4 1
4 2 1
 2 3 1 Impossible
 
P.S. Внимательно проверяйте ограничения
Алгоритм Дейкстры
✓ 18✗ 42700средняяВойти и решать
Беллман#21775
Дан ориентированный взвешенный граф с отрицательными ребрами (без отрицательных циклов).
Дана стартовая и конечная вершина, определить минимальное расстояние между ними.
 
Входные данные:
Дано 4 числа n, m, s, f - количество вершин, количество ребер, стартовая и конечная вершина(начиная с 1) соответственно.
В следующих m строках содержится по 3 числа - вершина 1, вершина 2 и цена перехода между вершинами.
 
Выходные данные:
Требуется вывести одно число - ответ на поставленную задачу. Если ответа нет - следует вывести Inf.
 
Примеры
№ Входные данные Выходные данные
1
4 2 1 4    
1 2 100500
2 3 100500
 Inf 
Алгоритм Форда-Беллмана
✓ 89✗ 137400лёгкаяВойти и решать
Ленивый Вася и релиз Half-Life 3#21773
Свершилось чудо! Наконец-то вышел долгожданный Half-Life 3, о котором мечтали миллионы людей по всему миру! Вася тоже с нетерпением ждал продолжения легендарной серии, и даже не ел в школьной столовой целый месяц, чтобы ему хватило на покупку этого шедевра! Единственная проблема, которая стоит у него на пути - огромное домашнее задание по алгебре. В классе он прошёл новую тему - прямые, и теперь ему нужно сделать аж N задач на построение прямой через 2 точки. Но ведь так хочется поиграть, а на следующий день рассказывать друзьям, какой же там классный графон... Поэтому он попросил Вас, своего друга, помочь ему.
 
Входные данные
В первой строке вводятся координаты первой точки (X1, Y1), (\(-50 <= X_1, Y_1 <= 50\)).
Во второй строке вводятся координаты второй точки (X2, Y2), (\(-50 <= X_2, Y_2 <= 50\)).
 
Выходные данные
В единственной строке выведите подряд 3 целых числа: коэффициенты a, b, c уравнения прямой.
 
Примечание: если у вас не заходит задача, но вы уверены, что всё правильно - попробуйте умножить все коэффициенты на -1. Задача предполагает, что вы использовали формулы, взятые с лекции/теории.

 

Примеры
№ Входные данные Выходные данные
1
-1 -1
1 1
 -2 2 0
Вычислительная геометрия
✓ 71✗ 65600лёгкаяВойти и решать
Перевод часов#21772
В плоской стране наступила очередная зима, и нужно срочно переводиться на зимнее время! Проблема в том, что стрелка городских часов (единственная, кстати), находящихся в начале координат, очень-очень тяжёлая, и поэтому рабочие хотят узнать, в какую сторону крутить стрелку будет быстрее. Чтобы упростить вам задачу, они уже посчитали, куда указывает стрелка и куда она должна указывать. Помогите им!
 
Входные данные
В первой строке задаётся точка, куда указывает стрелка. Она задаётся координатами X1 и Y1 (\(-10 <= X_1, Y_1 <= 10\)).
Во второй строке задаётся точка, куда должна указывать стрелка. Она задаётся координатами X2 и Y2 (\(-10 <= X2, Y2 <= 10\)).
Координаты задаются вещественным типом.
 
Выходные данные
В единственной строке выведите "Clockwise", если стрелку нужно крутить по часовой стрелке, "Counter-clockwise", если её нужно крутить против часовой стрелки, и "Doesn't matter", если это займёт одинаковое время, в какую сторону её бы не крутили. Выводить фразы следует без кавычек.

 

Примеры
№ Входные данные Выходные данные
1
1 0
-1 1
 Counter-clockwise
Вычислительная геометрия
✓ 233✗ 652700средняяВойти и решать
Простые числа - 1#21768
Найти количество всех четырехзначных простых чисел, оканчивающиеся на цифру k.

Входные данные 
Число k.

Выходные данные 
Вывести число - количество простых чисел, удовлетворяющих условию задачи. Если таких чисел нет то вывести слово Absent.

Примеры
№ Входные данные Выходные данные
1 1 266
2 0 Absent
Простые числа и разложение на множители
✓ 794✗ 1 382400лёгкаяВойти и решать
Постулат Бертрана#21767

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

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

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

Входные данные
Целое число n (\(2 <= n <= 50000\)).

Выходные данные 
Выведите одно число – ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 3000 353
Простые числа и разложение на множители
✓ 630✗ 1 075500лёгкаяВойти и решать
Максимальная цифра в восьмеричной СС#21763
Дано натуральное число N . Необходимо найти максимальную цифру данного числа при его записи в восьмеричной системе счисления.

Входные данные
На вход подается натуральное число N (\(N<=255\)).

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

 

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

 

Разные системы счисления
✓ 507✗ 350300лёгкаяВойти и решать
Количество единиц в двоичной СС#21762
Дано натуральное десятичное число N. Найдите количество единиц в двоичной записи данного числа. Ответ вывести в десятичной системе счисления.

Входные данные
На вход подается одно натуральное число N (\(N<=255\)).

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

 

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

 

Двоичная система счисления
✓ 589✗ 460300лёгкаяВойти и решать
Алгоритм Евклида#21722
Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: НОД(a,b)=НОД(a % b,b). Реализуйте рекурсивный алгоритм Евклида в виде функции gcd(a, b).

Ввод
12 16
Вывод
4
НОД и алгоритм ЕвклидаРекурсия
✓ 71✗ 36500лёгкаяВойти и решать
Перекрестные ребра#21710
Дан связный ориентированный невзвешенный граф. Требуется вывести номера вершин из которых исходят все его перекрестные ребра (нумерация с 1).
 
Входные данные:
Целое число n и m - число вершин и ребер в графе.
Следующие m строк содержат 2 числа a и b, показывающие, что из вершины a есть ребро в вершину b.
 
Выходные данные:
В первой строке должно находиться число n - количество перекрестных ребер, в следующей строке должны быть перечисленны вершины в порядке возрастания без повторений. Если таковых нет, тогда следует вывести -1.
Обход в глубинупоиск в глубину и подобное
✓ 17✗ 8500лёгкаяВойти и решать
Громозеки комфортное число#20379

Громозека любит печеньки, на которых записаны числа. Громозека будет есть печеньку, если на ней написано комфортное для него число. Громозека считает число комфортным, если оно является точной степенью двойки.  В руках у Громозеки сейчас печенька, на которой написано число N. Выведите слово YES, если Громозека съест эту печеньку и слово NO в противном случае.

Операцией возведения в степень пользоваться нельзя!
 

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

Вводится натуральное число N (N < 109).
 

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

Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 1 YES
2 4 YES
3 5 NO
 
Двоичная система счисленияЦикл for
✓ 314✗ 618400лёгкаяВойти и решать
Длина пути#19885
В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.
 
Формат входных данных
В первой строке входных данных записано число N - количество вершин в графе (1 <= N <= 100). Далее с новой строки записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.
 
Формат выходных данных 
Выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.
Обход в ширинуОчередь
✓ 1 225✗ 3 024500лёгкаяВойти и решать
Треугольник Паскаля#18786
Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая 
содержит на одно число больше, чем предыдущая. Первое и последнее из этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него.
 
Входные данные
Вводится одно целое число N (\(0<=N<=30\)).
 
Выходные данные 
Выведите N строк треугольника Паскаля. Разделяйте числа в строке одним пробелом.
 

Примечание
Все числа в треугольнике Паскаля при указанных ограничениях входят в Longint.
 
 
Примеры
№ Входные данные Выходные данные
1 
8
 
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
 
Динамическое программирование: два параметра
✓ 611✗ 653400лёгкаяВойти и решать
Поделиться
Класснуть