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

Массив#26995

У Пети есть массив отсортированных в порядке неубывания натуральных чисел. Известно, что чисел N. Петя пытливый мальчик, поэтому хочет найти в массиве три числа x, y и z (x <= y <= z), такие, что сумма (x - y)² + (x - z)² + (z - y)² была бы максимальна. Помогите ему в этом.

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

В первой строке входного файла находится число N> (3<=N <= 100000). На следующей строке находятся N натуральных чисел, каждое из которых не превышает 10000.

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

Нужно вывести три числа x, y и z в порядке возрастания. Если вариантов такой тройки несколько, вывести любой.

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

Одномерные массивы

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

Разбиение на пары#26982

Мария Ивановна написала на доске четыре числа: a, b, c и d. После чего предложила своему классу разбить эти числа на две пары так, чтобы сумма произведений чисел в парах была максимальна.

Например, если на доске написаны числа 5, 6, 7 и 8, то оптимально разбить их на пары (5, 6) и (7, 8), в этом случае искомая сумма равна 5 × 6 + 7 × 8 = 86.

Формат ввода

На вход подаются четыре целых числа: a, b, c и d. Все числа по модулю не превышают 1000.

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

Выведите искомую максимальную сумму.

Пример

Ввод	Вывод
5 6 7 8	86

Линейные алгоритмы

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

2048#26981

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

Напомним правила игры 2048. На поле 4 × 4 разбросаны числа, являющиеся степенями двойки от 2 до 1024, некоторые клетки могут быть пустыми. Каждый ход игрок может сдвинуть все плитки игрового поля в одну сторону. Если при сдвиге две плитки одного номинала «налетают» одна на другую, то они слипаются в одну, номинал которой равен сумме соединившихся плиток. За каждое соединение игровые очки увеличиваются на номинал получившейся плитки. Плитка, получившаяся при слипании двух других, не может больше участвовать в слипании.

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

Программа получает на вход четыре строки, в каждой из которых записано четыре числа. Числа являются степенями двойки от 2 до 1024. В некоторых клетках записано число 0, означающий, что данная клетка пуста.

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

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

Примеры

№	Входные данные	Выходные данные
1	2 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0	4
2	2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0	8
3	2 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0	4
4	2 2 4 0 0 2 2 2 0 2 4 0 2 4 4 0	16

Примечания

Внимательно прочитайте этот раздел для лучшего понимания правил игры.

Наилучший ответ на первый тест достигается движением вниз.
0 0 0 0
0 0 0 0
2 0 0 0
4 0 0 0

Наилучший ответ на второй тест достигается движением вниз.
0 0 0 0
0 0 0 0
4 0 0 0
4 0 0 0

Наилучший ответ на третий тест достигается движением влево.
4 4 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Наилучший ответ на четвертый тест достигается движением вниз.
0 0 0 0
0 2 4 0
0 4 2 0
4 4 8 2

Двумерные массивы

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

Бумага для олимпиады#26980

Лёлик решил провести у себя в школе олимпиаду. Для этого ему необходимо закупить много упаковок бумаги. Лёлику очень повезло, потому что один крупный канцелярский магазин объявил две рекламных акции: «купи A одинаковых товаров и получи еще один товар бесплатно», а также «купи B товаров по цене B-1 товара».

Лёлик узнал, что одна пачка бумаги в этом магазине стоит n рублей. Теперь он хочет определить сколько упаковок бумаги он сможет купить на p рублей. Помогите ему.

Формат ввода

На вход подаются четыре натуральных числа, разделенных пробелом: A, B, p и n (1 ≤ A ≤ 100, 2 ≤ B ≤ 100, 1 ≤ p, n ≤ 10000).

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

Выведите единственное целое число — максимальное количество упаковок бумаги, которое сможет купить Лёлик.

Пример

Ввод	Вывод
4 4 13 2	8
3 4 8 3	2
3 4 7 1	9

Примечания

В первом примере, дважды используя вторую акцию, можно купить 8 упаковок бумаги, заплатив за 6.

Во втором примере акциями воспользоваться нельзя.

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

Вывод формулы

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

Логические выводы#26979

