Задача A. Полоса препятствий

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Одно из заданий на соревнованиях по подводной робототехнике — полоса препятствий. Полоса состоит из n подряд идущих стен, высота i-й стены hi.

Цель робота — преодолеть все стены, достать флаг, который находится в конце полосы за всеми стенами, и вернуться обратно. Стену можно преодолеть двумя способами: подняться, проплыть над ней и опуститься обратно или сделать подкоп. Если стена была преодолена с помощью подкопа, то в при проходе в обратную сторону можно воспользоваться уже готовым подкопом. Всего разрешается сделать не более m подкопов.

Робот имеет ограниченный заряд батареи. Изначально он способен подняться над стеной высотой k или меньше, далее после каждого подъёма максимальная высота стены, которую может преодолеть робот, снижается на 1.

Робот поддерживает две команды: D — идти через подкоп (если подкопа ещё нет, то робот выкапывает его), U — проплыть над препятствием.

Формат входного файла

Первая строка входного файла содержит целые числа n m k. Следующая строка содержат n целых чисел hi - высоты стен.

Формат выходного файла

Выходной файл должен содержать строку NO, если задание выполнить невозможно. В противном случае — две строки: строку YES и строку из 2 n символов U и D — последовательность команд робота, которая позволит ему преодолеть полосу препятствий и вернуться обратно. Первые n символов содержат описание прохождение от стены с номером 1 до стены с номером n, следующие n символов содержат описание прохождения от стены с номером n до стены с номером 1.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ n, m ≤ 105, 1 ≤ k, hi ≤ 109

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1401 ≤ n, m ≤ 102, 1 ≤ k, hi ≤ 109полная
2601 ≤ n, m ≤ 105, 1 ≤ k, hi ≤ 1091полная

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10 5 10
10 1 4 2 4 3 4 4 8 9
YES
DUDUDUUUDDDDUUUDUDUD
2
5 1 1
5 5 5 5 5
NO
3
10 10 10000
13123 141323 213323 3213 213213 321 323213 1323 213 1232113
YES
DDDDDDDDDDDDDDDDDDDD

Задача B. Зельеварение

Автор:Н. Ляхута, М. Спорышев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Вася сварил N таких зелий, i-е зелье увеличивает температуру окружающей среды на целое число ai градусов. Каждое зелье он налил в отдельную колбу, чтобы зелья начали испаряться. Все колбы одинаковы. Эффекты от паров зелий в разных колбах складываются. Колбы Вася выставил в ряд и начал наблюдать за изменением температуры в комнате.

К сожалению, температура в комнате очень быстро стала некомфортной. И тут Вася подумал, почему бы не сделать температуру воздуха в комнате равной T0 + K, где T0 — температура в комнате до приготовления зелий. Он тут же вспомнил, что на уроках заклинаний он недавно научился заклинанию исчезновения! Заклинание позволяет ему безвозвратно уничтожить любой непрерывный отрезок подряд идущих колб вместе с их влиянием на температуру воздуха в комнате. Используя только это заклинание, Вася хочет сделать температуру в комнате желаемой.

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

Помогите Васе определить, на какие колбы направить свои заклинания.

Формат входного файла

Первая строка входного файла содержит два целых числа N K —– количество колб с зельями и температура, на которую Вася хочет изменить исходную в комнате.

Вторая строка содержит N целых чисел, i-е число — количество градусов, на которое увеличится температура окружающей среды из-за паров i-ой колбы.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 2 ⋅ 103

 − 107 ≤ K ≤ 107

 − 104 ≤ ai ≤ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 0
1
1
2
5 1
1 2 3 -1 -1
4

Задача C. Синхронизация

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Начинающий учёный Вася был допущен к управлению экспериментом на большом андронном коллайдере. Эксперимент Васи включал в себя M событий, каждое из которых он тщательно зафиксировал и записал время каждого наблюдения в миллисекундах от начала эксперимента.

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

Известно, что на протяжении своего эксперимента Вася фиксировал те же самые события, которые фиксировал коллайдер.

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

Формат входного файла

Входной файл содержит целое число N. Далее следует N целых чисел a1, a2, …, aN — времена событий, зафиксированных коллайдером. Затем записано целое число M. Далее следует M чисел b1, b2, …, bM — времена событий, зафиксированных Колей.

Формат выходного файла

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

Ограничения

2 ≤ M ≤ N ≤ 105;

0 ≤ a1 ≤ a2 ≤ … ≤ aN ≤ 109;

0 = b1 ≤ b2 ≤ … ≤ bM ≤ 109;

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
10 15 17 19 20
2
0 2 
2

Problem D. Knuth-Morris-Pratt

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives two strings and finds position where the second string appears in the first one as a substring.

Input file format

First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a' to 'z' and spaces.

Output file format

Output file must contain a single integer — position of the first occurrence of the substring in a string, or  − 1 if there is none. Positions are numbered from 1.

Constraints

Length of each string does not exceed 100000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
yezhiki nachinayut i vyygryvayut
yut
16

0.304s 0.013s 19