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

По мотивам ЕГЭ 2018 - 2#30769

На вход программы подается натуральное число N ($N<= 100000$), а затем N строк, в в которых по одному целому числу. Необходимо посчитать количество пар чисел, у которых индексы отличаются не меньше чем на три и произведение кратно 29.
Напишите эффективную по памяти и времени программу.

Примеры

№	Входные данные	Выходные данные
1	6 29 7 8 29 4 5	3

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

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

Максимальное произведение смежных элементов#30768

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

Примеры

№	Входные данные	Выходные данные
1	7 2 3 -2 -3 -1 4 6	72

Пояснения: наибольшее произведение можно получить для последовательности -3 -1 4 6.

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

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

Тройки чисел#30756

Напишите программу, находящую количество троек целых чисел a, c, p таких, что p — простое число, числа удовлетворяют равенству: $$ \sqrt{a} - \sqrt{c} = \sqrt{p}. $$ Каждое из чисел a, c и p лежит в промежутке от N до M (то есть $N<=a<= M,\ N<=c<= M,\ N<=p<= M$).

Входные данные
Вводятся два целых числа N и M ($0<=N<=M<=100000$).

Выходные данные
Выведите искомое количество троек чисел a, c, p.

Примеры

№	Входные данные	Выходные данные
1	1 8	1
2	5 20	1
3	1 7	0

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

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

Поддержка максимума#30755

Дана последовательность чисел. Для каждого числа вывести текущий максимум на момент его ввода.

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

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

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

Выведите текущие максимумы.

Примеры

№	Входные данные	Выходные данные
1	7 4 2 5 -1 4 6 2	4 4 5 5 5 6 6

Куча

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

Пирамида (максимум)#30723

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

CLEAR — сделать пирамиду пустой (если в пирамиде уже были какие-то элементы, удалить все). Действие происходит только с данными в памяти, на экран ничего не выводится.

ADD n — добавить в пирамиду число n. Действие происходит только с данными в памяти, на экран ничего не выводится.

EXTRACT — вынуть из пирамиды максимальное значение. Следует и изменить данные в памяти, и вывести на экран или найденное максимальное значение, или, если пирамида была пустой, слово "CANNOT" (большими буквами).

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

Во входных данных записано произвольную последовательность запросов CLEAR, ADD и EXTRACT — каждый в отдельной строке, согласно вышеописанному формату. Данные заканчиваются строкой "END!"

Суммарное количество всех запросов не превышает 200000.

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

Для каждого запроса типа EXTRACT выведите на стандартный выход (экран) его результат (в отдельной строке).

Ввод	Вывод
ADD 192168812 ADD 125 ADD 321 EXTRACT EXTRACT CLEAR ADD 7 ADD 555 EXTRACT EXTRACT EXTRACT END!	192168812 321 555 7 CANNOT

Куча

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

Загранпаспорт#30718

Осень 2243-го года. Государства в прошлом, главным территориальным образованием является автономия. В результате терраформирования территория бывшей Евразии теперь представляет собой прямоульник, он разбит на w × h квадратных автономий, которые организованы в виде сетки из w автономий по ширине и h по высоте. Некоторые автономии входят в содружество Крипто, они представляют собой криптоанархистские технократические общества и не признают бюрократии. Остальные автономии входят в конфедерацию Бюрро, бюрократия в них доведена до высшего совершенства.

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

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

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

Формат входных данных
В первой строке входного файла содержатся три целых числа: w, h и n (1 ≤ w, h ≤ 500, 1 ≤ n ≤ 1 000). В каждой из следующих h строк содержится по w символов, они задают карту Евразии. Символ «A» обозначает автономию содружества Крипто, а «T» — автономию конфедерации Бюрро. Автономия, в которой Вениамин начинает свое путешествие, обозначена символом «V». Карта дана с севера на юг по строкам и с запада на восток по столбцам, таким образом, первый символ второй строки входного файла описывает самую северо-западную автономию. Гарантируется, что в Евразии есть хотя бы одна автономия Бюрро.

Формат выходных данных
В выходной файл выведите одну строку из символов «N», «E», «S», «W» — план путешествия Вениамина. Эти символы означают, что Вениамину следует поехать на север, восток, юг или запад, соответственно. Число перемещений в плане необходимо минимизировать, в процессе путешествия Вениамин должен ровно n раз въехать в автономию Бюрро. Если возможных оптимальных планов путешествия несколько, можно вывести любой.

Ввод	Вывод
5 3 6 AAATA VAATA AAAAT	EEENSNSN
3 1 2 TVT	WEE

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

✓ 1✗ 1—Войти и решать

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

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

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

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

Помогите Тому понять, сколько радости он сможет доставить своим друзьям.

Формат входных данных
Первая строка входного файла содержит два целых числа n (1 ≤ n ≤ 10⁵ ) и k (1 ≤ k ≤ 10⁹ ). Следующая строка содержит n целых чисел — значения a_i (1 ≤ a_i ≤ k).

