Информатика

4 314 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
SNTP#32973
Для того чтобы компьютеры поддерживали актуальное время, они могут обращаться к серверам точного времени SNTP (Simple Network Time Protocol). К сожалению, компьютер не может просто получить время у сервера, потому что информация по сети передаётся не мгновенно: пока сообщение с текущим временем дойдёт до компьютера, оно потеряет свою актуальность. Протокол взаимодействия клиента (компьютера, запрашивающего точное время) и сервера (компьютера, выдающего точное время) выглядит следующим образом:
 
1) Клиент отправляет запрос на сервер и запоминает время отправления A (по клиентскому времени).
2) Сервер получает запрос в момент времени B (по точному серверному времени) и отправляет клиенту сообщение, содержащее время B.
3) Клиент получает ответ на свой запрос в момент времени C (по клиентскому времени) и запоминает его. Теперь клиент, из предположения, что сетевые задержки при передаче сообщений от клиента серверу и от сервера клиенту одинаковы, может определить и установить себе точное время, используя известные значения A, B, C.

Вам предстоит реализовать алгоритм, с точностью до секунды определяющий точное время для установки на клиенте по известным A, B и C. При необходимости округлите результат до целого числа секунд по правилам арифметики (в меньшую сторону, если дробная часть числа меньше ½, иначе в большую сторону). 

Возможно, что, пока клиент ожидал ответа, по клиентскому времени успели наступить новые сутки, однако известно, что между отправкой клиентом запроса и получением ответа от сервера прошло менее 24 часов. 

Программа получает на вход три временные метки A, B, C, по одной в каждой строке. Все временные метки представлены в формате «hh:mm:ss», где «hh» – это часы, «mm» – минуты, «ss» – секунды. Часы, минуты и секунды записываются ровно двумя цифрами каждое (возможно, с дополнительными нулями в начале числа). 
 
Программа должна вывести одну временную метку в формате, описанном во входных данных, – вычисленное точное время для установки на клиенте. В выводе не должно быть пробелов, пустых строк в начале вывода.
 
Ввод Вывод Примечание
15:01:00
18:09:45
15:01:40		 18:10:05 Клиент отправил запрос в 15:01:00 по своим часам, сервер получил запрос в 18:09:45 по своим часам. Клиент получил ответ в 15:01:40, в этот момент точное время будет 18:10:05.
Разбор случаев
✓ 81✗ 286800средняяВойти и решать
Космическое путешествие#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средняяВойти и решать
Ребра#31929
Есть n вершин неориентированного графа, в нем же нет ребер. В граф постепенно добавляются m ребер. 
После каждого добавления ребра требуется узнать количество компонент связности.
В графе могут быть петли и кратные ребра.

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

Ввод Вывод
3 2
1 2
2 3
 2
1
3 6
1 1
2 2
3 3
1 1
2 2
1 2
3
3
3
3
3
2

(с) Ибрахим Ахмад, 2018
Система непересекающихся множеств
✓ 9✗ 13800средняяВойти и решать
Сборка компьютера#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средняяВойти и решать
Яблоки#31883
У Даши есть n друзей, у каждого ai яблок. Все друзья образуют непересекающиеся компании. В любой момент времени две компании могут объединиться. Даша тщательно запомнила все действия друзей. Теперь ей интересно узнать, сколько яблок было в каждой новообразовавшейся компании. Изначально все друзья тусят отдельно, т.е. нет компании, где больше одного человека. У Даши нет яблок и она не принимает участия в объединениях.

Входные данные:
В первой строке - целые числа n и k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - количество друзей Даши и количество событий. Во второй строке n чисел - ai (0 <= ai <= 10^9) - количество яблок у i-того друга Даши. В следующих k строках по два числа u, v ( 1 <= u, v <= n). Событие (u, v) означает, что компания с u-тым другом Даши присоединилась к компании с v-тым другом. 

Выходные данные:
На каждый из k запросов выведите количество яблок в новой компании.

Ввод Вывод
3 2
1 2 3
1 2
1 3
3
6
2 1
999999999 0
1 2
 999999999

(с) Ибрахим Ахмад, 2018
Система непересекающихся множеств
✓ 15✗ 59800средняяВойти и решать
Покраска забора#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средняяВойти и решать
Троечные последовательности#31844
Вводится число N. Сгенерируйте в анти-лексикографическом порядке все последовательности длины N (1≤N≤9), состоящие из чисел 3, 4, 5, в которых количество троек не превосходит двух.
 
В "анти-лексикографическом" обозначает "в порядке, обратном к лексигографическому" (см. пример).
 
В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше.
В анти-лексикографическом, соответственно, наоборот. 
 

