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

Плагиат кода#49855

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

Компания пишет на эзотерическом языке программирования, похожем на Malbolge, поэтому код каждого из сотрудников представляет из себя строчку из маленьких латинских букв. Код Алисы — строка \(t\), а код Боба — строка \(s\).

Поскольку клавиатура Боба сломана, он может печатать ровно два символа за раз, то есть может вставлять в любое место строки два любых (не обязательно одинаковых) символа. После заявления Алисы о подозрении Боба в плагиате их начальник начал анализировать строки \(s\) и \(t\), пытаясь понять, мог ли Боб получить строку \(s\) из строки \(t\) со своей сломанной клавиатурой. Для этого он пытается постепенно удалять из строки \(s\) по два соседних символа, пока не получит в итоге строrку \(t\).

Помогите выяснить, виноват ли Боб в плагиате: определите, можно ли получить строку \(t\) из строки \(s\), вырезая из нее произвольное количество раз по два стоящих рядом символа.

Входные данные
В первой строке дана строка \(s\), состоящая из маленьких латинских букв от ‘a’ до ‘z’ (\(1 \le |s| \le 2 \cdot 10^5\)).

Во второй строке дана строка \(t\), также состоящая из маленьких латинских букв (\(1 \le |t| \le |s|\)).

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

В качестве ответа выведите <<YES>>, если из \(s\) можно получить \(t\) удалениями двух символов подряд, и <<NO>> в противном случае.

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

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

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

Двоичный поиск для монотонной функции (Python)#49750

Дано натуральное число x. Вычислите кубический корень из числа.

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

Число x – натуральное, не превосходящее \(10^6\).

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

Программа должна вывести единственное число: ответ на задачу с точностью не менее 6 знаков после запятой.

Примеры

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

Бинарный поиск значения функции

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

Тайлер украшает площадь#49743

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

Формат входных данных
В первой строке вводится натуральное число n (1 ≤ n ≤ 2·10⁵)- количество коробок, выданных Тайлеру. Во второй строке записаны n чисел a_i (1 ≤ a_i ≤ 10⁹)- количество плиток в i-й коробке.

Формат выходных данных
Выведите YES, если Тайлер сможет из всех плиток замостить квадрат какого-либо размера на площади, в противном случае выведите NO.

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

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

Сортировка по сумме элементов в столбце - 1#49711

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

Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

Формат выходных данных
Программа должна вывести получившуюся матрицу.

Алгоритмы сортировки

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

Сортировка по максимальному элементу в строке - 2#49710

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

Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

Формат выходных данных
Программа должна вывести получившуюся матрицу.

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

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

Сортировка по сумме строк#49709

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

Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

Формат выходных данных
Программа должна вывести получившуюся матрицу.

Алгоритмы сортировки

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

Сортировка по сумме строк - 2#49708

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

Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

Формат выходных данных
Программа должна вывести получившуюся матрицу.

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

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

Число пар районов#49685

В Сильвертауне есть N районов, пронумерованных от 1 до N, и M дорог, пронумерованных от 1 до M. Дорога i ведет из района A_i в район B_i, но вы не можете воспользоваться ею, чтобы попасть из района B_i в район A_i.
Максимус планирует прогулки по районам города. Он начинает в некотором районе, проходит по нулю или более дорог и заканчивает в некотором районе.
Сколько пар районов могут быть отправной и конечной точкой прогулки Максимуса?
Мы различаем пары с одинаковым набором районов, расположенных в разном порядке.

Формат входных данных
Первая строка содержит два целых числа N и M. Далее идет M строк, в каждой из которых записано по 2 числа: A_i и B_i.

Ограничения

