Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





Мегабайт

Ввод

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

Вывод

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

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

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

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

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

В первой строке через пробел записаны целые числа n и m (2 ≤  n  ≤  m  ≤ 50). Во второй строке через пробел записано m целых чисел f 1,  f 2, ...,  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 целых чисел a 1,   a 2,  ...,   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 целых чисел a 1, a 2,..., 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 целых чисел a 1,  a 2, ...,  an. Каждое из этих целых чисел может быть равно 0 или 1. Ему разрешено выполнить ровно одно действие: выбрать два индекса i и j (1 ≤  i  ≤  j  ≤  n) и перевернуть все значения ak, позиции которых находятся на отрезке [ i,  j ] (то есть i  ≤  k  ≤  j). Перевернуть значение x, значит выполнить операцию x  = 1 - x.

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

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

В первой строке содержится целое число n (1 ≤  n  ≤ 100). Во второй строке записано n целых чисел: a 1,  a 2, ...,  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. Разрежь ленточку







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

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

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

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...





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


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