Формат выходных данных
Выведите одно число — максимальное возможное значение x.

Ввод	Вывод
2 100 5 10	5
4 10 7 8 3 5	2

Пояснение
В первом примере x = 5, так как один из друзей просто не хочет красить больше пяти досок. Он придет первым, покрасит свои пять, после чего еще 10 неокрашенных досок достанется второму другу Тома. Оставшиеся 85 досок Тому придется красить самому.
Во втором примере достичь x = 2 можно, например, так. Сначала третий друг красит доски с 4 по 6 (3 неокрашенных доски). Затем четвертый друг красит доски с 1 по 5 (3 неокрашенных доски). Затем второй друг красит доски с 1 по 8 (2 неокрашенных доски). Наконец, первый друг красит доски с 6 по 10 и с 1 по 2 (2 неокрашенных доски, заметим, что забор идет по циклу и эти доски образуют последовательный отрезок).

Сканирующая прямая

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

Словарь синонимов#30711

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

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

Программа получает на вход количество пар синонимов N. Далее следует N строк, каждая строка содержит ровно два слова-синонима. После этого следует одно слово.

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

Программа должна вывести синоним к данному слову.

Пример

№	Входные данные	Выходные данные
1	3 Hello Hi Bye Goodbye List Array Goodbye	Bye

Словари

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

Коровы - в стойла#30709

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

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

- в первой строке вводятся числа N ($2 < N < 10001$) – количество стойл, и K ($1 < K < N $) – количество коров;
- во второй строке задаются N натуральных чисел в порядке возрастания – координаты стойл (координаты не превосходят $10^9$).

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

Примеры

№	Входные данные	Выходные данные
1	6 3 2 5 7 11 15 20	9

Бинарный поиск по ответу

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

Защищенное соединение#30707

В свете недавних новостей о прослушке каналов связи, два непримиримых интернет-гиганта Урагании <<Laim.UR>> и <<Xenda>> решили подписать соглашение об установлении защищенного канала связи между дата-центрами друг друга. В Урагании $n$ городов, но, к сожалению, ни в одном городе нет дата-центров обоих гигантов. Поэтому для формирования защищенного канала придется прокладывать междугородние линии связи.

Специалисты компаний определили $m$ пар городов, которые можно соединить, проложив сегмент канала связи, и оценили стоимость создания такого сегмента для каждой из этих пар.

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

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

Формат входных данных
В первой строке находятся целые числа $n$ и $m$ ($2 \le n \le 5\,000$, $1 \le m \le 10^5$) — количество городов и количество пар городов, которые можно соединить сегментом канала связи.

Во второй строке находятся $n$ целых чисел $a_i$ ($0 \le a_i \le 2$). Если $a_i = 0$, то в $i$-м городе нет дата-центра ни одного из гигантов. Если $a_i = 1$, то в $i$-м городе есть дата-центр <<Laim.UR>>, а если $a_i = 2$, то в $i$-м городе находится дата-центр <<Xenda>>. Гарантируется, что среди этих чисел есть как минимум одна единица и одна двойка.

В каждой из следующих $m$ строк находится по три целых числа — $s_i$, $t_i$ и $c_i$, которые означают, что города $s_i$ и $t_i$ ($1 \le s_i, t_i \le n$, $s_i \ne t_i$) можно соединить сегментом канала связи стоимостью $c_i$ ($1 \le c_i \le 10^5$). Каждую пару городов можно соединить не более чем одним сегментом канала.

Формат выходных данных
Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: $x$, $y$ и $d$, означающие, что между городами $x$ и $y$ возможно провести канал связи суммарной стоимостью $d$. В городе $x$ должен находиться дата-центр <<Laim.UR>>, в городе $y$ — дата-центр <<Xenda>>. Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите $-1$.

В первом примере оптимально построить канал связи из двух сегментов: $3-2$ и $2-4$.

Алгоритм Дейкстры

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

Редактор скобочной последовательности#30705

Задана строка, состоящая только из:

• прописных и строчных букв английского алфавита;

• символов подчёркивания (они используются в качестве разделителей);

• круглых скобок (как открывающих, так и закрывающих).

Гарантируется, что каждая открывающая скобка имеет парную закрывающую, идущую следом. Аналогично, каждая закрывающая скобка имеет парную открывающую, которая расположена до неё. Для каждой пары соответствующих скобок верно, что между ними нет каких-либо других скобок. Иными словами, каждая скобка в строке входит в пару «открывающая-закрывающая», и такие пары не вкладываются друг в друга.

Например, допустимой строкой является: _Hello_Vasya(and_Petya)__bye_(and_OK)

Словом называется нерасширяемая последовательность подряд идущих букв, то есть последовательность букв, где слева и справа от неё находится скобка или символ подчёркивания, или соответствующий символ отсутствует.
Приведенный пример содержит семь слов: «Hello», «Vasya», «and», «Petya», «bye», «and» и «OK».

