Ограничение по времени на тест

Учебный год подходит к концу, и классной руководительнице Манане Тариеловне скоро придется прощаться с очередным классом. На прощанье учительница решила подарить каждому из своих n учеников «пазл» (согласно wikipedia, пазл — игра-головоломка, в которой требуется составить мозаику из множества фрагментов рисунка различной формы).

В магазине учительнице сказали, что у них есть m пазлов, но они возможно не все одинаковой сложности и размера. Конкретно, первый пазл состоял из f ₁ фрагментов, второй — из f ₂, и так далее.

Манана Тариеловна решила, что разница между количествами фрагментов в подаренных ею пазлах должна быть как можно меньше, иначе дети могут обидеться. Поэтому она хочет выбрать такие n пазлов, что если A — это количество фрагментов в самом большом, а B — количество фрагментов в самом маленьком из них, то A - B должно быть минимальным возможным. Помогите учительнице и найдите наименьшую возможную разницу A - B.

В первой строке через пробел записаны целые числа n и m (2 ≤ n ≤ m ≤ 50). Во второй строке через пробел записано m целых чисел f ₁, f ₂, ..., f_m (4 ≤ f_i ≤ 1000) — количества фрагментов в пазлах, продающихся в магазине.

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

Пример 1. В классе всего 4 ученика. В магазине продается 6 пазлов. Если Манана Тариеловна купит первые четыре пазла, которые состоят из 10, 12, 10 и 7 фрагментов соответственно, тогда разница между самым большим и самым маленьким будет равна 5-ти. Меньшую разницу получить невозможно. Заметим, что учительница может купить пазлы 1, 3, 4 и 5 и также получить разницу 5.

В первую очередь, упорядочим числа f[i] по возрастанию. Теперь допустим, что самый маленький пазл, который приобретет учительница, состоит из f[k] фрагментов. Понятно, что в таком случае для минимизации разницы она должна приобрести наименьшие n пазлов, равных или превосходящих f[k] по размеру, то есть пазлы размеров f[k], f[k+1],..., f[k+n-1] (это не совсем правильно, если среди f[i] встречаются повторяющиеся числа и выполняется f[k]=f[k-1], но такие случаи можно не рассматривать). Разница между наибольшим и наименьшим количествами фрагментов в таком наборе равняется f[k+n-1]-f[k].

Чтобы выбрать оптимальное f[k], переберем значение k от 1 до m-n и выберем наименьшую возможную разницу. Таким образом, весь алгоритм выглядит следующим образом:

Кефа решил подзаработать денег, занимаясь различной деятельностью в интернете на протяжении ровно n дней. Он знает, что в i -й день (1 ≤ i ≤ n) он заработает a_i монет. Кефа любит прогресс, поэтому он хочет узнать длину максимального неубывающего подотрезка в последовательности a_i. Напомним, что подотрезок последовательности — это её непрерывный фрагмент. Подотрезок чисел называется неубывающим, если числа в нём следуют в порядке неубывания.

В первой строке содержится целое число n (1 ≤ n ≤ 10⁵).

Во второй строке заданы n целых чисел a ₁, a ₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Выведите единственное целое число — длину максимального неубывающего подотрезка последовательности a.

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

Во втором тесте максимальный неубывающий подотрезок это числа с первого по третье.

Заметим, что если в массиве есть две пересекающиеся непрерывные неубывающие подпоследовательности, то их можно объединить в одну. Поэтому можно просто проходиться по массиву слева направо. Если текущую подпоследовательность можно продолжить с помощью i -го элемента, то делаем это, иначе начинаем новую. Ответом будет максимальная из всех найденных подпоследовательностей.

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

Задана последовательность a, состоящая из n целых чисел. Игрок может сделать несколько ходов. За один ход игрок может выбрать некоторый элемент последовательности (обозначим выбранный элемент a_k) и удалить его, при этом из последователости также удаляются все элементы, равные a_k + 1 и a_k - 1. Описанный ход приносит игроку a_k очков.

