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

Покраска забора#31880

Однажды, в наказание за шалости и обман, тетя Полли заставила Тома красить забор длиной L ярдов. Все вы прекрасно помните, что Том продавал (за различные ништячки) свою работу другим мальчишкам, которые хотели побелить забор.
К тому моменту, когда у Тома закончилась известка, забор успели покрасить N мальчишек. И так как за мальчишками Том не особо следил, то каждый красил ту часть забора, которая ему больше нравилась.
Каждый i-й мальчишка начинал красить забор с вертикальной дощечки с координатой Left_i и красил до дощечки с координатой Right_i(длину дощечки считать равной 1).
Определите длину забора, которую необходимо будет докрасить Тому самостоятельно.

Входные данные
В первой строке находится число L - длина забора тети Полли. Во второй строке находится число N, в следующих N строках - пары Left_i и Right_i. Все числа - целые
Ограничения:
\(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

Быстрая сортировка

✓ 226✗ 1 198900средняяВойти и решать

Анти-QuickSort#31879

Дано число N (1<=N<=1000), а затем N натуральных чисел из диапазона от 1 до 100.
Вывести перестановку элементов массива, на которой быстрая сортировка выполнит максимальное число сравнений, при условии, что "опорным" будет элемент посередине.

Входные данные: в первой строке задаётся число N
Во второй строке идут N чисел - элементы массива
Выходные данные: выведите требуемую перестановку элементов исходного массива

Примеры

№	Входные данные	Выходные данные
1	5 3 10 1 20 7	3 20 7 1 10

Быстрая сортировка

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

Сложить две дроби#31872

Даны две рациональные дроби: \(a \over b\) и \(c \over d\). Сложите их и результат представьте в виде несократимой дроби \(m \over n\).

Входные данные
Программа получает на вход 4 натуральных числа a, b, c, d, не превосходящих 100.

Выходные данные
Программа должна вывести 2 натуральных числа m и n такие, что \({m \over n} = {a \over b}+ {c \over d}\) и дробь \(m \over n\) – несократима.

Примеры

№	Входные данные	Выходные данные
1	1 3 1 2	5 6

НОД и алгоритм Евклида

✓ 1 138✗ 1 750400лёгкаяВойти и решать

Применение Малой Теоремы Ферма#31866

Дано число a и простое число p. Найти такое минимальное число x, что \((a * x) \% p = 1\).

Входные данные
На вход подаются два натуральное числа a, p (\(a,\ p <= 10^{18} \)).

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

Примеры

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

Малая теорема Ферма

✓ 274✗ 1 154600лёгкаяВойти и решать

Сумма функции Эйлера#31850

Посчитать сумму функций Эйлера вида: \(\phi(1) + \phi(p) + \phi(p^2) + ... + \phi(p^\alpha)\), где \(p\) - простое число, \(\alpha\)- натуральное число.

Входные данные
В одной строке через пробел подаются два числа \(p\) и \(\alpha\) (\(p <=11, \alpha <=60 \)).

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

Пример

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

Функция Эйлера

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

Расчет асимптотики - 4#31799

Для приведенного ниже кода, найдите асимптотику:

#include <bits/stdc++.h>
main()
{
    std::string s;
    std::cin >> s;
    int n = s.size(), p[50003], j, i = 1;
    for (; i < n; i++)
    {
        j = p[i - 1];
        for (; j && s[i] != s[j]; j = p[j - 1]);
        p[i] = (s[i] == s[j] ? ++j : j);
    }
    std::cout << n - p[n - 1];
}

1) O(n^2) 2) O(nsqrt(n)) 3) O(nlogn) 4) O(n)

Z-функция. Префикс-функция

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

Расчет асимптотики - 2#31797

Для приведенного ниже кода, найдите асимптотику:

int n;
vector <int> arr(n);
next_permutation(arr.begin(), arr.end());

1) O(n!) 2) O(n) 3) O(1) 4) O(nlogn)

Перестановки

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

Расчет асимптотики - 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

В Волшебной стране используются монетки достоинством A₁, A₂,..., A_M. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы сначала поступает число N (1 <= N <= 10⁹), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A₁, A₂,..., A_M (1 <= A_i <= 10⁹).

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

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).

Ввод	Вывод
100 6 11 20 30 40 11 99	3 40 30 30

Рекурсивный перебор Рекурсия

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

Кинотеатр#31791

