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

Counting Haybales#90366

Фермер Джон разместил свои \(N\) (\(1 \leq N \leq 100,000\)) стогов сена в различных точках одномерной дороги вдоль его фермы. Вам требуется ответить на \(Q\) (\(1 \leq Q \leq 100,000\)) запросов, о том сколько стогов сена находится внутри указанного участка дороги.

ФОРМАТ ВВОДА (файл haybales.in):

Первая строка содержит \(N\) и \(Q\).

Следующая строка содержит \(N\) различных целых чисел, каждое в интервале \(0 \ldots 1,000,000,000\), указывающих местоположения стогов сена.

Каждая из последующих \(Q\) строк содержит два целых числа \(A\) и \(B\) (\(0 \leq A \leq B \leq 1,000,000,000\)) задающих запрос на количество стогов сена между \(A\) и \(B\), включительно.

ФОРМАТ ВЫВОДА (файл haybales.out):

Вы должны вывести \(Q\) строк. Для каждого запроса выведите количество стогов сена в соответствующем интервале.

Бинарный поиск в массиве Использование сортировки

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

Cow Baseball#89861

N (3 <= N <= 1000) коров Фермера Джона стоят в ряд, каждая в различной позиции на числовой прямой. Они бросают друг другу мяч по кругу в порядке подготовки к важной игре с коровами с соседней фермы.
ФД заметил, что группа из 3 коров (X,Y,Z) делает два успешных броска. Корова X бросает мяч вправо от себя корове Y, а затем корова Y бросает Мяч вправо от себя корове Z. ФД заметил также, что второй бросок получается на расстояние не менее чем первый бросок и не более чем в два раза превышает первый бросок. Посчитайте количество возможных троек коров, которые ФД мог наблюдать.
PROBLEM NAME: baseball
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..1+N: Каждая строка содержит целую координату одной коровы (целое число в диапазоне 0..100,000,000).
Формат выходных данных
* Строка 1: Количество троек коров (X,Y,Z), где Y справа от X, а Z справа от Y и расстояние от Y до Z находится между XY и 2XY (включительно), где XY представляет расстояние от X до Y.
Примечание
Три возможных тройки: 1-3-7, 1-4-7, 1-4-10, 4-7-10.

Бинарный поиск в массиве Использование сортировки

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

Бинарный поиск в подмножестве#84682

У Васи есть набор чисел. Для каждого запроса нужно найти минимальное число из набора, которое больше или равно заданному X. Если такого числа нет, вывести -1.

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

В первой строке — число N (1 ≤ N ≤ 100000) — размер набора.

Во второй строке — N целых чисел (1 ≤ число ≤ 1000000).

В третьей строке — число Q (1 ≤ Q ≤ 100000) — количество запросов.

В следующих Q строках — по одному числу X (1 ≤ X ≤ 1000001).

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

Для каждого запроса выведите ответ на отдельной строке.

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

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

Контрольная по ударениям#56051

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

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

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

Входные данные
Вводится сначала число N — количество слов в словаре (0≤N≤100).

Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 30000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примечание
1) В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.
2) Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

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

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

Медиана объединений#56019

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

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

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

Медиана объединений#55404

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤200, 1≤L≤50000). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

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

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

Контрольная по ударениям#55400

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

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

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

Входные данные
Вводится сначала число N — количество слов в словаре (0≤N≤20000).

Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 300000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примечание
1) В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.
2) Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

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

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

Массивы#55203

Дано два массива. Для каждого элемента второго массива определите, сколько раз он встречается в первом массиве.

Входные данные
Первая строка входных данных содержит одно число N (1 ≤ N ≤ 10⁵) – количество элементов в первом массиве. Далее идет N целых чисел, не превосходящих по модулю 10⁹ – элементы первого массива, Далее идет количество элементов M во втором массиве и M элементов второго массива с такими же ограничениями.

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

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

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

Бинарный поиск в невозрастающем массиве - 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лёгкаяВойти и решать

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

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

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

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

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

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

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

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