Леша максималист и поэтому хочет набрать как можно больше очков. Какое максимальное количество очков он сможет набрать?

В первой строке задано целое число n (1 ≤ n ≤ 10⁵) — количество элементов последовательности. Во второй строке записаны n целых чисел a ₁, a ₂,..., a_n (1 ≤ a_i ≤ 10⁵) — элементы последовательности.

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

Рассмотрим третий тестовый пример. В этом тестовом примере нужно действовать так.

Первоначально нужно выбрать любой элемент, равный 2. Тогда последовательность станет равна [2, 2, 2, 2]. Далее, делаем еще 4 хода, на каждом ходу выбираем любой элемент, равный 2. Итого мы заработали 10 очков.

В этой задаче вам надо было максимизировать сумму набранных очков. Давайте подсчитаем количество всех чисел в массиве a, то есть заведем массив cnt, где cnt [ x ] — количество чисел x в массиве a. Теперь очень просто считать ДП. Оно имеет такой вид:

Яхубу стало скучно и он придумал игру, в которую надо играть на бумаге.

Яхуб выписывает n целых чисел a ₁, a ₂, ..., a_n. Каждое из этих целых чисел может быть равно 0 или 1. Ему разрешено выполнить ровно одно действие: выбрать два индекса i и j (1 ≤ i ≤ j ≤ n) и перевернуть все значения a_k, позиции которых находятся на отрезке [ i, j ] (то есть i ≤ k ≤ j). Перевернуть значение x, значит выполнить операцию x = 1 - x.

Цель игры — получить максимальное количество единиц после ровно одного хода. Напишите программу, которая решает маленькую игру Яхуба.

В первой строке содержится целое число n (1 ≤ n ≤ 100). Во второй строке записано n целых чисел: a ₁, a ₂, ..., a_n. Гарантируется, что каждое из этих n чисел равняется либо 0, либо 1.

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

В первом случае надо перевернуть отрезок от 2 до 5 (i = 2, j = 5). Такой переворот превращает последовательность в: [1 1 1 0 1]. Итого, в ней теперь четыре единицы. Мы никак не сможем превратить последовательность в [1 1 1 1 1].

Во втором случае, если мы перевернем только второй и третий элементы (i = 2, j = 3), все числа будут равны 1.

I’ll present here the O(N ^ 3) algorithm, which is enough to solve this task. Then, for those interested, I’ll show a method to achieve O(N) complexity.

O(N ^ 3) method: The first thing to observe is that constrains are slow enough to allow a brute force algorithm. Using brute force, I can calculate for each possible single move the number of 1s resulting after applying it and take maximum. For consider each move, I can just generate with 2 FOR loops all indices i, j such as i <= j. So far we have O(N ^ 2) complexity. Suppose I have now 2 fixed vaIues i and j. I need to calculate variable cnt (initially 0) representing the number of ones if I do the move. For do this, I choose another indice k to go in a[] array (taking O(N) time, making the total of O(N ^ 3) complexity). We have two cases: either k is in range [i, j] (this means i <= k AND k <= j) or not (if that condition is not met). If it’s in range, then it gets flipped, so we add to count variable 1 – a[k] (observe that it makes 0 to 1 and 1 to 0). If it’s not in range, we simply add to cnt variable a[k]. The answer is maximum of all cnt obtained.

O(N) method: For achieve this complexity, we need to make an observation. Suppose I flip an interval (it does not matter what interval, it can be any interval). Also suppose that S is the number of ones before flipiing it. What happens? Every time I flip a 0 value, S increases by 1 (I get a new 1 value). Every time I flip a 1 value, S decreases by 1 (I loose a 1 value). What would be the “gain” from a flip? I consider winning “+1” when I get a 0 value and “-1” when I get a 1 value. The “gain” would be simply a sum of +1 and -1. This gives us idea to make another vector b[]. B[i] is 1 if A[i] is 0 and B[i] is -1 if A[i] is 1. We want to maximize S + gain_after_one_move sum. As S is constant, I want to maximize gain_after_one_move. In other words, I want to find a subsequence in b[] which gives the maximal sum. If I flip it, I get maximal number of 1s too. This can be founded trivially in O(N ^ 2). How to get O(N)? A relative experienced programmer in dynamic programming will immediately recognize it as a classical problem “subsequence of maximal sum”. If you never heard about it, come back to this approach after you learn it.