Болик решает логическую задачу. Для ее решения, он сначала сделал N базовых предположений. После этого происходит следующий процесс: Холмс разбивает все предположения на пары, из каждой пары отбрасывает наименее вероятное предположение (предположения таковы, что всегда есть наименее вероятное). Если получилось так, что какому-то предположению, пары не хватило, то Болик оставляет его для рассмотрения. Алгоритм повторяется пока у Болика не останется последнее предположение.

Болик также привык считать количество логических выводов, которое он сделал. Так, например, если рассматриваются 11-ое и 31-ое предположение и отбрасывается 11-ое, то Болик совершил один логический вывод. Если, например, 238-ому предположению не хватило пары, то Болик оставляет его для рассмотрения, но, конечно, не считает это действие за логический вывод. Более того, последний вывод Болик проверяет дважды.

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

Формат ввода

На вход подается натуральное число N (1 ≤ N ≤ 10²¹⁸) — количество базовых предположений.

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

Выведите единственное целое число — количество логических выводов.

Пример

Ввод	Вывод
3	3

Вывод формулы

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

Максимальная сумма, не делящаяся на 4#25980

На вход программы поступает последовательность из N натуральных чисел. Нужно выбрать из них произвольное количество чисел так, чтобы их сумма была максимальной и не делилась на 4.

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

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

На вход программе подаётся натуральное число N (\(N <= 1000\)), а затем N натуральных чисел, каждое из которых не превышает 10000.

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

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

Примеры

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

ЕГЭ - вычислительные задачи

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

Выборка чисел для максимальной суммы, кратной 4#25979

Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел была кратна 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Входные данные
На вход программе в первой строке подаётся количество троек N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

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

Примеры

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

ЕГЭ - вычислительные задачи

✓ 208✗ 2 3191 000средняяВойти и решать

Задача#25974

Для чего производится описание массивов?

1) чтобы самому запомнить сколько ячеек в массиве
2) чтобы компьютер запомнил имя массива
3) чтобы компьютер зарезервировал память для хранения элементов массива
4) чтобы компьютер зарезервировал количество энергии для обработки массива

Одномерные массивы

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

По мотивам ЕГЭ 2017#25970

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (a_i, a_j) этого набора, в которых \(1 <= i < j <= N\) и произведение элементов кратно 14.
Напишите эффективную по времени и по памяти программу для решения этой задачи.

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

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

Примеры

№	Входные данные	Выходные данные
1	5 14 7 7 2 19	6

ЕГЭ - вычислительные задачи

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

3-ий минимум#25969

От цифровых датчиков в компьютер поступает информация о характеристиках физического процесса. Результатом каждого измерения является целое число.

Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет выводить третье по величине (считая от минимума) значение измерения. Если несколько измерений имеют одинаковые значения, то они учитываются как одно измерение. Если искомого значения не существует (например, когда все значения измерений равны), то нужно вывести символ "#". Следует учитывать, что количество измерений может быть очень велико.

На вход программе в первой строке подается общее количество N значений измерений.
В каждой из последующих N строк записано целое число. Гарантируется, что \(N>0\), то есть всегда имеется хотя бы одно измерение.

Примеры

№	Входные данные	Выходные данные
1	5 100 10 100 10 100	#

ЕГЭ - вычислительные задачи

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

Дело в шляпах#25919

Как-то раз в город Шляп заехал известный парикмахер. До его приезда парикмахеры были явно не очень, так как все жители города предпочитали ходить в шляпах. Но наконец-то настало время снять шляпы!

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

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

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

Местного шляпника теперь интересует, каким жителям ему больше не нужно будет делать шляпы, так как они будут ходить с новыми стильными стрижками?

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

В первой строке содержится число N (1 <= N <= 10⁵) количество людей, которые придут к парикмахеру.

Каждая из следующих N строк обозначает пришедшего к парикмахеру жителя и содержит по три числа: фасон шляпы (все фасоны местного шляпника пронумерованы от 1 до 10⁹), момент времени прихода s (1 <= s <= 10⁹), и время на стрижку t (1 <= t <= 10⁹). Строки упорядочены по времени прихода жителей. Гарантируется, что все приходят в разное время. Так как парикмахер очень крут, гарантируется, что он успеет постричь всех жителей до момента времени 2 · 10⁹, даже если бы из очереди никто не уходил.

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

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

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