В первом ряду кинотеатра N + 2 мест, крайние места заняты персоналом кинотеатра, но N мест посередине свободно. K школьников входят в зрительный зал по очереди, и, конечно же, каждый школьник достаёт спиннер и начинает его крутить до начала сеанса. Поэтому каждый школьник выбирает себе место как можно дальше от уже занятых мест. А именно, школьник находит самый большой свободный участок в ряду (любой, если таких несколько) и садится посередине него. Если число свободных мест на этом участке было нечётно, то школьник садится точно посередине участка, тогда слева и справа от него остаётся поровну свободных мест. Если же это число чётно, то школьник выбирает одно из двух свободных мест посередине, тогда с одной стороны от школьника будет на одно свободное место больше, чем с другой стороны.

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

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

Ввод	Вывод	Примечание
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

Обход в глубину Рекурсия

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

Робот#31782

Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.

В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из N операций.

Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.

Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.

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

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

В первой строке записано число K > 0 - количество операций, которые можно записать в память робота.

Вторая строка состоит из N > K строчных латинских букв, обозначающих операции - процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой (N <= 200000).

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

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

Ввод	Вывод
2 zabacabab	5
2 abc	0

"Два указателя"

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

Садовник-художник#30783

Садовник посадил N деревьев в один ряд. После посадки деревьев садовнику нужно их покрасить. В его распоряжении есть краска трех цветов: белая, синяя и оранжевая. Сколько способов покраски деревьев есть у него, если никакие два соседних дерева нельзя красить в одинаковый цвет?

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

В единственной строке записано одно натуральное число - количество деревьев N (1 ≤ N ≤ 50).

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

В единственную строку нужно вывести одно число - количество способов покраски.

Ввод	Вывод
3	12

Динамическое программирование

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

Несложная сортировка#30779

Пусть x – целое положительное число, а k – натуральное число от 1 до 10. Пусть s(x, k) равно сумме цифр числа x, представленного в системе счисления по основанию k.

Задано n чисел a₁, a₂, ..., a_n. Необходимо вычислить последовательность b_i по формуле \(b_i = s(a_i, k_1) \cdot s(a_i, k_2)\). После этого отсортировать последовательность b_i по неубыванию.

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

Первая строка содержит три целых числа: n, k₁, k₂ (\(1 <= n <= 1000\), \(2 <= k_1, k_2 <= 10\)). Вторая строка содержит n целых чисел: a_i (\(1 <= a_i <= 10^9\)).

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

В ответе выведите n чисел – b_i в требуемом порядке.

Примеры

№	Входные данные	Выходные данные
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

НОД и алгоритм Евклида

✓ 795✗ 1 749500лёгкаяВойти и решать

Упрощение номеров#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

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

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

Премия#30774

Несмотря на кризис, компания Soft-Soft работает успешно. Директор компании принял решение выплатить сотрудникам премии. На следующий день был обнародован список счастливчиков. Чтобы не разглашать размер выплат, в списке напротив фамилий красовались странные цифры и даже буквы. Сотрудники быстро догадались, что размер премий записан в различных системах счисления. Но где и какая система счисления используется, сообразила только секретарша Танечка, которая вспомнила, что директор просил ее принести информацию о возрасте сотрудников. Она поняла, что директор отбрасывал десятки из числа, указывающего возраст, а к оставшимся единицам добавлял число 2. Полученное значение служило основанием для представления начисленной премии.

Помогите любопытной Танечке узнать размер премий в десятичной системе счисления. Известно, что размер премий не превышает 100000 рублей в десятичной системе счисления.

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

В первой строке записаны два целых числа N и K – возраст и размер премии, разделенные пробелом. Возраст не превышает 100, размер премии указан в некоторой системе счисления (запись числа не содержит незначащих нулей, использует арабские цифры и заглавные английские буквы).

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

Выведите одно число – размер премии в десятичной системе счисления.

Примеры

№	Входные данные	Выходные данные
1	28 2800	2800
2	30 101	5

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

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

Простые числа - 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

Простые числа и разложение на множители

✓ 458✗ 1 223600лёгкаяВойти и решать

Постоянная Капрекара#30772

Возьмем четырехзначное число, в котором не все цифры одинаковы, например, 6264. Расположим цифры сначала в порядке убывания - 6642; затем, переставив их в обратном порядке, получим 2466. Вычтем последнее число из 6642. На следующем шаге с полученной разностью проделаем тоже самое. Через несколько таких действий получится число, переходящее само в себя и называемое постоянной Капрекара. Если разность получается трехзначная, надо в начале добавить ноль.

Требуется написать программу, которая находит эту постоянную и количество шагов для ее получения из заданного четырехзначного числа.

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

Выходные данные: выведите в первой строке постоянную Капрекара, во второй – количество шагов для ее получения.

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

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