Алгоритмы

590 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Чет-нечет#33096
Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

Программа должна работать быстрее, чем за линейный поиск
 
Входные данные
Одно целое число N (1 <= N <= 109).
 
Выходные данные
Выведите одно целое число - N-й элемент последовательности.
 
Ввод Вывод
1 1
4 5
Бинарный поиск по ответу
✓ 25✗ 221 000средняяВойти и решать
Очень легкая задача - 2#33092
Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются M ксероксов, каждый из которых копирует лист за х секунд. (Разрешается использовать все ксероксы одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.

Программа должна работать быстрее, чем за линейный поиск


Формат входных данных
В первой строке записаны да натуральных числа N, M  разделенные пробелом (1 ≤ N, M ≤ 2•108), во второй строке записаны скорости всех ксероксов - x (1 ≤ x ≤ 10 )


Формат выходных данных
Выведите одно число – минимальное время в секундах, необходимое для получения N копий.
 
Ввод Вывод
8 3
2 3 7		 9
Бинарный поиск по ответу
✓ 25✗ 20800средняяВойти и решать
Домашнее задание#33080
Маленькому Арсению на кружке по системам счисления задали следующую задачу: перевести число X в системе счисления s1 в систему счисления s2. Недолго думая, он позвал на помощь своего лучшего друга Добрыню, который славился тем, что замечательно умел считать до 10 на пальцах. После нескольких бессонных ночей ребята общими усилиями справились с задачей.
 
Однако, на следующем занятии Арсению задали похожую задачу, где X, к сожалению, превышало 10. Тогда ребята решили обратиться в Летнюю Компьютерную Школу с просьбой написать универсальную программу, которая решает задачу для любых X, s1 и s2. Ваша цель – выполнить просьбу Арсения и Добрыни.
 
Входные данные
Во входных данных вашей программе дается 3 числа: исходное число X, основания систем счисления s1 и s2 (\(2  <=  s1,\ s2  <=  10\)). Число X в десятичной системе счисления не превышает \(2 \cdot 10^9\).
 
Выходные данные
В выходных данных должно находиться одно число, равное числу X в системе счисления s2, или -1, если входные данные некорректны.

 

 

Примеры
№ Входные данные Выходные данные
1 101 2 10 5
2 200 2 10 -1


 
Разные системы счисления
✓ 48✗ 146800средняяВойти и решать
Объединение прямоугольников#32983
На плоскости задано N прямоугольников с вершинами в точках с целыми координатами и сторонами, параллельными осям координат. Необходимо найти площадь их объединения.
 
Входные данные
В первой строке входного файла указано число N (0≤N≤1500). В следующих N строках заданы по 4 целых числа x1, y1, x2, y2 — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего (0≤x1≤x2≤109, 0≤y1≤y2≤109). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.
 
Выходные данные
В выходной файл выведите единственное число — ответ на задачу.
 
Ввод Вывод
3
1 1 3 5
5 2 7 4
2 4 6 7
 23
2
0 0 2 2
1 3 2 4
 5
Сканирующая прямая
✓ 12✗ 441 000средняяВойти и решать
Минимальное покрытие#32982
На прямой задано некоторое множество отрезков с целочисленными координатами концов \([L_i, R_i]\). Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок \([0, M]\), (M — натуральное число), содержащее наименьшее число отрезков.
 
Входные данные
В первой строке указана константа M (\(1<=M<=5000\)). В каждой последующей строке записана пара чисел Li и Ri (\(|L_i|,|R_i| < 50000\)), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.
 
Выходные данные
В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка \([0; M]\). Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка \([0; M]\) исходным множеством отрезков \([L_i, R_i]\) невозможно, то следует вывести единственную фразу “No solution”.

 

Примеры
№ Входные данные Выходные данные
1
1
-1 0
-5 -3
2 5
0 0
 No solution
2
1
-1 0
0 1
0 0
 1
0 1
Сканирующая прямая
✓ 43✗ 249900средняяВойти и решать
Распродажа#32981
В магазине проходит новогодняя распродажа – цены всех товаров снижены на 25 %. Оказалось, что первоначально все цены делились на 4, поэтому после снижения цен все цены также выражаются целым числом. Товаровед вечером перед распродажей снял ценники со всех товаров и напечатал для каждого товара ещё один ценник со сниженной ценой. Он оставил все ценники на столе, рассчитывая утром их развесить. Но, придя утром в магазин, он обнаружил, что уборщица смешала все ценники вместе, и теперь ему нужно отделить старые ценники от новых.
Помогите ему решить эту задачу. 
 

Входные данные
Первая строка входных данных содержит общее количество ценников N, 2 <= N <= 105, N – чётное число. Следующие N строк содержат целые положительные числа, не превосходящие 109, идущие в порядке неубывания по одному в строке – числа, записанные на всех ценниках (как старых, так и новых). Гарантируется, что входные данные корректны,то есть решение существует.

Выходные данные
Программа должна вывести N/2  целых чисел в порядке неубывания – стоимости товаров после понижения цен.

 
Примеры
№ Входные данные Выходные данные Примечание
1
6
30
40
42
45
56
60
30
42
45
До распродажи цены товаров были 40, 56, 60, после снижения цены
на эти товары стали равны 30, 42, 45.
"Два указателя"Словари
✓ 115✗ 595800средняяВойти и решать
Танец#32980
Для исполнения большого танца в круг выстроилось N танцоров (N чётное). Пронумеруем танцоров числами от 1 до N начиная от подиума по часовой стрелке. На каждом шаге танца танцоры разбиваются на пары (пару образуют два соседних по кругу танцора), и танцоры в паре меняются местам, причём на первом и всех последующих нечётных шагах танцор, стоящий в начале круга, образует пару с танцором, стоящим рядом с ним по часовой стрелке. Также пару образуют два танцора, следующие за ними по часовой стрелке, и т. д. На втором шаге и всех шагах с чётными номерами танцор, стоящий в начале
круга, образует пару с танцором, стоящим рядом с ним против часовой стрелки. Два танцора, следующие за ними против часовой стрелки, также образуют пару и т. д. 
 
На рисунке изображена начальная расстановка для N = 6 танцоров и два следующих шага танца. Расположение подиума отмечено точкой.
Определите, кто будет стоять рядом с танцором номер P через K шагов.

Программа получает на вход три целых числа N, P, K, записанные в отдельных строках. Первое число N – количество танцоров в кругу, N чётное. Второе число P – номер танцора, 1 ≤ P ≤ N. Третье число K – количество сделанных шагов после начала танца, 1 ≤ K. Максимальные значения для N и K <= 109. 
 
Программа должна вывести два целых числа в порядке возрастания – номера танцоров, которые будут стоять рядом с танцором номер P после K шагов танца.


 
Ввод Вывод Примечание
6
5
2		 2 4 Рисунок выше соответствует этому примеру.
Вывод формулыЗадачи на моделирование
✓ 54✗ 192900средняяВойти и решать
Счастливые билеты#32975
На автобусных билетах указываются их номера. Номера всех билетов всегда записываются при помощи одного и того же количества цифр, при этом число используемых цифр чётно. При необходимости числа дополняются ведущими нулями. К примеру, если для записи используют 4 цифры, то 514 будет записано как 0514. Билеты отпечатаны на лентах, билеты на каждой ленте нумеруются подряд числами от 00...01 до 99...99.
Счастливым считается тот билет, у которого сумма цифр первой половины равна сумме цифр второй половины, например, билеты 1001 и 123051 счастливые, а 7778 и 39 – нет. Сегодня Дима зашел в автобус, и кондуктор выдал ему билет с номером N. Поскольку Диме ехать достаточно долго, а заняться чем-нибудь надо, он стал думать, какой номер будет иметь следующий счастливый билет, выданный из той же ленты, что и Димин билет. Если в текущей ленте не осталось счастливых билетов, Диму интересует номер минимального счастливого билета из новой ленты.

В первой и единственной строке входного файла содержится номер Диминого билета N, записанный с ведущими нулями. Количество цифр в записи числа N не превосходит 100 000 и чётно.

Программа должа вывести номер следующего счастливого билета из текущей ленты в таком же формате. Если такого билета не существует, надо вывести номер минимального счастливого билета из новой ленты. В выводе не должно быть пробелов, пустых строк в начале вывода.
 
Ввод Вывод Примечание
0514 0523 Диме был выдан счастливый билет (сумма цифр обеих половин равна 5), но Диму не интересует номер его билета, его интересует номер следующего счастливого билета.


 
 
Жадный алгоритм
✓ 17✗ 2631 100средняяВойти и решать
Космическое путешествие#32966
В MMORPG "Космические торговцы online" скорость перемещения игрока между звёздами ограничена одним парсеком в секунду. С такой скоростью можно быстро добраться до ближайших звёзд, но на путешествие с одного края галактики до другого может потребоваться несколько часов. Для ускорения таких долгих путешествий создатели игры сделали несколько "кротовых нор" — туннелей, соединяющих две точки в пространстве, которые позволяют мгновенно перемещаться между этими точками туда и обратно.

Напишите программу, которая вычисляет минимальное время путешествия, используя информацию о "кротовых норах".

В первой строке ввода содержится целое число N (1 ≤ N ≤ 100). Далее следует строка, содержащая 6 целых чисел — координаты начальной (xs,ys,zs) и конечной (xt,yt,zt) точки путешествия. Далее следует N строк, содержащих 6 целых чисел — координаты концов "кротовых нор". Все координаты измеряются в парсеках и находятся в диапазоне от 0 до 10000, и нет точек с совпадающими координатами.

Вывести минимальное время путешествия в секундах с точностью не менее 10−6.
Примеры
№ Входные данные Выходные данные
1
1
0 0 0 100 100 0
1 1 1 50 100 10
 52.722246
Алгоритм Флойда
✓ 82✗ 193900средняяВойти и решать
Следующее число#32965
Дано натуральное число N. Необходимо определить следующее за ним число, в двоичном разложении которого столько же единиц, сколько в двоичном разложении числа N.
 
Входные данные
Входные данные содержит одно натуральное число N (\(N <= 2^{30}\)).
 
Выходные данные
Выведите ответ на задачу.
 

 

Примеры
№ Входные данные Выходные данные
1 1 2
2 2 4
3 3 5
Двоичная система счисления
✓ 108✗ 1 012800средняяВойти и решать
Степень числа#32949
Для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A.
 
Входные данные 
На вход подается единственное число A (\(1 <= A <= 10^9\)).
 
Выходные данные
Необходимо вывести единственное число N.
 
Примеры
№ Входные данные Выходные данные
1 8 4
2 13 13
Простые числа и разложение на множители
✓ 139✗ 1 086800средняяВойти и решать
Дорогие дороги#31930
Президент Берляндии обратился к вам за помощью! В его стране есть n городов. Между некоторыми парами городов есть двусторонние дороги. Совсем скоро откроется туристический сезон, но дороги Берляндии совсем не готовы к такому испытанию.
Президент хочет отремонтировать некоторое множество дорог так, чтобы суммарная стоимость ремонта была минимальной и из любого города Берляндии можно было бы добраться до любого другого, пользуясь только отремонтированными дорогами.
Найти множество дорог, которые нужно отремонтировать, вам поможет ваш друг. Вам только требуется подсчитать минимальную стоимость ремонта.
Гарантируется, что всегда найдется необходимое множество дорог.

Входные данные:
В первой строке задано два целых числа - n и m (2 <= n <= 300000, n - 1  <= m <= 300000).
В следующих m строках содержатся три числа - u, v и w (1 <= u, v <= n, 0 <= w <= 109) - дорога между городами u и v, стоимость ремонта которой w.

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

(с) Ибрахим Ахмад, 2018

Минимальный каркас
✓ 7✗ 9900средняяВойти и решать
Сборка компьютера#31928
Для сборки компьютера необходимо T компонентов различного типа (видеокарта, жесткий диск, монитор и т.д.). В магазине продаются N компонентов. Каждый компонент относится к определенному типу и имеет некоторую стоимость и рейтинг по обзорам в журналах.
Напишите программу, определяющую из каких компонентов нужно собрать компьютер, чтобы его стоимость не превышала B, в составе были по одному компоненту каждого типа, а суммарный рейтинг использованных компонентов был максимальным.

Первая строка ввода содержит одно целое число – количество типов компонентов T (1 ≤ T ≤ 5). Вторая строка ввода содержит одно целое число – количество компонентов в магазине N (1 ≤ N ≤ 1000). Далее следует N строк, содержащих по три целых числа, разделенных пробелами – стоимость i-го компонента Ci (1 ≤ Ci ≤ 3000), его рейтинг Ri (1 ≤ Ri ≤ 3000) и его тип ti (1 ≤ ti ≤ T). Далее следует строка, содержащая одно целое число – бюджет на покупку компьютера B (1 ≤ B ≤ 3000).

Вывести в первой строке одно целое число – максимальный суммарный рейтинг использованных компонент. Во второй строке вывести T целых чисел – i-е число означает номер компонента типа i, выбранного для сборки. Если существует несколько вариантов с максимальным суммарным рейтингом, то из них вывести вариант с минимальной стоимостью, а среди таких вариантов можно вывести любой. Если не существует варианта сборки компьютера в рамках указанного бюджета, то вывести в первой строке одно число –1

Ввод Вывод
2
5
10 6 1
5 7 1
6 10 2
1 5 1
11 11 2
16
 18
2 5

Динамическое программирование
✓ 9✗ 711 100средняяВойти и решать
Подпоследовательность#31927
Напишите программу, которая в некоторой последовательности целых чисел находит подпоследовательность наименьшей длины, сумма элементов в которой является числом, оканчивающимся на 6 или более нулей (делится без остатка на 1000000).
Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Вторая строка ввода содержит N целых чисел в диапазоне от 1 до 109, разделенных пробелами.
Вывести два целых числа – количество элементов в подпоследовательности и номер её первого элемента. Если существует несколько вариантов такой подпоследовательности с наименьшей длиной, выведите подпоследовательность с наименьшим номером первого элемента. Если такой подпоследовательности не существует – выведите одно число –1.

Ввод Вывод
6
1 2 701000 299000 1000 999000
 2 3
3
1 2 3		 -1

Остатки
✓ 10✗ 671 000средняяВойти и решать
RSA. Зашифровать числовое сообщение#31919
Даный два простых числа p и q. Надо зашифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится натуральное число, которое надо зашифровать, не превышающее 109.

Ввод Вывод
3 7
123456789		 1 11 12 16 17 6 7 8 18

Быстрое возведение в степеньМЦКО-10. RSA
✓ 8✗ 25900средняяВойти и решать
Покраска забора#31880
Однажды, в наказание за шалости и обман, тетя Полли заставила Тома красить забор длиной L ярдов. Все вы прекрасно помните, что Том продавал (за различные ништячки) свою работу другим мальчишкам, которые хотели побелить забор.
К тому моменту, когда у Тома закончилась известка, забор успели покрасить N мальчишек. И так как за мальчишками Том не особо следил, то каждый красил ту часть забора, которая ему больше нравилась. 
Каждый i-й мальчишка начинал красить забор с вертикальной дощечки с координатой Lefti и красил до дощечки с координатой Righti (длину дощечки считать равной 1). 
Определите длину забора, которую необходимо будет докрасить Тому самостоятельно. 

 
Входные данные
В первой строке находится число L - длина забора тети Полли. Во второй строке находится число N, в следующих N строках - пары Lefti и Righti. Все числа - целые
Ограничения:
\(0 <= L <= 2 \cdot 10^9\);
 \(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\).

Выходные данные
Вывести одно число - длину забора, которую необходимо докрасить Тому.
 
 
Примеры
№ Входные данные Выходные данные
1
20
1
10 20
 10
2 10
1
10 10		 10
3 100
2
10 30
20 40		 70
Быстрая сортировка
✓ 223✗ 1 124900средняяВойти и решать
Расчет асимптотики - 8#31796
Для приведенного ниже кода, найдите асимптотику: 
#include <bits/stdc++.h>
using namespace std;

vector < vector<int> > g;
vector <int> color;

void dfs(int v, int p)
{
	color[v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (to == p)
			continue;
		if (color[to] == 1)
		{
			cout << "YES";
			exit(0);
		}
		if (color[to] == 0)
			dfs(to, v);
	}
	color[v] = 2;
}

int main()
{
	int n, m, a, b;
	cin >> n >> m;

	g.resize(n);
	color.resize(n);

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs(0, -1);
	cout << "NO";
	return 0;
}
 
1) O(n)            2) O(m)          3) O(n + m)      4) O(nm)
Обход в глубину
800лёгкаяВойти и решать
Монетки#31794
В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы  сначала поступает число N (1 <= N <= 109), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 109).

