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

НОД и НОК#24905

Дано число n – количество чисел. В следующей строке дано n чисел, каждое не больше 1000.
Вам необходимо вывести количество таких пар чисел (a, b), что НОК (a, b) = НОД (a, b).

НОК (a, b) - наименьшее общее кратное этих двух чисел, то есть наименьшее число, которое делится сразу на оба числа. \( НОК (20, 30) = 60\).
НОД (a, b) – наибольший общий делитель этих двух чисел, то есть наибольшее число, на которое делятся оба числа. \(НОД (20, 30) = 10\).
Напишите эффективную по памяти и времени программу.

Входные данные
В первой строке вводится натуральное число n – количество данных вам чисел.
Во второй строке вводятся сами числа, каждое из них целое и принадлежит отрезку [0; 1000].

Выходные данные
Выведите одно целое число – количество пар чисел (a, b), таких, что НОК(a,b) = НОД(a,b).

Примеры

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

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

✓ 636✗ 2 555600лёгкаяВойти и решать

Тяжелая, вариант-2#24757

Вы работаете менеджером и составляете план работ на ближайшее время. Компания, в которой вы работаете, планирует заработать не менее X рублей. Всего имеется n задач, которые необходимо сделать. Однако, вы понимаете, что, возможно, выполнять все задачи нет необходимости, и хотите составить оптимальный план, выбрав для выполнения некоторые из них.

Про каждую задачу известно время t_i, которое нужно затратить, чтобы сделать её, а также прибыль p_i в рублях, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

Суммарная прибыль от выполнения этих задач была равна X или более рублей.
Суммарное время, затраченное на выполнение задач, включённых в план, было минимально.

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

Формат входного файла

В первой строке входного файла input.txt находятся натуральные числа X (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) — необходимая минимальная прибыль и число задач.

Следующие n строк содержат по два натуральных числа t_i и p_i (1 ≤ t_i, p_i ≤ 100 000) — время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

Формат выходного файла

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

Ввод	Вывод
10 3 6 20 2 7 3 4	5

Простые задачи на перебор

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

Максимальная прибыль#24755

Вы работаете менеджером и составляете план работ на следующий месяц. Каждый месяц разделён на T равных единиц времени. Всего имеется n задач, которые необходимо сделать. Однако, вы понимаете, что, возможно, успеть сделать все задачи за месяц не получится и хотите составить оптимальный план, выбрав для выполнения некоторые из них.

Про каждую задачу известно время t_i, которое нужно затратить, чтобы сделать её, а также прибыль p_i, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

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

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

Обратите внимание на то, что единственный подходящий под условия план может не содержать ни одной задачи.

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

