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

Дан ориентированный взвешенный граф с отрицательными ребрами (без отрицательных циклов).

Дана стартовая и конечная вершина, определить минимальное расстояние между ними.

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

Дано 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лёгкаяВойти и решать

N0SC0P3 360#21774

Джон aka xXx_1337_7R1k$#073R_xXx учится великому искусству стрельбы без прицеливания. Он уже освоил несколько простых выстрелов, и сейчас он учится одному из самых основных - так называемому noscope 360. Это достаточно трудно, но у него наконец-то начало получаться, и теперь он хочет узнать, поразил ли он цель своим выстрелом (который мы представим в виде луча).

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

В первой строке вводятся 2 числа X₀ и Y₀ - координаты точки, в которой стоит Джон (-10 <= X0, Y0 <= 10).

Во второй строке вводятся 2 числа vX и vY - координаты вектора, по которому направлен луч (-10 <= vX, vY <= 10).

В третьей строке вводятся 2 числа X и Y - координаты цели (-50 <= X, Y <= 50).

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

Выведите слово "Yes", если Джону удалось попасть, и "No" в противном случае.

Примеры

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

Элементарная геометрия

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

Ленивый Вася и релиз Half-Life 3#21773

Свершилось чудо! Наконец-то вышел долгожданный Half-Life 3, о котором мечтали миллионы людей по всему миру! Вася тоже с нетерпением ждал продолжения легендарной серии, и даже не ел в школьной столовой целый месяц, чтобы ему хватило на покупку этого шедевра! Единственная проблема, которая стоит у него на пути - огромное домашнее задание по алгебре. В классе он прошёл новую тему - прямые, и теперь ему нужно сделать аж N задач на построение прямой через 2 точки. Но ведь так хочется поиграть, а на следующий день рассказывать друзьям, какой же там классный графон... Поэтому он попросил Вас, своего друга, помочь ему.

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

В первой строке вводятся координаты первой точки (X₁, Y₁), ($-50 <= X_1, Y_1 <= 50$).

Во второй строке вводятся координаты второй точки (X₂, Y₂), ($-50 <= X_2, Y_2 <= 50$).

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

В единственной строке выведите подряд 3 целых числа: коэффициенты a, b, c уравнения прямой.

Примечание: если у вас не заходит задача, но вы уверены, что всё правильно - попробуйте умножить все коэффициенты на -1. Задача предполагает, что вы использовали формулы, взятые с лекции/теории.

Примеры

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

Вычислительная геометрия

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

Перевод часов#21772

В плоской стране наступила очередная зима, и нужно срочно переводиться на зимнее время! Проблема в том, что стрелка городских часов (единственная, кстати), находящихся в начале координат, очень-очень тяжёлая, и поэтому рабочие хотят узнать, в какую сторону крутить стрелку будет быстрее. Чтобы упростить вам задачу, они уже посчитали, куда указывает стрелка и куда она должна указывать. Помогите им!

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

В первой строке задаётся точка, куда указывает стрелка. Она задаётся координатами X₁ и Y₁ ($-10 <= X_1, Y_1 <= 10$).

Во второй строке задаётся точка, куда должна указывать стрелка. Она задаётся координатами X₂ и Y₂ ($-10 <= X2, Y2 <= 10$).
Координаты задаются вещественным типом.

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

В единственной строке выведите "Clockwise", если стрелку нужно крутить по часовой стрелке, "Counter-clockwise", если её нужно крутить против часовой стрелки, и "Doesn't matter", если это займёт одинаковое время, в какую сторону её бы не крутили. Выводить фразы следует без кавычек.

Примеры

№	Входные данные	Выходные данные
1	1 0 -1 1	Counter-clockwise

Вычислительная геометрия

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

Пикап-мастер#21771

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

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

В первой строке вводятся координаты концов тропинки (X₁, Y₁) и (X₂, Y₂), по которой гуляет Венцеслав ($-20 <= X1, Y1, X2, Y2 <= 20$).

Во второй строке вводится целое число N - количество тропинок, по которым гуляют девушки ($0 <= N <= 5$).