У Поликарпа есть ленточка длины n. Он хочет разрезать ее так, чтобы выполнялись два условия:

· После разрезания, каждый кусочек ленточки должен быть длины a, b или c.

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

Помогите Поликарпу, найдите количество кусочков ленточки после требуемого разрезания.

В первой строке записано через пробел четыре целых числа n, a, b и c (1 ≤ n, a, b, c ≤ 4000) — длина исходной ленточки и разрешенные длины кусочков ленточки после разрезания, соответственно. Числа a, b и c могут совпадать.

Выведите одно число — максимально возможное количество кусочков ленточки. Гарантируется, что существует хотя бы одно корректное разрезание ленточки.

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

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

The problem is to maximize x+y+z subject to ax+by+cz=n. Constraints are low, so simply iterate over two variables (say x and y) and find the third variable (if any) from the second equation. Find the maximum over all feasible solutions.

Other approaches: Use dynamic programming with each state being the remainder of ribbon. Select the next piece to be a, b or c.

Дана строка s. Требуется определить, существуют ли в данной строке s две непересекающиеся подстроки "AB" и "BA" (подстроки могут идти в любом порядке).

На вход подаётся строка s длиной от 1 до 10⁵ символов, состоящая из заглавных букв латинского алфавита.

Выведите "YES" (без кавычек), если строка s содержит две непересекающиеся подстроки "AB" и "BA", и "NO" иначе.

В первом примере входных данных, несмотря на то, что есть подстроки "AB" и "BA", их вхождения пересекаются, поэтому ответ — "NO".

Во втором примере входных данных есть следующие вхождения подстрок: BA CF AB.

В третьем примере нет ни подстроки "AB", ни подстроки "BA".

Задачу можно решать разными способами. Авторское решение такое: проверим две возможности — когда подстрока "AB" идет первее "BA" и наоборот. Проверять можно следующим образом: найти самое первое вхождение "AB" в исходной строке и рассмотреть подстроки длины 2 правее. Если среди них встретилась подстрока "BA" — ответ "YES". Аналогично проверяется второй случай. Если оба варианта не выполнены, ответ "NO". Сложность решения — O (n), где n — длина исходной строки.

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

Даны строка s = s1s2... sn (n — длина строки), состоящая только из символов «.» и «#», и m запросов. Каждый запрос описывается парой целых чисел li, ri (1 ≤ li < ri ≤ n). Ответ на запрос li, ri — это количество таких целых чисел i (li ≤ i < ri), чтоsi = si + 1.

Лев Илья хочет помочь друзьям, но кто же поможет ему. Помогите Льву Илье, решите задачу.

В первой строке записана строка s длины n (2 ≤ n ≤ 105). Гарантируется, что заданная строка состоит только из символов «.» и «#».

В следующей строке записано целое число m (1 ≤ m ≤ 105) — количество запросов. В каждой из следующих m строк записано описание соответствующего запроса. В i-той строке записаны целые числа li, ri (1 ≤ li < ri ≤ n).

Выведите m целых чисел — ответы на запросы в том порядке, в котором запросы заданы во входных данных.

Предпосчитаем такой масив A_i, что A_i = 1, если s_i = s_i _+ 1, иначе A_i = 0. Теперь не сложно заметить, что ответом на запрос будет Sum_A _{, l, r - 1}. Данную функцию можно организовать множеством вариантов. Одним из, является дерево отрезков. Но так как запросы можно выполнять в оффлайн, то можно использовать массив частичных сумм. Пусть Sum_i – это сумма всех A_j, (j ≤ i). Тогда, что бы найти сумму на отрезке (l, r - 1) – нужно Sum_r _- 1 - Sum_l _- 1.

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: