Алгоритмы

 

Примеры

№	Входные данные	Выходные данные
1	3 4 1 1 1 1 5 2 2 100 9 4 2 1	8

 

 

Примеры

№	Входные данные	Выходные данные
1	abab abababcab	2

Пояснение: подстрока abab встречается во второй строке дважды, начиная с 1-го и 3-го символа.

 

Примеры

№	Входные данные	Выходные данные
1	hgdfjgkdghkdjgkgkd1543gjdlgkdjlg	URA
2	1=5 4=3	NO

 

Примеры

№	Входные данные	Выходные данные
1	6 3 3 -5 7 4 9 6 1 4 1 2 2 3 1 5 3 5 2 5	2 1 1 2 2 2

В городе будущего Иннополис еще во всю идет стройка, но уже сейчас построено n зданий. Крышу каждого здания можно представить как прямоугольник со сторонами, параллельными осям координат. Никакие здания не касаются и не пересекаются.

Инна любит гулять по крышам. Она стоит на крыше здания с номером 1 и хочет попасть на крышу здания с номером n.

Инну можно представить как точку на плоскости. Она может перемещаться по крыше, не выходя за ее границы, но не может находиться на границе крыши. Также она умеет прыгать с крыши на крышу, но только в направлениях, параллельных осям координат. В целях безопасности Инна не может перепрыгивать здания, то есть в любой момент прыжка под ней не должно находиться здание.

Помогите Инне посчитать, какое минимальное количество раз она должна прыгнуть с одной крыши на другую, чтобы попасть на здание с номером n.

Формат входных данных
В первой строке задано натуральное число n — число зданий в Иннополисе (n<= 10⁵). В следующих n строках заданы крыши зданий. Каждая из этих строк содержит четыре целых числа x_i1, y_i1, x_i2 и y_i2 — координаты противоположных вершин прямоугольника, описывающего крышу здания (x_i1 < x_i2; y_i1 < y_i2) Гарантируется, что никакие два прямоугольника не имеют общих точек. Все координаты — неотрицательные целые числа и <= 10⁹

Формат выходных данных
Выведите одно целое число — минимальное количество прыжков, которые Инна должна совер- шить, чтобы добраться с крыши здания 1 до крыши здания n. Если же Инна не может добраться до крыши n-го здания, выведите -1.

Ввод	Вывод
4 0 0 3 2 1 6 4 8 1 3 4 5 7 7 10 9	3
3 0 0 3 2 1 3 4 5 7 7 10 9	-1

На занятиях по дискретной математике Сереже рассказали про двоичные коды Грея — это такое упорядочение всех 2ⁿ различных двоичных векторов длины n, что любые два соседних, а также первый и последний, вектора различаются ровно в одном разряде.

Для закрепления материала преподаватель задал им следующее задание: в коде Грея в каждом двоичном векторе ровно один бит заменен на знак вопроса «?». Требуется заменить обратно все знаки вопроса «?» на «0» или «1», чтобы получился код Грея.

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

Формат входных данных
В первой строке содержится целое число n — длина двоичных векторов. Следующие 2ⁿ строк содержат двоичные вектора длины n, в каждом из которых ровно один символ заменен на знак вопроса «?».
Формат выходных данных
В первой строке выведите «YES», если решение существует, и «NO» — в противном случае. В случае положительного ответа выведите исходный код Грея, если возможных вариантов ответа несколько, выведите любой.
 

Ввод	Вывод
2 0? 0? 1? 1?	YES 00 01 11 10
3 ?00 0?1 01? 0?0 ?10 1?1 10? 1?1	NO

Система оценки
 

Номер подзадачи	Баллы	Ограничения	Комментарии
1	37	1<=n<=4	Баллы начисляются, если все тесты пройдены.
2	63	1<=n<=12	Баллы начисляются, если все тесты этой и предыду- щих подзадач пройдены.

 

Университет Иннополис готовится к проведению Летней школы олимпиадного программирования. Сейчас им нужно выбрать даты проведения.