Задачи на моделирование Очередь Разбор случаев

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

Держать строй#24911

Ник Фьюри решил, что бойцы отряда спецназа, являющегося подразделением организации S.H.I.E.L.D., помогут мстителям отразить атаку войска Локи. Он решил, что в бой отправятся n бойцов, а все остальные понадобятся в других местах. Теперь ему осталось только выбрать, какие именно бойцы пойдут в атаку.

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

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

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

Первая строка входного файла содержит два числа n и m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000) количество солдат в строю и количество команд, которые подаст Ник. Вторая строка содержит n целых неотрицательных чисел, не превосходящих 10⁹ исходный рост солдат в строю. Следующие m строк содержат команды, подаваемые Ником. Если первый символ в строке, описывающей очередную команду, '!', то за ним следуют два числа k и x (1 ≤ k ≤ n, 0 ≤ x ≤ 10⁹), где k место в строю того солдата, которого должен заменить солдат роста x. Команда второго типа описывается знаком '?'.

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

Для каждой команды второго типа в отдельной строке выведите "YES", если в данный момент солдаты в строю стоят по неубыванию роста, и "NO" в противном случае.

Ввод	Вывод
5 5 2 4 6 8 10 ? ! 2 7 ? ! 3 8 ?	YES NO YES

Задача на реализацию

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

Поймать Халка#24910

Когда Локи ловил Халка, он немного не рассчитал своих сил, и случайно перенес его в параллельный n-мерный мир. После этого Локи намертво вморозил Халка в глыбу льда. Для окончательной победы Локи необходимо только отпилить от глыбы лишний лед так, чтобы остался только сам замороженный Халк. Пространство, в которое Локи перенес все происходящее, не более чем трехмерно. В одномерном пространстве глыба представляет из себя отрезок некоторой длины, а Халк внутри вложенный в него отрезок. В двумерном пространстве глыба и Халк прямоугольники со сторонами, параллельными оcям координат, причем Халк вложен в глыбу. Аналогично, в трехмерном пространстве глыба и Халк являются параллелепипедами со сторонами, параллельными осям координат.

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

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

Первая строка входного файла содержит одно число n (1 ≤ n ≤ 3) количество измерений в пространстве, в котором происходит действие. Следующая строка содержит n натуральных чисел ai (1 ≤ a_i ≤ 10000) координаты одной из вершин глыбы. Будем считать, что вершина глыбы, противоположная данной, находится в начале координат.

В следующей строке сначала перечислены n целых чисел b_i (0 ≤ b_i ≤ a_i) координаты одной из вешин Халка, затем еще n целых чисел ci (0 ≤ c_i ≤ a_i) координаты противоположной вершины Халка.

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

Выведите единственное целое число минимальное количество разрезов, которые необходимо

сделать Локи, чтобы выпилить Халка.

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

Задача на реализацию

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

Это Бомба#24906

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

Инструкция:

Посчитайте числовой код для числа на дисплее соответственно приведённым правилам и введите его. Применяется первое подошедшее правило:

1. Если число <= 2, то числовой код равен 1.

2. Если число заканчивается на 7, то нужно отнять от него 5. Посчитайте числовой код для нового числа и прибавьте 1.

3. Если число делится на 4 без остатка, его числовой код равен сумме кодов для числа,делённого на 4 и числа, делённого на 2.

4. Во всех остальных случаях к числу нужно прибавить 1. Посчитайте числовой код для нового числа и прибавьте 2.

Какой числовой код нужно ввести Мише?

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

В единственной строке содержится одно число от 1 до 10⁸, которое отображается на дисплее.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

Ввод	Вывод
1	1
10	12

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

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

Тяжелая, вариант-1#24903

На уроке информатики учитель рассказал Васе про новый вид строк — минимально-символьные строки. Строка называется минимально-символьной, если символ, который встречается в ней минимальное количество раз, единственен. Например, строка "abacaba" — минимально-символьная, потому что единственный символ, который встречается минимальное количество раз в ней — 'c'. В то же время строка "cababac" — не минимально-символьная, потому что символы 'b' и 'c' встречаются в ней минимальное количество раз, то есть не являются единственными.

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

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