Выходные данные
Сначала выведите K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
 
Ввод Вывод
100 6
11 20 30 40 11 99		 3
40 30 30
Рекурсивный переборРекурсия
✓ 19✗ 721 000средняяВойти и решать
Кинотеатр#31791
В первом ряду кинотеатра N + 2 мест, крайние места заняты персоналом кинотеатра, но N мест посередине свободно. K школьников входят в зрительный зал по очереди, и, конечно же, каждый школьник достаёт спиннер и начинает его крутить до начала сеанса.  Поэтому каждый школьник выбирает себе место как можно дальше от уже занятых мест. А именно, школьник находит самый большой свободный участок в ряду (любой, если таких несколько) и садится  посередине него. Если число свободных мест на этом участке было нечётно, то школьник садится точно посередине участка, тогда слева и справа от него остаётся поровну свободных мест. Если же это число чётно, то школьник выбирает одно из  двух свободных мест посередине, тогда с одной стороны от школьника будет на одно свободное место больше, чем с другой стороны.

По данным числам N и K определите, сколько мест осталось свободными с двух сторон от школьника, который занял место последним (K-м по счёту). 
 
Программа получает на вход два целых числа N и K, 1 ≤ K ≤ N ≤ 1018, и должна вывести два целых числа в порядке неубывания – количество свободных мест с двух сторон от школьника, который последним занял место в ряду.

 
Ввод Вывод Примечание
10
1		 4
5
В зале 10 свободных мест, первый школьник сел посередине, с одной стороны от него 4 места, с другой стороны – 5.
 