В первой строке находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа t_i и p_i (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

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

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

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31

битмаски Задача о рюкзаке

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

Легкая, вариант-1#24754

Вы занимаетесь разработкой системы по продаже билетов на поезда. Несмотря на то, что поезда ходят по множеству различных маршрутов, вы будете работать только с одним из них. Маршрут рассматриваемого поезда состоит из n остановок: маршрут начинается в первой из них, а заканчивается в n-й, соответственно. Всего в поезде имеется m мест для пассажиров.

Эта система будет использоваться для продажи билетов пассажирам. При покупке билета пассажир указывает номер станции L, на которой он хочет сесть на поезд и номер станции R, на которой он хочет сойти с поезда. Если у одного пассажира есть билет до станции S, а другой хочет купить билет от станции S, то они друг другу не мешают: второй может занимать только что освободившееся место первого. Система должна сообщить пассажиру следующую информацию:

«YES», если в поезде есть свободные места. В этом случае пассажир покупает один билет с L-й по R-ю станцию.
«NO», если подходящих свободных мест нет. В этом случае пассажир билет не покупает.

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

В первой строке находятся натуральные числа n (2 ≤ n ≤ 100), m (1 ≤ m ≤ 100) и k (1 ≤ k ≤ 100) — число станций в маршруте поезда, максимальное число пассажиров в поезде и число обращений обращений пассажиров к системе покупки билетов.

Следующие k строк содержат по два натуральных числа L_i и R_i (1 ≤ L_i < R_i ≤ n) — начальная и конечная станции в i-м обращении к системе.

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

Для каждого обращения к системе в своей строке выведите её ответ: YES или NO.

Пример входных и выходных данных

Ввод	Вывод
5 2 4 1 4 1 3 2 5 3 5	YES YES NO YES

Алгоритмы обработки Задачи на моделирование

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

Легкая, вариант-2#24735

На складе хранятся ящики разных цветов и размеров. Каждый цвет и каждый размер имеют свой порядковый номер в информационной системе.

Перед отправкой ящики упаковывают и сортируют. Упаковка и сортировка ящиков неэффективна и происходит следующим образом:

Ящик под номером i поступает на склад.
Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
Поступающий ящик помещается наверх найденной или сформированной стопки.
Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.

Отправка продолжается до тех пор, пока не будут обработаны все поступающие на склад ящики.

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

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

В первой находятся три натуральных числа n, m, k (1 ≤ n, m, k ≤ 100) — количество ящиков, поступающих на склад, количество различных размеров и количество различных цветов соответственно.
В каждой из следующих n строк находятся по два натуральных числа x_i и y_i (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ k) — номер размера и номер цвета ящика, который поступит i-м на склад.

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

Требуется вывести одно число — сколько ящиков будут отправлены.

Пример входных и выходных данных

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

Задачи на моделирование Очередь реализация

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

Златопольский 13.6#24662

Известны максимальные скорости 20-ти моделей автомобилей. Все значения выражены в км/ч.
Написать программу, которая организовывает ввод исходных данных в структуру и выводит названия моделей автомобилей с самой маленькой и самой большой максимальной скоростью

Входные данные:
20 строк в формате <Марка автомобиля> <Максимальная скорость>

Выходные данные:
Необходимо вывести через пробел названия двух моделей автомобилей, сначала автомобиль с наибольшей максимальной скоростью, затем через пробел автомобиль с наименьшей максимальной скоростью

Алгоритмы обработки Использование сортировки Одномерные массивы

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

Замена букв#24655

Ввести с клавиатуры символьную строку и заменить в ней все буквы «a» на «b» и все буквы «b» на «a» (заглавные на заглавные, строчные на строчные).

Входные данные
В первой строке задается строка без пробелов.

Выходные данные
Необходимо вывести модифицированную строку.

Примеры

№	Входные данные	Выходные данные
1	aabbAABBccCC	bbaaBBAAccCC

Обработка текста Строки

✓ 8 070✗ 14 080300лёгкаяВойти и решать

Желание для Герцога Циклонского#23629

Герцог Циклонский, обладая безграничным могуществом, что отражено в его девизе "Все могу!", ежегодно проводит конкурс среди приглашенных на исполнение самого заветного желания.
Отбор проводится следующим образом: все претенденты рассаживаются на пронумерованных стульях (нумерация стульев начинается с 1) вокруг Большого Круглого стола, после чего посредством Константы счета начинается отсчет по часовой стрелке.
Претендент, на которого падает Константы счета, обязан освободить место, отсчет продолжается до тех пор, пока не останется два человека.
Требуется при известном числе гостей N и Константы счета С определить номера стульев, которые нужно занять, чтобы попасть в число этих двух "счастливчиков".

Входные данные
В первой строке вводится число N (\(1<=N<=100\)) - количество приглашенных претендентов. Во второй строке вводится Константы счета (\(С<=100\)).

Выходные данные
Необходимо вывести через пробел два числа - номера стульев "счастливчиков".

Примеры

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

Алгоритмы обработки Задачи на моделирование

✓ 1 172✗ 3 067600лёгкаяВойти и решать

Использование сортировки#23590

Известны значения роста всех учащихся класса. Определите рост учащегося, который при построении учащихся по росту, в порядке возрастания, занимал бы 10-е место при счете от самого высокого ученика.

Нельзя использовать встроенную сортировку.

Входные данные
В первой строке вводится натуральное число N - количество учащихся класса (11 <= N <= 35).
Во второй строке вводятся N целых чисел - рост учащихся.

Выходные данные
Необходимо вывести на экран значение роста учащегося, который бы занимал 10-е место по росту в порядке убывания, при счете от самого высого ученика.

Пример

№	Входные данные	Выходные данные
1	12 148 144 154 145 155 130 157 136 152 130 177 166	136

Квадратичные сортировки

✓ 2 088✗ 2 168300лёгкаяВойти и решать

Покупка билетов#23414

За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя "постояльцев" очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному.

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

Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит A_i секунд, на продажу двух билетов - B_i секунд, трех билетов - C_i секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).

Входные данные:
- в первой строке записано число N - количество покупателей в очереди (\(1<=N<=5000\));
- далее идет N троек натуральных чисел A_i, B_i, C_i. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются начиная от кассы.

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

Примеры

№	Входные данные	Выходные данные
1	5 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1	12
2	2 3 4 5 1 1 1	4

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

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

Ход конем#23411

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-4927. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

Клавиатура телефона выглядит так:

7	8	9
4	5	6
1	2	3
	0

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

Входные данные: на вход подается целое число N (\(1<=N<=50\)).

Выходные данные: выведите файл искомое количество телефонных номеров.