В единственной строке входного файла input.txt записана строка s, характеризующая набор символов. Ее длина не превосходит 100.

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

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

В следующих k строках выходного файла требуется вывести минимально-символьные строки, составленные из данного набора символов.

Если существует несколько правильных ответов, разрешается вывести любой из них.

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

Ввод	Вывод
abacaba	1 abacaba
abcabc	2 abb acc
abc	3 a b c
cababac	2 bcb acaa

Разбор случаев реализация

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

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

В Берляндии каждый автомобиль имеет регистрационный номер. Автомобильные номера в Берляндии имеют следующий вид: LDDLDDL, где символ L обозначает строчную латинскую букву, а D цифру.

Филипп устроился работать в службу регистрации автомобильных номеров. По своей неопытности в первый же день работы Филипп разлил на стопку номеров кофе. У некоторых номеров оказался залит второй блок цифр (цифры на позициях 5 и 6).

Филипп считает, что все номера в Берляндии уникальны, поэтому он хочет быстро подобрать все залитые цифры, так чтобы среди всех номеров не было двух одинаковых. Задача показалась ему нерешаемой, и он попросил вас помочь ему.

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

В первой строке записано натуральное число n, не превосходящее 1000 — количество номеров в стопке.

В следующих n строках находятся n регистрационных номеров, в i+1-й строке i-й номер, в описанном выше формате. На месте залитых цифр находятся знаки вопросов.

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

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

Первая строка должна содержать NO, если в стопке были одинаковые номера. Иначе первая строка должна содержать YES, а далее n строк должны содержать номера из стопки — по одному в каждой строке, причем i+1-я строка должна содержать i-й номер. Номера должны удовлетворять принятому в Берляндии формату в том же порядке, что и во входном файле.

Если ответов несколько — разрешается вывести любой.

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

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

Ввод	Вывод
4 a10a10c a30b??c a30b??c x70r??r	YES a10a10c a30b10c a30b22c x70r37r
3 a00b10c a00b10c c02y03x	NO
2 a99a??b a99a??b	YES a99a11b a99a22b

Задача на реализацию Простые задачи на перебор

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

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

Филипп устроился работать в службу регистрации автомобильных номеров. По своей неопытности в первый же день работы Филипп разлил на стопку номеров кофе. У некоторых номеров оказался залит первый блок цифр (цифры на позициях 2 и 3).

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

В первой строке входных данных записано натуральное число n, не превосходящее 1000 — количество номеров в стопке.

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

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

Первая строка выходного данных должна содержать NO, если в стопке были одинаковые номера. Иначе первая строка должна содержать YES, а далее n строк должны содержать номера из стопки — по одному в каждой строке, причем i+1-я строка должна содержать i-й номер. Номера должны удовлетворять принятому в Берляндии формату в том же порядке, что и во входных данных.

Если ответов несколько — разрешается вывести любой.

Ввод	Вывод
4 a10a10c a??b30c a??b30c x??r70r	YES a10a10c a10b30c a22b30c x37r70r
3 a10b00c a10b00c c03y02x	NO
2 a??a99b a??a99b	YES a11a99b a22a99b

Задача на реализацию реализация

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

Составление условий - 9#24900

Составьте программу, которая печатает 1, если указанное высказывание является истинным, и 0 в противном случае

цифры исходного четырехзначного числа N образуют строго возрастающую последовательность

входные данные
на вход подается число N (1000<=N<=9999)

выходные данные
1 - если все цифры числа образуют строго возрастающую последовательность
0 - в противном случае

ПРИМЕР:
вход: 1234
вывод: 1

ПРИМЕР:
вход: 1224
вывод: 0

Условный оператор

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

Составление условий - 10#24899

данные числа х и у являются координатами точки, лежащей в первой координатной четверти

входные данные
на вход подаются два целых числа x и y (-10^5<x,y<10^5)

выходные данные
1 - данные числа х и у являются координатами точки, лежащей в первой координатной четверти
0 - в противном случае

Условный оператор

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

Составление условий - 11#24898

все цифры исходного четырехзначного числа различны

входные данные
на вход подается число N (1000<=N<=9999)

выходные данные
1 - если все цифры числа различны
0 - в противном случае

Условный оператор

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