Информатика

15 724 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Расчет асимптотики - 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средняяВойти и решать
Функция - 2*#31793
Описана рекурсивная функции с тремя параметрами F(a, b, c):
 
F(a, b, c) = 1, если a ≤ 0 или b ≤ 0 или c ≤ 0;
F(a, b, c) = F(20, 20, 20), если a > 20 или b > 20 или c > 20;
F(a, b, c) = F(a, b, c-1) + F(a, b-1, c-1) - F(a, b-1, c), если a < b и b < c;
F(a, b, c) = F(a-1, b, c) + F(a-1, b-1, c) + F(a-1, b, c-1) - F(a-1, b-1, c-1), во всех остальных случаях.

 
Входные данные
Входные данные содержат три целых числа a, b, c - параметры функции F (-104 ≤ a,b,c ≤ 104).
 
Выходные данные
В ответе выведите значение функции F(a, b, c).

 
Примеры
№ Входные данные Выходные данные
1 1 1 1 2
2 2 2 2 4
3 10 4 6 523
4 50 50 50 1048576

 
Рекурсия
✓ 179✗ 540700средняяВойти и решать
Как поделить картошку#31792
Вася и Петя пошли копать картошку. В конце дня они накопали N мешков с картошкой весом W1, W2, ... WN. Как им поделить мешки с картошкой между собой, чтобы разница масс была минимальной.
Входные данные
В первой строке  записано число N – количество мешков (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы мешков W1, W2 , … WN (1 ≤ Wi ≤ 105).
 
Выходные данные
В единственную строку нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух куч с мешками.
 
Ввод Вывод
5
5 3 5 7 8		 2
Рекурсия
✓ 97✗ 191700средняяВойти и решать
Плацкартный вагон#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средняяВойти и решать
Не про спиннеры#31789
Саша совсем не любит спиннеры, поэтому он рисует в тетрадке. Он взял тетрадный лист из N × M клеточек и пронумеровал все клетки различными числами. Теперь ему стало интересно, сколько различных прямоугольников он может вырезать из этого листа бумаги по границам клеточек.
 
Программа получает на вход два числа N и M – размеры исходного листа. Все числа – целые положительные, не превосходящие 75000.

Программа должна вывести одно число – количество прямоугольников, которые можно вырезать из данного листа бумаги (весь лист целиком также считается одним из возможных прямоугольников).
 
Ввод Вывод Примечание
2
2		 9
3
1		 6


 
Вывод формулы
✓ 152✗ 342600лёгкаяВойти и решать
Снова спинеры#31788
Денис тоже решил заняться производством и продажей спиннеров, но он считает, что у спиннера может быть только три или четыре лопасти. У него есть ровно M лопастей, которые он может прикреплять к основаниям, и неограниченный запас оснований. Он хочет изготовить несколько трёхлопастных и несколько четырёхлопастных спиннеров так, чтобы использовать все M лопастей. Определите, сколько спиннеров каждого вида он должен произвести. 

Программа получает на вход одно целое положительное число M, не превосходящее 2×109
, – количество лопастей, которое есть у Дениса.
 
Программа должна вывести два целых числа – количество спиннеров с 3 лопастями и количество спиннеров с 4 лопастями, которые должен произвести Денис. Если у задачи есть
несколько решений, нужно вывести любое из них. Если Денис не может использовать ровно M лопастей для производства спиннеров, программа должна вывести два числа 0.

Ввод Вывод Примечание
10 2
1		 10 = 3 × 2 + 4 × 1
1 0
0
Невозможно произвести спиннеры так, чтобы
суммарное число лопастей было равно 1.
 

Вывод формулы
✓ 168✗ 393500лёгкаяВойти и решать
Робот#31782
Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.
 
В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из N операций.
 
Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.
 
Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.
 
Требуется написать программу, которая по заданному процессу сборки определит количество экономически целесообразных способов использования робота.
 
Входные данные
В первой строке записано число K > 0 - количество операций, которые можно записать в память робота.
Вторая строка состоит из N > K строчных латинских букв, обозначающих операции - процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой (N <= 200000).
 
Выходные данные
Выведите единственное целое число - количество экономически целесообразных способов использования робота.
 
Ввод Вывод
2
zabacabab
 5
2
abc		 0
"Два указателя"
✓ 54✗ 1331 000средняяВойти и решать
Садовник-художник#30783
Садовник посадил N деревьев в один ряд. После посадки деревьев садовнику нужно их покрасить. В его распоряжении есть краска трех цветов: белая, синяя и оранжевая. Сколько способов покраски деревьев есть у него, если никакие два соседних дерева нельзя красить в одинаковый цвет?
 
Входные данные
В единственной строке записано одно натуральное число - количество деревьев N (1 ≤ N ≤ 50).
 
Выходные данные
В единственную строку нужно вывести одно число - количество способов покраски.
 
Ввод Вывод
3 12
Динамическое программирование
✓ 91✗ 233500лёгкаяВойти и решать
Городской парад#30782

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

Напишите программу, определяющую, сможет ли Виггам обеспечить правильный порядок движения платформ на параде.
 

Входные данные
Первая строка ввода содержит одно целое число N (\(1 <= N <= 100\)) – количество платформ.
Вторая строка содержит N различных целых чисел от 1 до N – номера платформ в порядке прибытия.

Выходные данные
Вывести сообщение "YES", если можно обеспечить правильный порядок платформ, или сообщение "NO", если нельзя.
 

Примеры
№ Входные данные Выходные данные
1
4
1 3 4 2
 YES
2
4
4 3 2 1
 NO
3 4
2 1 3 4		 YES

 
Очередь
✓ 365✗ 883700средняяВойти и решать
Морской бой - 3#30781
Всем известна увлекательная игра «Морской бой». Сейчас играть в Морской бой можно не только с соседом по парте, но и с компьютером. Игра c компьютером ведется на прямоугольном поле произвольных размеров N×M, где N - количество строк, M - количество столбцов. Приближается чемпионат мира по Морскому бою. Планируется вести его трансляцию в режиме реального времени: демонстрировать карту с кораблями и выводить статистику: количество целых, подбитых и уничтоженных кораблей, находящихся на поле. Требуется написать программу для подсчета статистики.
 
Корабль на поле — это связанная фигура, стоящая из одной или нескольких рядом расположенных клеток, имеющих общую сторону. Корабли могут быть абсолютно любых форм и размеров!
 
Входные данные
Первая строка содержит два целых числа N и M (\(1<= N,M <= 10^3\)), разделённых пробелами. Это размеры игрового поля. Далее идут N строк по M символов - описание игрового поля. Английская буква 'X' обозначает подбитую клетку корабля, 'S' - не подбитую клетку корабля, '-' – свободное водное пространство.
 
Выходные данные
В ответе выведите через пробел три числа:
- количество целых кораблей;
- количество подбитых кораблей;
- количество уничтоженных кораблей.
 
Примеры
№ Входные данные Выходные данные
1 
3 8
---SSS--
XX--S-X-
X-S---S-

2 1 1
Очередь
✓ 269✗ 352800средняяВойти и решать
Несложная сортировка#30779
Пусть x – целое положительное число, а k – натуральное число от 1 до 10. Пусть s(x, k) равно сумме цифр числа x, представленного в системе счисления по основанию k.
 
Задано n чисел a1, a2, ..., an. Необходимо вычислить последовательность bi по формуле \(b_i = s(a_i, k_1) \cdot s(a_i, k_2)\). После этого отсортировать последовательность bi по неубыванию.
 
Входные данные
Первая строка содержит три целых числа: n, k1, k2 (\(1 <= n <= 1000\), \(2 <= k_1, k_2 <= 10\)). Вторая строка содержит n целых чисел: ai (\(1 <= a_i <= 10^9\)).
 
Выходные данные
В ответе выведите n чисел – bi в требуемом порядке.
 

 

Примеры
№ Входные данные Выходные данные
1
9 10 10
1 2 3 4 5 6 7 9 8
 1 4 9 16 25 36 49 64 81
2
10 2 2
1 2 4 8 16 32 64 128 256 512
 1 1 1 1 1 1 1 1 1 1
Разные системы счисления
✓ 140✗ 94600лёгкаяВойти и решать
Апельсины#30777
Катя решила пригласить к себе в гости n друзей. Так как ее друзья очень любят фрукты, то в качестве угощения для них она купила m одинаковых апельсинов. Она хочет разрезать каждый апельсин на одинаковое число равных долек так, чтобы их можно было распределить между гостями (сама Катя апельсины есть не будет), и всем досталось одинаковое количество долек.

Напишите программу, которая вычисляет минимальное количество долек, на которое необходимо разрезать каждый апельсин, чтобы были выполнены указанные выше условия.
 
Входные данные 
Входная строка содержит два положительных целых числа n и m (\(1 <= n, m <= 10^9\)).

Выходные данные 
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 2 5 2
2 2 4 1
НОД и алгоритм Евклида
✓ 778✗ 1 703500лёгкаяВойти и решать
Упрощение номеров#30776
Как, вы не можете запомнить 6 или 7-значный номер телефона, появившийся на секунду на экране телевизора?! С помощью специальной методики, описываемой далее, Вы превратитесь в ходячий телефонный справочник!
 
Очевидно, что число 402 запомнить легче, чем число 110010010, а число 337377 запомнить легче, чем число 957472. Значит, нужно чтобы запоминаемое число, с одной стороны, содержало как можно меньше цифр, а с другой стороны, желательно, чтобы в числе было как можно больше повторяющихся цифр. В качестве критерия сложности запоминания примем сумму количества цифр в числе и количества различных цифр в числе. Запоминаемое число можно записать в другой системе счисления, возможно, тогда его окажется легче запомнить. Например, число 65535 в шестнадцатеричной системе исчисления выглядит как FFFF.
Напишите программу подбора основания системы счисления для минимизации критерия сложности. Основание системы счисления нужно выбирать в диапазоне от 2 до 36, тогда для представления числа можно использовать цифры 0-9 и английские буквы A-Z.
 
Входные данные
Первая строка содержит в первой строке целое число n (\(1 <= n <= 100\)). Далее следует n строк, каждая строка содержит целое число от 1 до 999999999.
 
Выходные данные
Ответ должен содержать n строк. Для каждого из n заданных чисел строка содержит: основание системы счисления (от 2 до 36), минимизирующее критерий сложности запоминания, и число в выбранной системе исчисления, разделенные одним пробелом. Если несколько оснований дают одинаковое значение критерия, то выбрать наименьшее среди них.
 

 

Пример
№ Входные данные Выходные данные
1
2
2
65535
3 2
16 FFFF
Разные системы счисления
✓ 38✗ 73900средняяВойти и решать
Несложное вычисление#30775
Задано натуральное число n. Необходимо перевести его в k-ичную систему счисления и найти разность между произведением и суммой его цифр в этой системе счисления.
 
Например, пусть \(n = 239\), \(k = 8\). Тогда представление числа n в восьмеричной системе счисления — \(357\), а ответ на задачу равен \(3 \cdot 5 \cdot 7 ? (3 + 5 + 7) = 90\).
 
 
Входные данные
Строка содержит два натуральных числа: n и k (\(1 <= n <= 10^9\), \(2 <= k <= 10\)). Оба этих числа заданы в десятичной системе счисления.
 
Выходные данные
Выведите ответ на задачу (в десятичной системе счисления).
 

 

Примеры
№ Входные данные Выходные данные
1 239 8 90
2 1000000000 7 -34
Разные системы счисления
✓ 333✗ 187400лёгкаяВойти и решать
Премия#30774
Несмотря на кризис, компания Soft-Soft работает успешно. Директор компании принял решение выплатить сотрудникам премии. На следующий день был обнародован список счастливчиков. Чтобы не разглашать размер выплат, в списке напротив фамилий красовались странные цифры и даже буквы. Сотрудники быстро догадались, что размер премий записан в различных системах счисления. Но где и какая система счисления используется, сообразила только секретарша Танечка, которая вспомнила, что директор просил ее принести информацию о возрасте сотрудников. Она поняла, что директор отбрасывал десятки из числа, указывающего возраст, а к оставшимся единицам добавлял число 2. Полученное значение служило основанием для представления начисленной премии.
 
Помогите любопытной Танечке узнать размер премий в десятичной системе счисления. Известно, что размер премий не превышает 100000 рублей в десятичной системе счисления.
 
Входные данные
В первой строке  записаны два целых числа N и K – возраст и размер премии, разделенные пробелом. Возраст не превышает 100, размер премии указан в некоторой системе счисления (запись числа не содержит незначащих нулей, использует арабские цифры и заглавные английские буквы).
 
Выходные данные
Выведите одно число – размер премии в десятичной системе счисления.
 

 

Примеры
№ Входные данные Выходные данные
1 28 2800 2800
2 30 101 5
Разные системы счисления
✓ 142✗ 341600лёгкаяВойти и решать
Простые числа - 2#30773
Из заданного набора чисел выберите одно, имеющее максимальное количество простых делителей. Например, 30 имеет три простых делителя (2, 3 и 5), а 40 – только два (2 и 5).
 
Входные данные 
Первая строка  содержит число N – количество чисел в наборе. Во второй строке теста содержится N чисел, разделенных пробелом. Все числа во входных данных целые, принимающие значения от 2 до 1024.
 
Выходные данные 
В ответе выведите число с максимальным количеством простых делителей. Если таких чисел несколько, выведите наименьшее из них.
 
Примеры
№ Входные данные Выходные данные
1
10
3 5 7 9 11 13 15 17 19 21
 15
2
11
2 4 6 8 10 13 39 105 200 201 143
 105
Простые числа и разложение на множители
✓ 424✗ 1 136600лёгкаяВойти и решать
Разложение числа на 5 и 3#30771
На сколько пятерок и троек можно разложить число, чтобы количество разложений было минимально.

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

Выходные данные
Выведите два целых числа через пробел: число пятерок и число троек.
 

 

Примеры
№ Входные данные Выходные данные
1 8 1 1
2 11 1 2
3 15  3 0
Остатки
✓ 134✗ 141500лёгкаяВойти и решать
Единичный НОД#30770
Заданы два натуральных числа в десятичной системе счисления, состоящие из единиц. В первом числе ровно N единиц, а во втором их ровно M. Требуется найти НОД этих чисел. 
 
Входные данные
В единственной строке  записаны два целых числа N и M (\(1 <= N,\ M <= 2000\)).
 
Выходные данные
Выведите ответ без ведущих нулей.
 

 

Примеры
№ Входные данные Выходные данные
1 1 1 1
2 1 2 1
НОД и алгоритм Евклида
✓ 370✗ 477500лёгкаяВойти и решать
Поделиться
Класснуть