Уже начался сезон олимпиад по программированию, а значит пора писать командные тренировки. Серёжа ведёт тренировки у своих команд не первый год и знает, что к туру надо подготовить не только набор задач и разбор. Тренировка длится несколько часов, и команды, которые в ней участвуют, успевают за это время проголодаться. Поэтому на каждую тренировку Серёжа закупает некоторое количество пицц, чтобы после окончания тура команды подкрепились и обсудили свои успехи и неудачи.
Командам предстоит написать n тренировок в течение n последовательных дней. Во время каждой тренировки на каждую команду, пришедшую в этот день, Серёжа заказывает по пицце в своей любимой пиццерии. Серёжа уже знает, что на i -ю тренировку придёт ровно a i команд.
В пиццерии проходят две акции. В рамках первой акции можно получить скидку, если купить две пиццы в один день. Вторая акция позволяет получить купон на покупку одной пиццы в день на протяжении двух последовательных дней.
Серёжины тренировки очень популярны, поэтому ему приходится часто делать заказы в этой пиццерии. Как их самый ценный клиент, он может неограниченно пользоваться указанными скидками и купонами в любых количествах в любые дни.
Серёжа хочет заказать все пиццы, пользуясь только скидками и купонами. При этом он не хочет приобретать ни в один из дней больше пицц, чем ему нужно в этот день. Помогите Серёже определить, может ли он закупить пиццу на все тренировки, пользуясь только купонами и скидками.
В первой строке находится целое число n ( 1 ≤ n ≤ 200 000 ) — количество тренировок.
Во второй строке находится n целых чисел a 1 , a 2 , ..., a n ( 0 ≤ a i ≤ 10 000 ), разделённых пробелами, — количества команд, которые придут на каждую из тренировок.
Если Серёжа может заказать все пиццы, используя только скидки и купоны и не покупая лишние пиццы ни в один из дней, выведите « YES » (без кавычек). Иначе выведите « NO » (без кавычек).
В первом примере Серёжа может воспользоваться одним купоном для покупки пицц в первый и второй день, одним купоном для покупки пицц во второй и третий день и одной скидкой в четвёртый день для покупки двух пицц. Это единственный возможный способ заказать все пиццы для данного теста.
Во втором примере Серёжа не может воспользоваться ни купоном, ни скидкой, не заказав при этом лишнюю пиццу. Обратите внимание, что в некоторые дни на тренировку может не прийти ни одной команды, как, например, во второй день в данном тесте.
4 1 2 1 2
YES
3 1 0 1
NO
Маленький Влад обожает играть в популярную игру Bota-2 на своем компьютере. На днях разработчики сообщили о выходе её продолжения под названием Bota-3. Разумеется, Влад тут же её приобрёл, но оказалось, что компьютер Влада слишком старый для этой игры, поэтому он отправился в магазин за обновлением для него.
В магазине Влад увидел n видеокарт, i -я из которых имеет свою мощность a i , выражаемую целым положительным числом. Для того, чтобы игра точно заработала, Влад решил купить не одну, а несколько видеокарт и объединить их мощности по новейшей технологии. Для использования этой технологии одна из видеокарт выбирается в качестве ведущей, а все остальные видеокарты подключаются к ней в качестве вторичных. Для корректной работы этой конструкции необходимо, чтобы мощность каждой видеокарты была кратна мощности ведущей видеокарты. Для обеспечения совместимости мощность каждой вторичной видеокарты может быть понижена до любого меньшего целого положительного значения. При этом мощность опорной видеокарты должна оставаться оригинальной, то есть не может быть уменьшена.
У Влада очень много денег, поэтому он может купить любые видеокарты. Помогите ему выбрать такие видеокарты, чтобы после необходимого понижения их мощностей и соединения их по новой технологии суммарная итоговая мощность видеокарт была максимальной.
В первой строке находится целое число n ( 1 ≤ n ≤ 200 000 ) — количество видеокарт в магазине.
Во второй строке находится n целых чисел a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 200 000 ), обозначающих мощности видеокарт.
В единственной строке выведите целое число — максимальную возможную суммарную итоговую мощность видеокарт.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи |
| 1 | 30 | \(N \le 100\) | тесты |
| 2 | 40 | \(N \le 1000\) | 1 |
| 3 | 30 | нет дополнительных ограничений | 2 |
В первом примере выгодно купить видеокарты с мощностями 3, 15 и 9. В таком случае можно выбрать видеокарту с мощностью 3 ведущей, а все остальные видеокарты будут с ней совместимы. Суммарная мощность в таком случае будет равна 3 + 15 + 9 = 27 . Если же купить все видеокарты и выбрать видеокарту с мощностью 2 ведущей, то мощности каждой из остальных трёх видеокарт придётся понизить на 1 , чтобы они стали кратны 2 , а значит итоговая мощность будет 2 + 2 + 14 + 8 = 26 , что менее выгодно. Обратите внимание, что не разрешается понижать мощность ведущей видеокарты, то есть получить сумму мощностей 3 + 1 + 15 + 9 = 28 нельзя.
Во втором примере выгодно купить все видеокарты, а в качестве ведущей выбрать видеокарту с мощностью 2. Видеокарта с мощностью 7 с ней несовместима, поэтому её мощность придется понизить до 6. Суммарная мощность будет равна 8 + 2 + 2 + 6 = 18 .
4 3 2 15 9
27
4 8 2 2 7
18
Арсений уже совсем взрослый и самостоятельный. Мама решила оставить его на m дней в одиночестве и уехать отдыхать в тёплые страны. Перед этим она наготовила ему много еды, оставила достаточное количество карманных денег и постирала всю одежду.
Однако за десять минут до отъезда в тёплые страны ей пришла в голову мысль, что Арсению надо оставить точную инструкцию, какую одежду надевать в какой из дней её отсутствия. Арсений живёт в очень необычной семье, в которой вся одежда пронумерована: например, n носков Арсения имеют различными целые номера от 1 до n . Поэтому всё, что потребовалось его маме, это указать для каждого дня два числа l i и r i — номера носков, которые надо надеть в i -й день на левую и правую ногу соответственно (разумеется, l i не совпадает с r i ). Каждый носок покрашен в один из k цветов.
Уже после отъезда матери Арсений заметил, что в некоторые дни в соответствии с инструкцией ему придётся надеть носки разных цветов, что, конечно, является досадной оплошностью, вызванной спешкой перед отъездом при составлении инструкции. Но Арсений находчивый мальчик, и, по счастливому совпадению, он нашёл у себя дома банки с красками всех k цветов, которые встречаются среди его носков.
Арсений собирается перекрасить некоторые носки таким образом, чтобы, следуя инструкции, оставленной его мамой, на протяжении каждого из m дней носить одноцветные носки. Арсений уже запланировал деловые встречи в каждый день отсутствия мамы, в течение которых у него не будет возможности заниматься перекраской носков, поэтому он должен определиться с цветами и провести всю работу именно сейчас.
Он хочет как можно быстрее расправиться с этой задачей, чтобы отправиться играть в недавно вышедшую суперпопулярную игру Bota-3, поэтому он просит вас помочь определить минимальное количество носков, которое ему придётся перекрасить, чтобы в каждый день надевать два одноцветных носка.
В первой строке находится три целых числа n , m и k ( 2 ≤ n ≤ 200 000 , 0 ≤ m ≤ 200 000 , 1 ≤ k ≤ 200 000 ) — количество носков, количество дней отсутствия мамы и количество доступных цветов соответственно.
Во второй строке находится n разделённых пробелами целых чисел c 1 , c 2 , ..., c n ( 1 ≤ c i ≤ k ) — цвета носков Арсения.
В каждой из последующих m строк находится по два целых числа l i , r i ( 1 ≤ l i , r i ≤ n , l i ≠ r i ) — номера носков, которые Арсений должен надеть в i -й день на левую и правую ногу соответственно.
Выведите единственное целое число — минимальное количество носков, которые Арсений должен перекрасить, чтобы не насмешить людей разноцветными носками ни в один из дней отсутствия мамы.
В первом примере Арсений может, например, перекрасить первый и третий носки во второй цвет.
Во втором примере ничего перекрашивать не придётся.
3 2 3 1 2 3 1 2 2 3
2
3 2 2 1 1 2 1 2 2 1
0
У Миши сегодня день рождения, и в честь этого события он решил погулять с друзьями. Поскольку день рождения Миши в морозный зимний день, дети отправились играть со снегом на поляне. Они уже заготовили n снежных шаров и были готовы лепить из них снеговиков, как вдруг Миша сообщил, что ему нравятся только красивые снеговики . В представлении Миши красивый снеговик — снеговик, состоящий из как минимум k снежных шаров, идущих в порядке невозрастания радиуса снизу вверх. Причём радиусы двух соседних шаров должны отличаться не менее чем на d сантиметров.
Поскольку дети больше не хотят катать новые снежные шары, им интересно узнать, какое максимальное число красивых снеговиков они смогут сделать из уже скатанных шаров. Помогите им решить эту задачу.
Первая строка содержит три целых числа n , k и d ( 1 ≤ k ≤ n ≤ 100 000 , 0 ≤ d ≤ 10 9 ) — количество снежных шаров, минимальное количество шаров в одном красивом снеговике и минимальную разность радиусов двух соседних шаров в красивом снеговике.
Вторая строка содержит n целых чисел r 1 , r 2 , ..., r n ( 1 ≤ r i ≤ 10 9 ) — радиусы имеющихся снежных шаров.
Выведите одно число — максимальное количество красивых снеговиков, которое можно слепить из данных снежных шаров.
В первом примере можно слепить только одного красивого снеговика, состоящего из шаров радиусами 13 и 5 .
Во втором примере можно слепить много различных пар красивых снеговиков, например из шаров радиусами 11 , 5 и 6 , 1 или 11 , 2 и 6 , 1 . Способа слепить трех красивых снеговиков нет.
В третьем примере можно лепить любых снеговиков, поскольку d = 0 , например 8 , 7 , 6 , 3 или 3 , 3 , 1 . Но оптимальным распределением шаров по снеговикам будет распределение, в котором каждый шар является отдельным снеговиком.
В четвертом примере нельзя слепить ни одного красивого снеговика.
3 2 6 5 10 13
1
7 2 5 1 6 3 4 2 11 5
2
8 1 0 1 3 3 3 5 8 7 6
8
2 2 100 1 1
0
Винни-Пух отправился в очередную Экспедицию по Лесу!
Лес представляет собой n полянок, соединённых m двусторонними тропинками. При этом возможно, что для некоторых полянок не существует способа добраться из одной в другую по тропинкам. За половину суток (день или ночь) Пух проходит ровно по одной тропинке.
Когда Пух пришёл на рассвете на очередную полянку, ему показалось, что он вернулся к полянке, с которой он начал свое путешествие. Он также уверен, что не проходил ни по одной тропинке дважды, и что все полянки до этого были различными. Также он помнит, что он отправился в Экспедицию на рассвете, то есть число дней в пути было равно числу ночей.
Вы решили помочь медвежонку и хотите определить по карте Леса, могло ли такое случиться.
Первая строка содержит число T — число наборов входных данных, которые вам предстоит обработать. Далее следуют T наборов входных данных. Каждый набор задаётся в следующем формате.
В первой строке набора входных данных заданы два числа n и m ( 2 ≤ n ≤ 500 000 , 1 ≤ m ≤ 500 000 ) — количество полянок и количество тропинок в соответствующем Лесу.
В следующих m строках содержатся описания тропинок: каждая строка состоит из двух целых чисел u i , v i ( 1 ≤ u i , v i ≤ n , u i ≠ v i ), обозначающих номера полянок, соединённых очередной тропинкой.
Гарантируется, что никакие две полянки не соединены двумя или более тропинками.
Гарантируется, что и суммарное число полянок, и суммарное число тропинок по всем наборам входных данных не превзойдёт 500 000 .
Для каждого набора входных данных выведите в отдельной строке " YES ", если в Лесу существует маршрут, удовлетворяющий описанию Пуха, и " NO " в противном случае.
Тест из условия состоит из двух наборов входных данных.
В первом примере Пух мог начать Экспедицию на полянке с номером 2 , в первый день перейти на полянку 5 , в первую ночь перейти на полянку 3 , во второй день перейти на полянку 4 и во вторую ночь вернуться обратно на полянку 2 .
Во втором примере, независимо от выбора начальной полянки, Пух может вернуться на неё, но ему в любом случае потребуется три перехода, а значит дней в пути будет больше, чем ночей.
2 5 6 1 2 2 3 3 4 4 5 5 2 5 3 3 3 1 2 2 3 3 1
YES NO