3 задачи для универа

Задача А. Столовая

 Вася только устроился в компанию, но уже успел полюбить столовую в офисе. Теперь он каждый день ходит в эту столовую, где на выбор предлагается 𝑛 различных блюд. Известно, что 𝑖-е блюдо стоит 𝑥𝑖 рублей. Вася планирует в ближайшие 𝑞 дней покупать по одному блюду в день. Он решил, что в 𝑖-ый день он не хочет тратить на еду больше, чем 𝑚𝑖 рублей. Помогите Васе узнать, насколько велик будет выбор блюд для него в каждый из дней, если компания оплатит Васе половину стоимости обеда. 

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

В первой строке входных данных содержится целое число 𝑛 (1 ≤ 𝑛 ≤ 200000) — количество блюд в столовой. Во второй строке входных данных содержится 𝑛 чисел 𝑥𝑖 (1 ≤ 𝑥𝑖 ≤ 200000) — цена 𝑖-го блюда. В третьей строке входных данных содержится число 𝑞 (1 ≤ 𝑞 ≤ 200000) — количество дней, в течение которых Вася планирует ходить в столовую. В следующих 𝑞 строках входных данных содержатся целые числа 𝑚𝑖 (1 ≤ 𝑚𝑖 ≤ 200000) — количество денег, которое есть у Васи в 𝑖-й день. 

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

Выведите 𝑞 целых чисел (каждое число в новой строке), 𝑖-е из которых должно равняться количеству блюд, на которые у Васи может хватить денег в день 𝑖. 

Пример 

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

5 

6 20 16 12 22 

4 

1

10

3 

11 

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

0 

4 

1 

5 

Примечание 

В первом запросе ни на одно блюдо Васе не хватит денег (он может купить блюдо максимальной стоимостью 2 рубля – один он оплатил бы сам, а второй компания). Во втором запросе Васе хватит денег, чтобы купить одно из четырех первых блюд. В третьем запросе Васе хватит денег только на первое блюдо. И в последнем запросе Вася может позволить себе любое блюдо. 

Задача B. Путь на работу 

Добираться Васе до офиса не так уж и сложно — от метро до офиса компании курсирует шаттл. Будем считать, что он едет по прямой от метро (точка 0) до офиса (точка 𝑠) и обратно, преодолевая 1 метр за 𝑡1 секунд в обоих направлениях. То есть шаттл ходит равномерно прямолинейно, мгновенно разворачиваясь в точках 𝑥 = 0 и 𝑥 = 𝑠. В точке 𝑥1 находится Вася. Ему нужно попасть в точку 𝑥2. Он преодолевает 1 метр за 𝑡2 секунд. Вам нужно определить минимальное время, за которое Вася сможет добраться из точки 𝑥1 в точку 𝑥2, если известно, где находится шаттл и в каком направлении он едет в момент, когда Вася пришел в точку 𝑥1. Вася может неограниченное количество раз заходить в шаттл в любой момент времени, когда позиции его и шаттла совпадают. Точки, в которых Вася может заходить и выходить из шаттла, не обязательно целочисленные. Считайте, что любая высадка/посадка происходит мгновенно. Вася может произвольным образом перемещаться по прямой (но не быстрее, чем 1 метр за 𝑡2 секунд) или даже стоять на месте. 

Входные данные В первой строке следуют три целых числа 𝑠, 𝑥1 и 𝑥2 (2 ≤ 𝑠 ≤ 1000, 0 ≤ 𝑥1, 𝑥2 ≤ 𝑠, 𝑥1 ≠ 𝑥2) — максимальная координата точки, до которой доезжает шаттл, точка, в которой находится Вася и точка, в которую ему нужно попасть. Во второй строке следуют два целых числа 𝑡1 и 𝑡2 (1 ≤ 𝑡1,𝑡2 ≤ 1000) — время в секундах, за которое шаттл преодолевает 1 метр, и время в секундах, за которое Вася преодолевает 1 метр. В третьей строке следуют два целых числа 𝑝 и 𝑑 (1 ≤ 𝑝 ≤ 𝑠 − 1, 𝑑 равняется 1 или −1) — позиция шаттла в момент, когда Вася пришел в точку 𝑥1, а также направление движения шаттла в этот же момент. Если 𝑑 = −1, то шаттл движется к метро (то есть в направлении от точки 𝑠 в точку 0). Если 𝑑 = 1, то шаттл движется к офису (то есть в направлении от точки 0 в точку 𝑠). 

Выходные данные Выведите минимальное время в секундах, за которое Вася может добраться из точки 𝑥1 в точку 𝑥2. 

Примеры 

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

4 2 4 

3 4 

1 1 

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

8 

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

5 4 0 

1 2 

3 1 

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

7 

Примечание 

В первом примере Васе выгоднее пойти пешком. Таким образом, ему нужно пройти 2 метра, и он сможет это сделать суммарно за 8 секунд, так как он преодолевает 1 метр за 4 секунды. Во втором примере он может, например, пойти в сторону точки 𝑥2 и дойти до точки с координатой 1 за 6 секунд (так как ему нужно пройти для этого 3 метра, а он преодолевает 1 метр за 2 секунды). В этот момент времени, шаттл также будет находиться в точке 1, поэтому Вася может зайти в него, и доехать оставшийся 1 метр за 1 секунду. Таким образом, Вася доберётся до точки 𝑥2 суммарно за 7 секунд. 

Задача C. Чаты 

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

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

В первой строке записано целое число 𝑛 (1 ≤ 𝑛 ≤ 300 000) — количество сообщений. Далее в 𝑛 строках перечислены адресаты сообщений в порядке отправки\получения сообщений. Имя каждого адресата — непустая последовательность строчных букв английского алфавита длины не более 10. 

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

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

Пример 

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

4 

alex 

ivan 

roman 

ivan 

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

ivan 

roman 

alex 

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

8 

alina 

maria 

ekaterina 

darya 

darya 

ekaterina 

maria 

alina 

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

alina 

maria 

ekaterina 

darya