Примеры
№ Входные данные Выходные данные
1 3
5 5 5
5 5 4
5 5 3
5 4 5
5 4 4
5 4 3
5 3 5
5 3 4
5 3 3
4 5 5
4 5 4
4 5 3
4 4 5
4 4 4
4 4 3
4 3 5
4 3 4
4 3 3
3 5 5
3 5 4
3 5 3
3 4 5
3 4 4
3 4 3
3 3 5
3 3 4
 
Рекурсия
✓ 94✗ 205800средняяВойти и решать
Скобки-2#31804
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
 
Входные данные
В первой строке находится единственное число N. \(1 <= N <= 14\), N - чётное.
 
Выходные данные
Каждое выражение выводится в отдельной строке.
 

 

Примеры
№ Входные данные Выходные данные
1 2
()
[]
2 4
(())
[[]]
[()]
()[]
[]()
()()
([])
[][]
Рекурсия
✓ 96✗ 306800средняяВойти и решать
Расчет асимптотики - 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лёгкаяВойти и решать
Сумма кубов#31795
Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов натуральных чисел. Вася решил придумать аналогичное утверждение для кубов - он хочет узнать, сколько кубов достаточно для представления любого числа. Его первая рабочая гипотеза - восемь.

Выяснилось, что почти все числа, которые Вася смог придумать, представляются в виде суммы не более чем восьми кубов. Однако число 239, например, не допускает такого представления. Теперь Вася хочет найти какие-либо другие такие числа, а также, возможно, какую-либо закономерность в представлениях всех остальных чисел, чтобы выдвинуть гипотезу относительно вида всех чисел, которые не представляются в виде суммы восьми кубов.

Помогите Васе написать программу, которая проверяла бы, возможно ли представить данное натуральное число в виде суммы не более чем восьми кубов натуральных чисел, и если это возможно, то находила бы какое-либо такое представление.

Входные данные
Вводится натуральное число N <= 2*109.

Выходные данные
Требуется вывести не более восьми натуральных чисел, кубы которых в сумме дают N. Если искомого представления не существует, то в выходной файл необходимо вывести слово IMPOSSIBLE.
 
Примеры
№ Входные данные Выходные данные
1 239 IMPOSSIBLE
2 17  2 2 1
Рекурсия
✓ 8✗ 491 100средняяВойти и решать
Плацкартный вагон#31790
В плацкартном вагоне 54 места, пронумерованных числами от 1 до 54. Вагон разбит на 9 купе. Первые 36 мест расположены по левую сторону от прохода, места 1–4 находятся в первом купе, места 5–8 – во втором и т. д. В девятом купе находятся места с номерами 33– 36. По правую сторону от прохода находятся боковые места, их номера от 37 до 54, причём они нумеруются в противоположном направлении: места 37 и 38 находятся напротив девятого купе, а места 53 и 54 – напротив первого. Ниже приведена схема всех мест в вагоне.


Группа школьников едет на олимпиаду и будет всю дорогу крутить спиннеры. 
Поэтому им нужно купить места в нескольких подряд идущих купе вместе с прилегающими боковыми местами. Даны номера свободных мест в поезде. Определите, какое наибольшее число подряд идущих купе полностью свободны. 
 
Программа получает на вход число N – количество свободных мест в вагоне (0 ≤ N ≤ 54). Следующие N строк содержат номера свободных мест – различные числа от 1 до 54 в произвольном порядке, по одному числу в строке. 
Программа должна вывести одно целое число – максимальное число подряд идущих свободных купе (купе – 4 места слева от прохода и 2 боковых места) в этом вагоне.

Ввод Вывод Примечание
12
5
6
3
4
8
7
51
9
10
54
49
52		 1 Свободно одно купе с местами 5, 6, 7, 8, 51, 52.
1
1		 0
В вагоне только одно свободное место, поэтому
свободных купе нет совсем.

Алгоритмы обработкиреализация
✓ 53✗ 132800средняяВойти и решать
Робот#31782
Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.
 
В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из N операций.
 
Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.
 
Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.
 
Требуется написать программу, которая по заданному процессу сборки определит количество экономически целесообразных способов использования робота.
 
Входные данные
В первой строке записано число K > 0 - количество операций, которые можно записать в память робота.
Вторая строка состоит из N > K строчных латинских букв, обозначающих операции - процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой (N <= 200000).
 
Выходные данные
Выведите единственное целое число - количество экономически целесообразных способов использования робота.
 
Ввод Вывод
2
zabacabab
 5
2
abc		 0
"Два указателя"
✓ 54✗ 1331 000средняяВойти и решать
Поделиться
Класснуть