Напишите программу, которая найдет:

• длину самого длинного слова вне скобок (выведите 0, если слов вне скобок нет),

• количество слов внутри скобок (выведите 0, если слов внутри скобок нет).

Входные данные: в первой строке записано целое число n ($1 <= n <= 255$) — длина заданной строки. Во второй строке записана строка, состоящая только из строчных и прописных английских букв, открывающих и закрывающих скобок, а также символов подчёркивания.

Выходные данные: выведите два числа:

• длину самого длинного слова вне скобок (выведите 0, если слов вне скобок нет);

• количество слов внутри скобок (выведите 0, если слов внутри скобок нет).

Примеры

№	Входные данные	Выходные данные
1	37 _Hello_Vasya(and_Petya)__bye_(and_OK)	5 4
2	37 _a_(_b___c)__de_f(g_)__h__i(j_k_l)m__	2 6
3	27 (LoooonG)__shOrt__(LoooonG)	5 2
4	5 (___)	0 0

Примечание
В первом примере слова «Hello», «Vasya» и «bye» записаны вне скобок, а слова «and», «Petya», «and» и «OK» — внутри. Обратите внимание, что слово «and» встречается дважды, и учитывать в ответе его тоже следует два раза.

Строки

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

Замена подстроки#30704

Найти в строке указанную подстроку и заменить ее на новую. Строка s, ее подстрока s1 для замены и новая подстрока s2 вводятся.

P.S. Искомые подстроки в исходной строке не пересекаются.
P.P.S. В строках не содержатся пробелы.
P.P.P.S. Искомая подстрока может встречаться неоднократно.
P.P.P.P.S. Все буквы строчные.
P.P.P.P.P.S. Нет символов помимо строчных латинских букв.

На вход подаются 3 строки: s, s1, s2. Длина всех строк не превосходит 100.

Примеры

№	Входные данные	Выходные данные
1	abcde ab fg	fgcde
2	ababc ab c	ccc

Строки

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

Очень легкая задача#30703

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y.
Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии. Помогите ему выяснить, какое минимальное время для этого потребуется.

Входные данные: на входе задается три натуральных числа N, x и y, разделенные пробелом ($1 <= N <= 2 \cdot 10^8,\ 1 <= x, y <= 10$).

Выходные данные: выведите одно число – минимальное время в секундах, необходимое для получения N копий.

Примеры

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

Бинарный поиск по ответу

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

Заправки-2#30702

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

В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-й, потратив как можно меньшее денег.

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

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

В первой строке вводится число N (1<=N<=100), в следующей строке идет N чисел, i-е из которых задает стоимость бензина в i-м городе (всё это целые числа из диапазона от 0 до 100). Затем идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

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

Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.

Алгоритм Дейкстры

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

Спутник "Восход" -2#30698

На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи натуральное число – количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии количество пар таких показаний прибора, произведение которых кратно 6 и между моментами передачи которых прошло не менее трех минут. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.

Задача А (2 балла). Напишите, на любом языке программирования, программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего проверены все возможные пары элементов.

Задача Б (4 балла). Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Входные данные
В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что $N>3$. В каждой из следующих N строк задаётся одно натуральное число – очередное показание прибора.

Примеры

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

В приведённом наборе из 5 чисел имеются три пары (6, 3), (2, 3) и (6, 1), удовлетворяющих условию задачи.

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

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

Подсчет пар с суммой кратной 12#30697

Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (a_i, a_j) этого набора, в которых $1 < i < j < N$ и сумма элементов кратна 12.

Напишите эффективную по времени и памяти программу для решения этой задачи.

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

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

Примеры

№	Входные данные	Выходные данные
1	5 7 5 6 12 24	2

В приведённом наборе из 5 чисел имеются две пары (7, 5) и (12, 24), сумма элементов которых кратна 12.

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

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

Подсчет пар с произведением кратным 6#30696

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

Напишите эффективную по времени и памяти программу для решения этой задачи.

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

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

Примеры

№	Входные данные	Выходные данные
1	4 7 5 6 12	5

В приведённом наборе из 4 чисел имеются пять пар (7, 6), (5, 6), (7, 12), (5, 12), (6, 12), произведение элементов которых кратно 6.

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

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

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

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

Напишите эффективную программу, решающую поставленную задачу.

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

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

Примеры

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

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

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

НОД для пары чисел#30694

Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель.

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

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

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 100 килобайт.

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

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

Примеры

№	Входные данные	Выходные данные
1	6 1 3 5 15 6 9 5 4 3 3 36 40	3 1

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

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

Цифры в числах#30693

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

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

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

Выходные данные
Вывести цифры, встречающиеся в эти числах, в порядке неубывания частоты их появления.

Примеры

№	Входные данные	Выходные данные
1	3 456 20 3452	6 3 0 5 4 2

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

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