Организаторы заметили, что школа проходит лучше, если настроение детей с каждым днем школы улучшается, также они заметили, что настро- ение школьников сильно зависит от погоды: в ясную погоду школьники веселее, чем в пасмурную. Организаторы запросили прогноз погоды на n дней, в которые можно провести школу. Для каждого дня они посчитали число ai — солнечность i-го дня. Теперь они хотят выбрать для про- ведения школы некоторый непрерывный отрезок дней, такой, что каждый следующий день школы солнечность строго больше, чем в предыдущий.

Помогите организаторам школы найти максимальное число дней, которые может идти школа.

Формат входных данных
В первой строке входного файла задано число n — число дней, в которые можно провести школу. Во второй строке заданы n ( 1<=n<=10⁵) чисел ai — солнечности дней (0 <= a_i <= 10⁹ ).
Формат выходных данных
Выведите одно число: максимальное число дней, которое может идти школа так, чтобы каждый следующий день школы был солнечнее, чем предыдущий.
 

Вывод	Ввод
6 2 0 3 7 4 5	3
3 1 2 3	3
4 1 1 1 1	1

Ввод	Вывод
3 2 2 1	5
5 2 4 4	120
5 6 2 3 9 5 6 6	120

Ввод	Вывод
1	7
0	7
35	70

 

На отдыхе в Теплой Стране Вера познакомилась с симпатичным волейболистом- трактористом Петром. Турист Петр, кстати, собирается после отличного отдыха в Теплой Стране отправиться в путешествие по городам Европы. Как известно, Европа облада- ет развитой транспортной системой: в Европе есть V интересующих Петра городов и E маршрутов ночных поездов. Каждый маршрут соединяет два различных города, время в пути составляет одну ночь. Поезда по маршруту ходят в обоих направлениях.

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

Но на этом прагматичность Петра не заканчивается: Петр, как настоящий турист, хо- чет посмотреть на самые красивые европейские достопримечательности. Он долго изучал справочники и для каждого города оценил свою ожидаемую радость от его посещения pi. Теперь он хочет найти маршрут, при котором его радость будет наибольшей. Помогите Петру найти такой маршрут.

Формат входного файла
В первой строке входных данных заданы два целых числа V и E (1 <= V, E <= 3 · 10⁵ ) — количество городов и маршрутов поездов, соответственно. В следующей строке заданы V целых чисел p_i (1 <= p_i <= 10⁸ ), где pi обозначает ожидаемую радость от посещения го- рода с номером i. В следующих E строках заданы описания маршрутов поездов. Каждое описание состоит из пары различных чисел ai и bi (1 <= a_i, b_i <= V ) — номеров городов, меж- ду которыми курсирует этот маршрут поезда. Гарантируется, что между каждой парой городов существует не более одного маршрута поезда.

Формат выходного файла
В первой строке выходных данных выведите число K (1 <= K <= 4) — количество горо- дов в оптимальном маршруте туриста Петра. В следующей строке выведите номера этих городов в порядке посещения. Города нумеруются начиная с единицы. Если оптимальных маршрутов несколько, выведите любой из них.

Ввод	Вывод
5 4 4 2 3 1 5 1 2 2 3 3 4 4 5	4 2 3 4 5
4 3 1 2 3 4 1 2 1 3 1 4	3 4 1 3

Вера очень много работала в этом году, подавая своим коллегам пример настоящего труженика. На восьмое марта за прекрасное исполнение служебных обязанностей Вера получила подарок — долгожданный отпуск в Теплой Стране! Тяжелые трудовые будни закончились, и Вера уже нежится на пляже на берегу Теплого Моря.

Любимое хобби Веры — пляжный волейбол, и как же Вера ждала момента, когда она сможет испытать невероятный азарт этой игры! Вера уже познакомилась с несколькими симпатичными волейболистами, но она пока не решила, какая же команда достойна иметь в своем составе такого замечательного игрока.

