Мисис 2023 осень - массивы, строки
A. Клятва Ночного дозора
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

«Слушайте мою клятву и будьте свидетелями моего обета! Ночь собирается, и начинается мой дозор. Он не окончится до самой моей смерти. Я не возьму себе ни жены, ни земель, не буду отцом детям. Я не надену корону и не буду добиваться славы. Я буду жить и умру на своем посту. Я — меч во тьме. Я — дозорный на Стене. Я — щит, который охраняет царство людей. Я отдаю свою жизнь и честь Ночному Дозору в эту ночь и во все грядущие!» — Клятва Ночного дозора

С этого начинается дозор Джона Сноу. Ему возложена задача поддержки стюардов.

Сейчас у него имеется 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.

B. Влад и столовые
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Влад очень любит ходить в столовые. За свою жизнь он сделал это 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. Обратите внимание, что Влад мог пропустить некоторые номера в нумерации столовых.

C. Место в таблице
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джон Смит знает, что его сын, Томас Смит, один из лучших учеников не только в его классе, а и во всей школе. После того, как все ученики школы сдали экзамены по английскому языку, немецкому языку, математики и истории, была сформирована таблица результатов.

В таблице результатов расположены $$$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$$$-е место.

D. Поливальная система
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

E. YES или YES?
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$ длины $$$3$$$, состоящая из строчных и заглавных букв латинского алфавита. Ваша задача состоит в том, чтобы определить, равняется ли она строке «YES» (без кавычек), где каждая буква может быть как заглавной, так и строчной. Например, «yES», «Yes» и «yes» все являются допустимыми.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных. Далее следует описание каждого набора.

Единственная строка каждого набора входных данных содержит строку $$$s$$$ длины три. Каждый символ $$$s$$$ является строчной или заглавной буквой латинского алфавита.

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

Для каждого набора входных данных выведите «YES» (без кавычек) если $$$s$$$ удовлетворяет условию, и «NO» в противном случае.

Вы можете выводить «Yes» и «No» в любом регистре (например, строки «yES», «yes» и «Yes» будут распознаны как правильный ответ).

Пример
Входные данные
10
YES
yES
yes
Yes
YeS
Noo
orZ
yEz
Yas
XES
Выходные данные
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
Примечание

Первые пять наборов входных данных содержат строки «YES», «yES», «yes», «Yes», «YeS». Все они равны строке «YES», где каждый символ либо заглавный, либо строчный.

F. Расшифровка генома мамонта
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Расшифровка генома берляндского мамонта подходит к концу!

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

Во втором примере геном уже корректно расшифрован и каждого нуклеотида в нём ровно по одному.

В третьем и четвертом примерах корректно расшифровать геном невозможно.

G. Панграмма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вам дана строка, состоящая из маленьких и больших латинских букв. Проверьте, является ли эта строка панграммой. Считается, что строка содержит букву латинского алфавита, если эта буква встречается в верхнем или нижнем регистре.

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

В первой строке записано одно целое число n (1 ≤ n ≤ 100) — количество символов в строке.

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

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

Выведите «YES», если строка является панграммой, и «NO» в противном случае.

Примеры
Входные данные
12
toosmallword
Выходные данные
NO
Входные данные
35
TheQuickBrownFoxJumpsOverTheLazyDog
Выходные данные
YES
H. Отельер
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Амуга владеет отелем, представимым в виде длинного коридора с $$$10$$$ комнатами, идущими подряд. Комнаты пронумерованы цифрами от $$$0$$$ до $$$9$$$ слева направо.

В отель есть два входа: с левого конца коридора и с правого. Если гость заходит с левого конца коридора, то он будет расположен в ближайшей к левому входу свободной комнате. Аналогично, если гость заходит с правого конца коридора, то ему будет назначена ближайшая к правому входу свободная комната.

Однажды Амуга потерял документ с указанием статуса занятости комнат. К счастью, у него безупречная память, и он помнит всё о своих гостях: когда гость пришёл в отель, с какой стороны он вошёл, и когда он покинул отель. Изначально все комнаты в отеле были свободными. Напишите программу, которая восстановит статус занятости комнат по событиям из памяти Амуга.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество событий в памяти Амуга.

Вторая строка содержит строку длины $$$n$$$, описывающую события, которые помнит Амуга, заданные в хронологическом порядке. Символы заданной строки могут быть следующими:

  • «L»: новый гость зашёл в отель с левого конца коридора.
  • «R»: новый гость зашёл в отель с правого конца коридора.
  • «0», «1», ..., «9»: гость из комнаты $$$x$$$ ($$$0$$$, $$$1$$$, ..., $$$9$$$ соответственно) покинул отель.

Гарантируется, что в отеле имеется хотя бы одна свободная комната, когда появляется новый гость. Также гарантируется, что, если задано $$$x$$$ ($$$0$$$, $$$1$$$, ..., $$$9$$$), то в комнате $$$x$$$ находится гость. В начальный момент времени все комнаты свободны.

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

В единственной строке выведите статус занятости комнат, начиная с комнаты $$$0$$$ и заканчивая комнатой $$$9$$$. Свободную комнату обозначайте как «0», а занятую — как «1». Символы выводите без пробелов.

Примеры
Входные данные
8
LLRL1RL1
Выходные данные
1010000011
Входные данные
9
L0L0LLRR9
Выходные данные
1100000010
Примечание

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

  • Изначально все комнаты свободны. Статус занятости: 0000000000.
  • L: гость заходит в отель через вход слева. Статус занятости: 1000000000.
  • L: ещё один гость заходит через вход слева. Статус занятости: 1100000000.
  • R: ещё один гость заходит через вход справа. Статус занятости: 1100000001.
  • L: ещё один гость заходит через вход слева. Статус занятости: 1110000001.
  • 1: гость из комнаты $$$1$$$ покидает отель. Статус занятости: 1010000001.
  • R: ещё один гость заходит через вход справа. Статус занятости: 1010000011.
  • L: ещё один гость заходит через вход слева. Статус занятости: 1110000011.
  • 1: гость из комнаты $$$1$$$ покидает отель. Статус занятости: 1010000011.

Таким образом, финальный статус занятости комнат следующий: 1010000011.

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

  • L: гость заходит в отель через вход слева. Статус занятости: 1000000000.
  • 0: гость из комнаты $$$0$$$ покидает отель. Статус занятости: 0000000000.
  • L: гость заходит в отель через вход слева. Статус занятости: 1000000000.
  • 0: гость из комнаты $$$0$$$ покидает отель. Статус занятости: 0000000000.
  • L: гость заходит в отель через вход слева. Статус занятости: 1000000000.
  • L: ещё один гость заходит через вход слева. Статус занятости: 1100000000.
  • R: ещё один гость заходит через вход справа. Статус занятости: 1100000001.
  • R: oещё один гость заходит через вход справа. Статус занятости: 1100000011.
  • 9: гость из комнаты $$$9$$$ покидает отель. Статус занятости: 1100000010.

Таким образом, финальный статус занятости комнат следующий: 1100000010.