2 ≤ N ≤ 2000
0 ≤ M ≤ min(2000, N*(N-1)
1 ≤ Ai, Bi ≤ N
Ai не равно Bi.
Пары (Ai,Bi) уникальны.
Все значения во входных данных целые числа.

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

Примечание
В первом тестовом примере есть семь пар районов, которые могут быть отправной точкой и пунктом назначения (1,1),(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)

Обход в глубину

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

Количество кратчайших путей#49684

В Сильвертауне есть N районов с номерами от 1 до N и M дорог с номерами от 1 до M. Используя дорогу i, вы можете добраться из района A_i в район B_i или наоборот за один час.
Сколько существует путей, по которым можно добраться из района 1 в район N как можно быстрее?
Поскольку число может быть огромным, выведите его по модулю 10⁹+7

Формат входных данных
Первая строка содержит два целых числа N и M. Далее идет M строк, в каждой из которых записано по 2 числа: A_i и B_i.

Ограничения

2 ≤ N ≤ 2×10⁵
0 ≤ M ≤ 2×10⁵
1 ≤ Ai < Bi ≤ N
Пары (Ai,Bi) уникальны.
Все значения во входных данных целые числа.

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

Обход в ширину

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

Открыть все комнаты#49671

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

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

По известному набору заклинаний, определите сможет ли Максимум получить все артефакты или нет.

Формат входных данных
В первой строке записано число n (2 <= n <= 1000), количество комнат. Далее идет n строк. В i-й строке описываются заклинания, хранящиеся в этой комнате. В каждой из этих строк первое число (m, 0 <= m <= 1000) обозначает количество уникальных заклинаний, которые открывают комнаты, далее записаны m уникальных чисел rooms[i](0 <= rooms[i][j] < n) - номера комнат, которые открывают эти заклинания (0<=i<n, 1 <= общее количество заклинаний во всех комнатах <= 10000).

Формат выходных данных
Выведите True, если Максимус может посетить все комнаты и найти все магические артефакты, или False в противном случае.

Обход в ширину

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

Лестница#49636

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

Решите задачу двоичным поиском.

Формат входных данных
Программа получает на вход натуральное число n (1 <= n <= 2³¹ - 1) - количество блоков.

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

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

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

Перевод из 10 сс в двоичную сс#49564

Переведите {1} из десятичной системы счисления в двоичную систему счисления.

Двоичная система счисления

—Войти и решать

Полный квадрат#49542

Для заданного целого положительного числа num, выведите 1, если num является полным квадратом, или 0 в противном случае.
Полный квадрат - это целое число, которое является квадратом целого числа. Другими словами, это произведение некоторого целого числа на само себя.

Решите задачу с помощью бинарного поиска.

Формат входных данных
Программа получает на вход одно целое положительное число num (1 <= num <= 2³¹ - 1).

Формат выходных данных
Выведите 1, если num является полным квадратом, или 0 в противном случае

Бинарный поиск значения функции

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

Бинарный (двоичный) поиск по ответу (C++)#49462

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

Вы уже выпустили n версий [1, 2, ..., n] и забыли проверить на качество все, кроме последней. Теперь, вы хотите найти первую плохую версию, которая приводит к тому, что все последующие становятся плохими.

Руководитель отдела качества очень хорошо к вам относится и написал для вас функцию isBadVersion(version), которая определяет является ли версия резила плохой (возвращает True, если версия плохая, и False если хорошая).

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

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

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

Бинарный (двоичный) поиск по ответу (Python)#49461

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

Вы уже выпустили n версий [1, 2, ..., n] и забыли проверить на качество все, кроме последней. Теперь, вы хотите найти первую плохую версию, которая приводит к тому, что все последующие становятся плохими.

Руководитель отдела качества очень хорошо к вам относится и написал для вас функцию isBadVersion(version), которая определяет является ли версия релиза плохой (возвращает True, если версия плохая, и False если хорошая).

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

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

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

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

Бинарный поиск в невозрастающем массиве - 6#49457

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.

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

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

Бинарный поиск в невозрастающем массиве - 5#49456

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

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

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

Бинарный поиск в невозрастающем массиве - 4.2#49455

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

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

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

Бинарный поиск в невозрастающем массиве - 4.1#49454

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

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

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

Бинарный поиск в невозрастающем массиве - 3#49453

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс последнего элемента равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.

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

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