Каждый из N капитанов команд мечтает заполучить Веру в состав своей команды, поэтому они хотят максимально проявить себя. Так как поиграть хотят все, они решили действовать следующим образом: все N команд выстроились в очередь. Первый матч иг- рается между двумя командами, которые стоят в очереди раньше остальных. Победитель игры остается на площадке, а проигравший отправляется в конец очереди. В каждом из следующих матчей победитель предыдущего играет с первой командой из очереди, а про- игравший в очередной встрече опять становится в конец очереди. Каждая команда имеет некоторую силу, причем для простоты будем предполагать, что силы всех команд различ- ны, а победителем в матче является команда, сила которой больше. Матчей может быть как угодно много.

Вера решила для себя, что она будет действовать по самому справедливому принципу «считалочки»: она будет играть с одной из двух команд, играющих матч с соответствую- щем считалке номером K. Но затем Вера поняла, что уже выбрала себе команду, в которой хотела бы играть, причем ориентируясь не только на ее силу. Ей известны Q считалок, соответствующих различным значениям K. Для каждого из этих чисел K_i необходимо узнать, а кто же именно будет сражаться за столь ценный приз, то есть какие две коман- ды будут играть в матче с номером K_i.

Формат входного файла
Первая строка входных данных содержит единственное целое число N — количество команд (2 <= N <= 100 000). Вторая строка содержит N различных чисел от 1 до N — силы команд: первое число — сила команды, стоящей в начале очереди, второе — сила следующей по очереди команды, ..., последнее — сила команды, стоящей в конце очереди. Третья строка содержит единственное целое число Q (1 <= Q <= 100 000) — коли- чество известных Вере считалок. Каждая из следующих Q строк содержит число Ki (1 <= K_i <= 10¹⁸) — номер очередного интересующего Веру матча. Обратите внимание, Ki может быть больше N. Формат выходного файла Выведите Q строк: для каждого интересующего Веру числа K_i два числа в любом порядке — силы команд, сыграющих на K_i-м шаге. Первая строка должна содержать ответ на первый запрос, вторая — на второй и так далее.

Примеры

Ввод	Вывод
4 1 3 2 4 1 3	3 4
4 2 1 4 3 3 1 5 2	2 1 4 2 2 4

Комментарии
Разберем первый тест из условия:

	Кто играет	Состояние очереди	Победитель	Проигравший
Матч № 1 Матч № 2 Матч № 3	1 3 3 2 3 4	2 4 4 1 1 2	3 3 4	1 2 3

Таким образом, в единственном интересующем Веру третьем матче сыграют команды с силами 4 и 3.

Весь год Гошан был прилежным мальчиком и делал добрые дела: переводил бабушку через дорогу, еженедельно оставался в школе на контесты, давал одноклассникам списать химию и т.д.  За это Дедушка Мороз позволил Гошану выбрать абсолютно любой подарок на новый год. Гошан воспользовался возможностью и попросил долгожданную для него книгу “History of Hip-Hop”, ведь он был истинным поклонником хип-хопа! За кем же еще может стоять андерграунд?

Но Дед Мороз решил устроить испытание для мальчика. Он поставил на коробку с книгой кодовый замок.
Кодовый замок устроен следующим образом. На электронном экране замка появляются три числа – a , b и c. Чтобы открыть замок необходимо перевести числа a и b в двоичную систему счисления и поразрядно выполнить для них операцию c.
Описание операций:

1	Конъюнкция
2	Дизъюнкция
3	Исключающее или
4	Импликация
5	Эквивалентность

Результат операции необходимо представить в виде числа в двоичной системе счисления, а затем перевести в десятичное число .
Это число и будет являться ключом числа.
Помогите Гошану открыть замок, ведь с логикой у него плохи дела, а ему очень хочется поскорее почитать “History of Hip-Hop”.
P.S. Если в одном из чисел a и b разрядов будет больше, чем в другом, то в наименьшее необходимо добавить ведущие нули.
Входные данные
Входной файл содержит в себе три числа – a,b(1<=a,b<=1000) и с(1<=c<=5).
Выходные данные
Необходимо вывести одно число – ответ на задачу.
Пример
Ввод:
12 10 5
Вывод:
9
Пояснение
12=1100
10=1010
 
1100
1001
 
1001=9

(с) Курбатов Егор 9и