Примеры

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

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

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

Подпоследовательности#23409

Дана последовательность, требуется найти длину наибольшей возрастающей

подпоследовательности.

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

В первой строке входного файла записано число N - длина последовательности (1 <= N <= 1000). Во второй строке записана сама последовательность (через пробел). Числа последовательности - целые числа, не превосходящие 10000 по модулю.

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

В выходной файл требуется вывести наибольшую длину возрастающей подпоследовательности.

Примеры

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

Динамическое программирование: последовательности

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

Гвоздики#23408

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

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

- в первой строке записано число N - количество гвоздиков (\(2 <= N <= 100\));
- в следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

Выходные данные: выведите единственное число - минимальную суммарную длину всех ниточек.

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

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

Минимальный путь в таблице#23407

В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке.

За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено).

При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.

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

В первой строке записаны два числа N и M - размеры таблицы (\(1<=N<=20\), \(1<=M<=20\)). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).

Выходные данные
Выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.

Примеры

№	Входные данные	Выходные данные
1	3 4 1 1 1 1 5 2 2 100 9 4 2 1	8

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

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

Распаковка строчки#23406

Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки.

Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.

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

Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n - количество повторений символа (целое число от 2 до 99), а A - заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.

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

В выходной файл выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).

Примеры

Ввод	Вывод
3A4B7D	AAABBBBDDDDDDD
22D7AC18FGD	DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF FFFFFFFFGD
95AB	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAB
40AB39A	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Алгоритмы на строках

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

Поиск подстроки#23403

Сколько раз встречается?

Входные данные
Вам дается две строки. Длина каждой из строк не превышает 255 символов.

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

Примеры

№	Входные данные	Выходные данные
1	abab abababcab	2

Пояснение: подстрока abab встречается во второй строке дважды, начиная с 1-го и 3-го символа.

Поиск подстроки в строке

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

Найти 1543#23401

Найдите в тексте 1543.

Входные данные
Программа получает на вход текст, содержащий сколь угодно длинные строки. Количество строк неизвестно.

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

Если в нем встречается число 1543, выведите слово URA, если же 1543 в файле не встречается, выведите NO.

Примеры

№	Входные данные	Выходные данные
1	hgdfjgkdghkdjgkgkd1543gjdlgkdjlg	URA
2	1=5 4=3	NO

Поиск подстроки в строке

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

Наименьшее число#23378

Дана последовательность чисел. Найти в ней наименьшее число.

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

Задано сначала число N (количество чисел в последовательности), а затем

N чисел. Все числа - из диапазона Integer. N<=100

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

Выведите наименьшее число.

Линейный поиск

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

Монотонность#23363

Университет Иннополис готовится к проведению Летней школы олимпиадного программирования. Сейчас им нужно выбрать даты проведения.

Организаторы заметили, что школа проходит лучше, если настроение детей с каждым днем школы улучшается, также они заметили, что настро- ение школьников сильно зависит от погоды: в ясную погоду школьники веселее, чем в пасмурную. Организаторы запросили прогноз погоды на n дней, в которые можно провести школу. Для каждого дня они посчитали число ai — солнечность i-го дня. Теперь они хотят выбрать для про- ведения школы некоторый непрерывный отрезок дней, такой, что каждый следующий день школы солнечность строго больше, чем в предыдущий.

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

Формат входных данных
В первой строке входного файла задано число n — число дней, в которые можно провести школу. Во второй строке заданы n ( 1<=n<=10⁵) чисел ai — солнечности дней (0 <= a_i<= 10⁹ ).
Формат выходных данных
Выведите одно число: максимальное число дней, которое может идти школа так, чтобы каждый следующий день школы был солнечнее, чем предыдущий.

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

Линейный поиск

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

Интересные числа (С', C)#23334

Маленький Вася очень любит числа, а особенно сильно он любит интересные числа. Вася считает число x интересным, если сумма квадратов его цифр делится на число 7. Например, число 123 -

интересное, потому что 1² + 2² + 3² = 14 делится на 7, а число 16 - нет, потому что 1² + 6² = 37 не делится на 7. Однажды Вася увидел на доске число x, он сразу же захотел узнать величину минимального интересного числа, которое строго больше чем x. Так как Вася еще слишком юн, он обратился к вам за помощью в решение этой задачи.

Формат входных данных

Во входном файле содержится единственное целое число x - число, написанное на доске 0<= x <= 10⁵

Формат выходных данных
В единственную строку выходного файла выведите минимальное интересное число, которое строго больше чем x.

Ввод	Вывод
1	7
0	7
35	70

Арифметические алгоритмы (Теория чисел)Вывод формулы Циклы

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