«Слушайте мою клятву и будьте свидетелями моего обета! Ночь собирается, и начинается мой дозор. Он не окончится до самой моей смерти. Я не возьму себе ни жены, ни земель, не буду отцом детям. Я не надену корону и не буду добиваться славы. Я буду жить и умру на своем посту. Я — меч во тьме. Я — дозорный на Стене. Я — щит, который охраняет царство людей. Я отдаю свою жизнь и честь Ночному Дозору в эту ночь и во все грядущие!» — Клятва Ночного дозора
С этого начинается дозор Джона Сноу. Ему возложена задача поддержки стюардов.
Сейчас у него имеется n стюардов, которым необходимо предоставить поддержку. Каждый стюард имеет собственную силу. Джон Сноу предпочитает поддерживать стюарда, если существует хотя бы один стюард с силой строго меньшей, чем его, и хотя бы один стюард с силой строго большей, чем у него.
Можете ли вы ответить, сколько стюардов будет поддерживать Джон Сноу?
Первая строка содержит единственное целое число n (1 ≤ n ≤ 105) — количество стюардов Джона Сноу.
Вторая строка содержит n целых чисел, разделенных пробелом, a1, a2, ..., an (0 ≤ ai ≤ 109), представляющих значения, назначенные стюардам.
Выведите единственное целое число — количесто стюардов, которым поможет Джон Сноу.
2
1 5
0
3
1 2 5
1
В первом тестовом примере Джон Сноу не может поддержать стюарда с силой 1, потому что нет стюарда с силой меньше, чем 1. Также он не может поддержать стюарда с силой 5, потому что нет стюарда с силой больше, чем 5.
Во втором тестовом примере Джон Сноу может поддержать стюарда с силой 2, потому что есть стюард с силой меньше, чем 2, и есть стюард с силой больше, чем 2.
Влад очень любит ходить в столовые. За свою жизнь он сделал это n раз. К сожалению, в последнее время он начал замечать, что его выбор не отличается разнообразием. Ему хочется это исправить, и поэтому он провёл следующее исследование.
Сначала Влад присвоил каждой столовой индивидуальный номер. Затем он выписал в ряд все номера столовых, в которых он был, в порядке посещения. Теперь он хочет найти такую столовую, что последний раз он в ней был раньше последних посещений всех остальных столовых. Иными словами, он хочет найти столовую, в которой не был дольше всего на текущий момент. Помогите ему в этом.
В первой строке находится одно целое число n (1 ≤ n ≤ 2·105) — количество выписанных Владом номеров столовых.
Во второй строке находятся n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 2·105) — номера столовых в порядке посещения Владом. Влад мог посетить одну и ту же столовую несколько раз. Обратите внимание, не обязательно, что столовые пронумерованы подряд.
Выведите одно число — номер столовой, в которой Влад не был как можно дольше.
5
1 3 2 1 2
3
6
2 1 2 2 4 1
2
Рассмотрим первый тест. В нём есть три столовые, причём последнее посещение столовых с номерами 1 и 2 состоялись после последнего посещения столовой с номером 3, поэтому эта столовая — искомая.
Во втором тесте также есть три столовые с номерами 1, 2 и 4. Столовые с номерами 1 и 4 были посещены после последнего посещения столовой с номером 2, поэтому ответ 2. Обратите внимание, что Влад мог пропустить некоторые номера в нумерации столовых.
Джон Смит знает, что его сын, Томас Смит, один из лучших учеников не только в его классе, а и во всей школе. После того, как все ученики школы сдали экзамены по английскому языку, немецкому языку, математики и истории, была сформирована таблица результатов.
В таблице результатов расположены $$$n$$$ учеников, каждый из которых имеет свой уникальный id (от $$$1$$$ до $$$n$$$). У Томаса id $$$1$$$. Каждый из учеников получил баллы по каждому из четырех предметов: английскому, немецкому, математики и истории. Ученики даны в порядке увеличения их id.
В таблице результатов ученики будут отсортированы по убыванию суммы их оценок. Это значит, что ученик с самой большой суммой балов займет первое место в таблице. Если два или более ученика имеют одинаковую сумму балов, то они будут отсортированы по увеличению их id.
Пожалуйста, помогите Джону понять, какое место займет его сын.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество учеников.
Каждая из следующих $$$n$$$ строк содержит четыре целых числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ и $$$d_i$$$ ($$$0\leq a_i, b_i, c_i, d_i\leq 100$$$) — оценки $$$i$$$-го ученика по английскому, немецкому, математики и истории. У $$$i$$$-го ученика номер id равен $$$i$$$.
Выведите место Томаса в таблице. У Томаса id равен $$$1$$$.
5
100 98 100 100
100 100 100 100
100 100 99 99
90 99 90 100
100 98 60 99
2
6
100 80 90 99
60 60 60 60
90 60 100 60
60 100 60 80
100 100 0 100
0 0 0 0
1
В первом примере ученики получили такие оценки: $$$398$$$, $$$400$$$, $$$398$$$, $$$379$$$ и $$$357$$$. Среди $$$5$$$-ти учеников Томас и третий ученик имеют вторую максимальную сумму, но поскольку Томас имеет меньший id, то он займет $$$2$$$-е место.
Во втором примере ученики получили такие оценки: $$$369$$$, $$$240$$$, $$$310$$$, $$$300$$$, $$$300$$$ и $$$0$$$. Среди $$$6$$$ учеников Томас имеет максимальную сумму, поэтому он займет $$$1$$$-е место.
Аркадий собирается полить свой единственный цветок. К сожалению, у него в наличии лишь очень неудобная система полива, разработанная для $$$n$$$ цветов, и потому имеющая вид трубы с $$$n$$$ отверстиями. Аркадий может использовать только воду, вытекающую из первого отверстия.
Аркадий может заткнуть некоторые отверстия, а затем он нальет $$$A$$$ литров воды в систему полива. После этого вода вытечет через все незаткнутые отверстия пропорционально их размерам $$$s_1, s_2, \ldots, s_n$$$. Другими словами, если сумма размеров незаткнутых отверстий равна $$$S$$$, и $$$i$$$-е отверстие не заткнуто, то из него вытечет $$$\frac{s_i \cdot A}{S}$$$ литров воды.
Какое минимальное число отверстий Аркадию необходимо заткнуть, чтобы из первого отверстия вытекло хотя бы $$$B$$$ литров воды?
Первая строка содержит три целых числа $$$n$$$, $$$A$$$, $$$B$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le B \le A \le 10^4$$$) — количество отверстий, объем воды, которые Аркадий зальет в систему, и объем, который должен вытечь из первого отверстия.
Вторая строка содержит $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^4$$$) — размеры отверстий.
Выведите одно целое число — количество отверстий, которые должен заткнуть Аркадий.
4 10 3
2 2 2 2
1
4 80 20
3 2 1 4
0
5 10 10
1000 1 1 1 1
4
В первом примере Аркадий должен заткнуть одно отверстие. После этого $$$\frac{10 \cdot 2}{6} \approx 3.333$$$ литров воды вытечет из первого отверстия, что достаточно Аркадию.
Во втором примере, даже если не затыкать отверстия, из первого отверстия вытечет $$$\frac{80 \cdot 3}{10} = 24$$$ литров воды, что не меньше необходимых $$$20$$$.
В третьем примере Аркадию нужно заткнуть все отверстия, кроме первого, чтобы вся вода вытекла из первого отверстия.
Дана строка $$$s$$$ длины $$$3$$$, состоящая из строчных и заглавных букв латинского алфавита. Ваша задача состоит в том, чтобы определить, равняется ли она строке «YES» (без кавычек), где каждая буква может быть как заглавной, так и строчной. Например, «yES», «Yes» и «yes» все являются допустимыми.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных. Далее следует описание каждого набора.
Единственная строка каждого набора входных данных содержит строку $$$s$$$ длины три. Каждый символ $$$s$$$ является строчной или заглавной буквой латинского алфавита.
Для каждого набора входных данных выведите «YES» (без кавычек) если $$$s$$$ удовлетворяет условию, и «NO» в противном случае.
Вы можете выводить «Yes» и «No» в любом регистре (например, строки «yES», «yes» и «Yes» будут распознаны как правильный ответ).
10YESyESyesYesYeSNooorZyEzYasXES
YES YES YES YES YES NO NO NO NO NO
Первые пять наборов входных данных содержат строки «YES», «yES», «yes», «Yes», «YeS». Все они равны строке «YES», где каждый символ либо заглавный, либо строчный.
Расшифровка генома берляндского мамонта подходит к концу!
Одна из немногих оставшихся задач — восстановление нераспознанных нуклеотидов в найденной цепочке s. Каждый нуклеотид кодируется прописной буквой латинского алфавита: 'A', 'C', 'G' или 'T'. Нераспознанный нуклеотид кодируется знаком вопроса '?'. Таким образом, s — это строка, состоящая из букв 'A', 'C', 'G', 'T' и символов '?'.
Известно, что в расшифрованном геноме берляндского мамонта количества нуклеотидов каждого из четырех видов равны между собой.
Требуется расшифровать геном и заменить каждый нераспознанный нуклеотид на один из четырёх так, чтобы количества нуклеотидов каждого из четырёх типов стали равны между собой.
В первой строке следует целое число n (4 ≤ n ≤ 255) — длина генома.
Во второй строке следует строка s длины n — описание генома, состоящее из символов 'A', 'C', 'G', 'T' и '?'.
Если расшифровать геном возможно, выведите его расшифровку. Если существует много вариантов расшифровки, то выведите любой из них. Если искомой замены не существует, то выведите три знака равно подряд «===» (без кавычек).
8
AG?C??CT
AGACGTCT
4
AGCT
AGCT
6
????G?
===
4
AA??
===
В первом примере можно заменить первый знак вопроса на букву 'A', второй знак вопроса на букву 'G', в третий — на букву 'T', тогда каждого нуклеотида в геноме будет по 2.
Во втором примере геном уже корректно расшифрован и каждого нуклеотида в нём ровно по одному.
В третьем и четвертом примерах корректно расшифровать геном невозможно.
Слово или предложение на некотором языке называется панграммой, если в нем встречаются все символы алфавита этого языка хотя бы один раз. Панграммы часто используют в типографии для демонстрации шрифтов или тестирования средств вывода различных устройств.
Вам дана строка, состоящая из маленьких и больших латинских букв. Проверьте, является ли эта строка панграммой. Считается, что строка содержит букву латинского алфавита, если эта буква встречается в верхнем или нижнем регистре.
В первой строке записано одно целое число n (1 ≤ n ≤ 100) — количество символов в строке.
Во второй строке записана сама строка. Строка содержит исключительно строчные и заглавные латинские буквы.
Выведите «YES», если строка является панграммой, и «NO» в противном случае.
12
toosmallword
NO
35
TheQuickBrownFoxJumpsOverTheLazyDog
YES
Амуга владеет отелем, представимым в виде длинного коридора с $$$10$$$ комнатами, идущими подряд. Комнаты пронумерованы цифрами от $$$0$$$ до $$$9$$$ слева направо.
В отель есть два входа: с левого конца коридора и с правого. Если гость заходит с левого конца коридора, то он будет расположен в ближайшей к левому входу свободной комнате. Аналогично, если гость заходит с правого конца коридора, то ему будет назначена ближайшая к правому входу свободная комната.
Однажды Амуга потерял документ с указанием статуса занятости комнат. К счастью, у него безупречная память, и он помнит всё о своих гостях: когда гость пришёл в отель, с какой стороны он вошёл, и когда он покинул отель. Изначально все комнаты в отеле были свободными. Напишите программу, которая восстановит статус занятости комнат по событиям из памяти Амуга.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество событий в памяти Амуга.
Вторая строка содержит строку длины $$$n$$$, описывающую события, которые помнит Амуга, заданные в хронологическом порядке. Символы заданной строки могут быть следующими:
Гарантируется, что в отеле имеется хотя бы одна свободная комната, когда появляется новый гость. Также гарантируется, что, если задано $$$x$$$ ($$$0$$$, $$$1$$$, ..., $$$9$$$), то в комнате $$$x$$$ находится гость. В начальный момент времени все комнаты свободны.
В единственной строке выведите статус занятости комнат, начиная с комнаты $$$0$$$ и заканчивая комнатой $$$9$$$. Свободную комнату обозначайте как «0», а занятую — как «1». Символы выводите без пробелов.
8 LLRL1RL1
1010000011
9 L0L0LLRR9
1100000010
В первом примере статус занятости комнат после каждого из событий следующий:
Таким образом, финальный статус занятости комнат следующий: 1010000011.
Во втором примере статус занятости комнат после каждого из событий следующий:
Таким образом, финальный статус занятости комнат следующий: 1100000010.