Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





А. Пазлы

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

Секунда

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

Мегабайт

Ввод

Стандартный ввод

Вывод

Стандартный вывод

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

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

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

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

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

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

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

Примеры

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

4 6
10 12 10 7 5 22

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

Примечание

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

A - Пазлы

В первую очередь, упорядочим числа 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 и выберем наименьшую возможную разницу. Таким образом, весь алгоритм выглядит следующим образом:

read(n, m, f[1..m])

sort(f[1..m])

best = INFINITY

for k = 1 to m-n

best = min(best, f[k+n-1] - f[k])

print best


 

A. Кефа и первые шаги

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

Секунды

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

Мегабайт

Ввод

Стандартный ввод

Вывод

Стандартный вывод

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

Помогите Кефе справиться с этой задачей!

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

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

Во второй строке заданы n целых чисел a1,  a2,  ...,  an (1 ≤ ai ≤ 109).

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

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

Примеры

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

6
2 2 1 3 4 1

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

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

3
2 2 9

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

Примечание

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

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

 

 


A - Кефа и первые шаги

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

Асимптотика — O(n).

 


 

A. Скука

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

Секунда

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

Мегабайт

Ввод

Стандартный ввод

Вывод

Стандартный вывод

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

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

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

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

В первой строке задано целое число n (1 ≤ n ≤ 105) — количество элементов последовательности. Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 105) — элементы последовательности.

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

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

Примеры

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

2
1 2

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

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

3
1 2 3

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

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

9
1 2 1 3 2 2 2 2 3

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

Примечание

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

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

 


A - Скука

Решения: 7407649, 7407655;

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

f(i) = max(f(i - 1), f(i - 2) + cnt[ii), 2 ≤ i ≤ n;

f(1) = cnt[1];

f(0) = 0;

Ответ будет содержаться в f(n).

Асимптотика — O(n).

 

 


 

A. Игра с переворачиванием

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

Секунда

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

Мегабайт

Ввод

Стандартный ввод

Вывод

Стандартный вывод

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

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

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

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

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

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

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

Примеры

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

5
1 0 0 1 0

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

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

4
1 0 0 1

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

Примечание

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

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

 


A - Flipping Game

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.

 

 


 

A. Разрежь ленточку

Секунда

Мегабайт

Ввод

Стандартный ввод

Вывод

Стандартный вывод

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

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

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

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

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

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

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

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

Примеры

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

5 5 3 2

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

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

7 5 5 2

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

Примечание

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

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

 

 


Problem 189A — Cut Ribbon

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.

 


 

A. Две подстроки

Секунды

Мегабайт

Ввод

Стандартный ввод

Вывод

Стандартный вывод

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

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

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

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

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

Примеры

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

ABA

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

NO

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

BACFAB

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

YES

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

AXBYBXA

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

NO

Примечание

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

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

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

 


A - Two Substrings

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

 


 

B. Илья и запросы

Секунды

Мегабайт

Ввод

Стандартный ввод

Вывод

Стандартный вывод

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

Даны строка 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 целых чисел — ответы на запросы в том порядке, в котором запросы заданы во входных данных.

Примеры

входные данные

......
4
3 4
2 3
1 6
2 6

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

1
1
5
4

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

#..###
5
1 3
5 6
1 5
3 6
3 4

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

1
1
2
2
0

 

B - Илья и запросы

Предпосчитаем такой масив Ai, что Ai = 1, если si = si + 1, иначе Ai = 0. Теперь не сложно заметить, что ответом на запрос будетSumA, l, r - 1. Данную функцию можно организовать множеством вариантов. Одним из, является дерево отрезков. Но так как запросы можно выполнять в оффлайн, то можно использовать массив частичных сумм. Пусть Sumi – это сумма всех Aj, (j ≤ i). Тогда, что бы найти сумму на отрезке (l, r - 1) – нужно Sumr - 1 - Suml - 1.

 

А. Пазлы

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

Секунда







Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

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

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

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





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


©2015- 2023 zdamsam.ru Размещенные материалы защищены законодательством РФ.