Шлюзы#48931

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Недавно в Диваново построили огромную шлюзовую систему. Всего было построено \(n\) шлюзов, \(i\)-й из них имеет объем \(v_i\) литров. Изначально все шлюзы пусты. В каждый шлюз ведет труба, при открытии которой в шлюз будет поступать по \(1\) литру воды в секунду. Исходно все трубы закрыты.

Шлюзовая система устроена так, что если доливать воду в \(i\)-й шлюз сверх его объема, она будет моментально моментально переливаться в шлюз с номером \(i + 1\). Если шлюз c номером \(i + 1\) тоже заполнен, вода будет переливаться дальше. Вода из последнего шлюза будет выливаться в озеро.

Рисунок показывает \(5\) шлюзов с открытыми трубами к шлюзам \(1\) и \(3\). Так как шлюзы \(1\), \(3\) и \(4\) уже заполнены, фактически вода идет в шлюзы \(2\) и \(5\).

Для того, чтобы шлюзы начали функционировать, необходимо заполнить каждый из них. Мэра Дивановской области интересует \(q\) независимых запросов. Для каждого запроса предположим, что изначально все шлюзы пусты и все трубы закрыты, затем одновременно открываются несколько труб. Для \(j\)-го запроса мэр хочет знать, какое минимальное число труб надо включить, чтобы не позже чем через \(t_j\) секунд все шлюзы стали заполнены.

Помогите мэру справиться с этой сложной задачей и ответьте на все его запросы!

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \le n \le 200\,000\)) — количество шлюзов.

Во второй строке вводятся \(n\) целых чисел \(v_1, v_2, \dots, v_n\) (\(1 \le v_i \le 10^9\)) — объемы шлюзов.

В третьей строке вводится одно целое число \(q\) (\(1 \le q \le 200\,000\)) — число запросов.

В следующих \(q\) строках вводится по одному целому числу \(t_i\) (\(1 \le t_j \le 10^9\)) — время, за которое нужно наполнить все шлюзы в \(j\)-м запросе.

Формат выходных данных
Выведите \(q\) чисел, \(j\)-е из них должно быть равно минимальному числу труб, которое нужно открыть, чтобы наполнить все шлюзы за время \(t_j\). Если за это время наполнить всю шлюзы невозможно, выведите \(-1\).

В первом примере \(6\) запросов:

В запросах \(1, 3, 4\) ответ \(-1\). Чтобы заполнить первый шлюз нужно подождать \(4\) секунды, даже если открыты все трубы.

В шестом запросе можно открыть трубы в шлюзах \(1, 3\), и \(4\). Тогда через \(4\) секунды заполнятся шлюзы \(1\) и \(4\). Через \(1\) секунду \(1\) литр воды перельётся в шлюзы \(2\) и \(5\). Шлюз \(3\) будет заполнен своей трубой.

Аналогично во втором запросе можно открыть трубы в шлюзах \(1, 3\) и \(4\).

В пятом запросе можно открыть трубы в шлюзах с номерами \(1, 2, 3, 4\).

Бинарный поиск в массиве Вывод формулы Задача на реализацию

✓ 2✗ 41 100средняяВойти и решать

Первый, меньший данного#44935

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите минимальный номер элемента массива, меньший данного (нумерация элементов массива начинается с 1).

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

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

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

Для каждого из k запросов выведите минимальный номер элемента массива, меньше данного. Если таких нет, выведите 0.

Примеры

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

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

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

Последний элемент, не меньший данного - 2#44934

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, не меньше данного (нумерация элементов массива начинается с 1).

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

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

Для каждого из k запросов выведите максимальный номер элемента массива, не меньше данного. Если таких нет, выведите 0.

Примеры

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

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

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

Последний элемент > x#44931

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

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

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

Для каждого из k запросов выведите максимальный номер элемента массива, большего данного. Если таких нет, выведите 0.

Примеры

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

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

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

Последний элемент, меньший данного#44915

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

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

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

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

Для каждого из k запросов выведите максимальный номер элемента массива, меньший данного. Если таких нет, выведите 0.

Примеры

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

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

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