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

Несложная сортировка#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

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

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

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

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

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

Премия#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лёгкаяВойти и решать

По мотивам ЕГЭ 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

Словари

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

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

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

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

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

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

Примеры

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

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

✓ 614✗ 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лёгкаяВойти и решать