В последующих N строках вводятся координаты концов тропинок, по которым гуляют девушки (X_i1, Y_i1) и (X_i2, Y_i2), по i-ой тропинке гуляет i-ая девушка ($-20 <= X_{i1}, Y_{i1}, X_{i2}, Y_{i2} <= 20$)
Координаты концов тропинок - вещественные числа.

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

В первой строке выведите число M - количество девушек, пути которых пересекутся с путём Венцеслава (касание путей считается пересечением).

Во второй строке выведите M чисел - номера девушек, с которыми встретится наш герой. Девушки нумеруются с единицы!

Примеры

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

Вычислительная геометрия

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

1 - k BFS#21770

Дан ориентированный взвешенный граф. Необходимо найти расстояние от вершины 1 до всех остальных, используя алгоритм 1 - k BFS.

Входные данные
В первой строке даны 2 целых числа n и m, число вершин и ребер в графе соответственно. В следующих m строках дается по 3 числа a и b - вершины которые соединяет ребро и c - вес этого ребра (a, b, c >= 0).

Выходные данные
Необходимо вывести n-1 число через пробел - расстояния от вершины 1 до всех остальных, если нет возможного пути из 1 в i вершину, то необходимо вывести Impossible.

Примеры

№	Входные данные	Выходные данные
1	9 9 1 2 1 2 4 2 4 6 1 4 3 1 3 5 2 5 6 1 8 9 100 9 7 100 7 8 100	1 4 3 6 4 Impossible Impossible Impossible

0-1 BFS

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

Простые числа - 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лёгкаяВойти и решать

21766#21766

Дано натуральное десятичное число N (N<=255). Найдите местоположение младшего единичного бита. Выведите номер бита в десятичной системе счисления

Битовые операции Двоичная система счисления

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

21765#21765

Дано натуральное число N (N<=255). Найти сумму цифр данного числа в двоичной системе счисления. Ответ вывести в десятичной системе.

Двоичная система счисления Целые числа

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

21764#21764

Дано натуральное число N (N<=255). Найти сумма цифр данного числа в восьмеричной системе счисления.

Разные системы счисления

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

Максимальная цифра в восьмеричной СС#21763

Дано натуральное число N . Необходимо найти максимальную цифру данного числа при его записи в восьмеричной системе счисления.

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

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

Примеры

№	Входные данные	Выходные данные
1	255	7

Разные системы счисления

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

Количество единиц в двоичной СС#21762

Дано натуральное десятичное число N. Найдите количество единиц в двоичной записи данного числа. Ответ вывести в десятичной системе счисления.

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

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

Пример

№	Входные данные	Выходные данные
1	100	3

Двоичная система счисления

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

21753#21753

Как задать отрезок на плоскости?

1. координатами отрезка
2. координатами и длиной отрезка
3. координатами конца и начала
4. длиной отрезка

Элементарная геометрия

1 100труднаяВойти и решать

21752#21752

Как задается положение окружности на плоскости

1. координатами радиуса
2. координатами центра и длиной радиуса
3. длиной радиуса и его координатами
4. координатами диаметра и его длиной

Элементарная геометрия

1 000средняяВойти и решать

21745#21745

Редактирование документа является процессом

1. сбора информации
2. обработки информации
3. хранения информации
4. передачи информации

Задачи на моделирование

800лёгкаяВойти и решать

21739#21739

В каком из вариантов ответов верно соблюден порядок осуществления информационных процессов?

1. сбор, передача, обработка, хранение
2. сбор, хранение, передача, обработка
3. сбор, обработка, хранение, передача
4. сбор, хранение, передача, обработка

Задачи на моделирование

800лёгкаяВойти и решать

21726#21726

Каким образом можно задать поиск точно по фразе?

1. с помощью логического ИЛИ
2. заключить фразу в кавычки
3. с помощью логического И
4. нет правильного ответа

Обработка текста

800лёгкаяВойти и решать

Уменьшение длинного на 1#21725

В строке записано натуральное число, не превышающее 10¹⁰⁰.
Нужно вывести результат уменьшения этого числа на 1.

"Длинная" арифметика

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

Увеличение длинного на 2#21724

В строке записано натуральное число, не превышающая 10¹⁰⁰
Нужно вывести результат умножения этого числа на 2.

"Длинная" арифметика

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