10
2		 2
2
Второй вошедший в зал школьник садится посередине группы из 5 свободных мест, с каждой стороны от него остаётся по 2 свободных места.
10
3		 1
2
После того, как два школьника сели на места, в зале остались группы свободных мест из 4, 2, 2 мест. Третий школьник садится посередине группы из 4 мест, поэтому с одной стороны от него 1 место, с другой стороны – 2 места.

Вывод формулыЗадачи на моделирование
✓ 36✗ 196900средняяВойти и решать
Заполнение конем#31784
Дана шахматная доска nхn. Пусть конь стоит на клетке (1,1). Необходимо найти такую последовательность ходов коня, при которой он побывает на каждой клетке доски ровно по одному разу.
 
Входные данные
На вход программе подается натуральное число n (n ≤ 8).
 
Выходные данные
Если обход невозможен, то выведите в выходной файл 0, если возможен, то 1, а на следующих строчках выведите матрицу nn, иллюстрирующую порядок обхода. Выравнивать числа по столбцам не обязательно.
 
Примечание. Скорость работы рекурсивной программы в этой задаче существенно зависит от порядка, в каком будут рассматриваться варианты хода коня из очередной клетки. Одним из удачных порядков является размещение всех восьми вариантов хода "по кругу".
 
Ввод Вывод
3 0
5
1
1 20 17 12 3 
16 11 2 7 18 
21 24 19 4 13 
10 15 6 23 8 
25 22 9 14 5 
Обход в глубинуРекурсия
✓ 26✗ 1141 000средняяВойти и решать
Поделиться
Класснуть