Алгоритмы

2 310 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
ABCD-код#21810
Вася часто ходит в гости к Пете. Для того, чтобы попасть к Пете во двор, надо ввести код,
состоящий из четырех цифр. Обычно друзья ходили вместе, но в этот раз Вася пришел один, а
Петя ждет его у себя.
Вася не помнит код, но у него есть несколько вариантов. Кроме того, Васе почему-то запомнился
факт, что квадрат числа, составленного из первых двух цифр кода, в сумме с квадратом числа,
состоящего из последних двух цифр кода, имеет при делении на семь остаток один. То есть, если код
представляет собой «ABCD», где «A», «B», «C», «D» — некоторые цифры, тогда AB2+CD2 имеет
остаток 1 при делении на 7. Например, код 2843, является одним из возможных кодов, поскольку
282 + 432 = 2633 = 376 · 7 + 1, а 8243 — нет, поскольку 822 + 432 = 8573 = 1224 · 7 + 5.
У Васи есть несколько вариантов того, каким может быть код. Помогите ему определить, какие
из вариантов могут быть кодом от входа в Петин двор.

Формат входных данных
В первой строке  находится число t (1 ≤ t ≤ 10 000) — число вариантов кода,
которые помнит Вася. В следующих t строках содержится по четыре цифры — варианты кода.
Формат выходных данных
В ответе выведите t строк. В i-й строке выведите «YES», если i-й код может быть кодом
для входа в Петин двор, иначе выведите «NO».
Вычисление по заданной формулеОстатки
✓ 151✗ 148500лёгкаяВойти и решать
21804#21804
Если мы хотим сделать два одинаковых слова, то необходимо использовать операцию:

1. вырезать
2. копировать
3. размножить
4. удалить
Конечные автоматы
1 100труднаяВойти и решать
21803#21803
Работая с готовым текстом, мы не можем

1. изменить его начертание
2. изменить его цвет
3. изменить его язык
4. изменить его размер
Обработка текста
1 000средняяВойти и решать
21802#21802
Преобразование, изменяющее структуру текста называется

1. редактированием
2. форматированием
3. стилизацией
4. структуризацией
Конечные автоматы
1 300труднаяВойти и решать
21801#21801
Преобразование, изменяющее содержание текста называется

1. редактированием
2. форматированием
3. стилизацией
4. структуризацией
Обработка текста
1 000средняяВойти и решать
21800#21800
Представление текста в виде списка называется

1. проверкой правописания
2. форматированием
3. редактированием
4. стилизацией
Обработка текста
1 300труднаяВойти и решать
Dank numbers#21778
Число является dank number, если все его цифры идут в неубывающем порядке. Чтобы получить dank kush, Bonkisilver должен назвать все n-значные dank numbers. Вас не просят узнать все такие числа, Вам лишь нужно вывести их количество.

 
Входные данные
На вход подается число n (0 <= n <= 50).
 
Выходные данные
Выведите одно число - количество n-значных dank number. 
 
 
Примеры
№ Входные данные Выходные данные
1 9 24310
 
Динамическое программирование
✓ 105✗ 164700средняяВойти и решать
Запросы по Флойду#21777
Дан неориентированный взвешенный граф с отрицательными весами, необходимо выдавать информацию о кратчайшем пути между 2 вершинами.

Входные данные
В первой строчке дано целое число n - количество вершин в графе. Дальше на вход подается матрица смежности, в которой -1 означает отсутствие ребра между вершинами. После матрицы идет число k - количество запросов, в следующих k строках содержится по 2 числа, a и b - вершины в запросе.

Выходные данные
Выведите k чисел - расстояние между парой чисел из запроса в порядке их ввода, если нельзя добраться из вершины a в вершину b, следует вывести Imp. Каждое число выводится в отдельной строке.
 
Примеры
№ Входные данные Выходные данные
1
3
0 3 -1
3 0 4
-1 4 0
3
1 3
3 2
1 2
 7
4
3
Алгоритм Флойда
✓ 277✗ 465500лёгкаяВойти и решать
Дейкстра: Расстояние до всех вершин#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лёгкаяВойти и решать
N0SC0P3 360#21774
Джон aka xXx_1337_7R1k$#073R_xXx учится великому искусству стрельбы без прицеливания. Он уже освоил несколько простых выстрелов, и сейчас он учится одному из самых основных - так называемому noscope 360. Это достаточно трудно, но у него наконец-то начало получаться, и теперь он хочет узнать, поразил ли он цель своим выстрелом (который мы представим в виде луча).
 
Входные данные
В первой строке вводятся 2 числа X0 и Y0 - координаты точки, в которой стоит Джон (-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 точки. Но ведь так хочется поиграть, а на следующий день рассказывать друзьям, какой же там классный графон... Поэтому он попросил Вас, своего друга, помочь ему.
 
Входные данные
В первой строке вводятся координаты первой точки (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
Вычислительная геометрия
✓ 240✗ 666700средняяВойти и решать
Пикап-мастер#21771
Недавно Венцеслав прочитал новую книгу по пикапу, и теперь он хочет опробовать свои знания в парке. Для простоты представим парк в виде набора тропинок, которые являются отрезками на плоскости. Венцеслав уже гулял в этом парке, и знает, какая девушка по какой тропинке гуляет. Проблема в том, что Венцеслав очень ленивый, и гуляет только по одной тропинке. А ещё ему лень узнать, каких девушек он может встретить по пути, и поэтому он попросил Вас, своего лучшего друга, помочь ему в этом непростом деле.
 
Входные данные
В первой строке вводятся координаты концов тропинки (X1, Y1) и (X2, Y2), по которой гуляет Венцеслав (\(-20 <= X1, Y1, X2, Y2 <= 20\)).
Во второй строке вводится целое число N - количество тропинок, по которым гуляют девушки (\(0  <= N <= 5\)).
В последующих N строках вводятся координаты концов тропинок, по которым гуляют девушки (Xi1, Yi1) и (Xi2, Yi2), по 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
Простые числа и разложение на множители
✓ 816✗ 1 405400лёгкаяВойти и решать
Постулат Бертрана#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
Простые числа и разложение на множители
✓ 639✗ 1 084500лёгкаяВойти и решать
Поделиться
Класснуть