Информатика

Однажды на огород к Ивану Петровичу (сыну Деда Мороза и Снегурочки) забежало целых три оленя. Известно, что олени — весьма агрессивное нечто, особенно когда речь идет о борьбе за вкусную зелень. Поэтому каждый из трех оленей, заметив других козлов, замер на месте и начал наблюдать за оставшимися оленями: одним глазом за одним оленем, другим — за оленем номер 2. Естественно, для этого оленю нужно “косить” глазами.

Определите наибольший угол, на который пришлось “раскосить” глазами этим странным животным. Причём тут Иван Петрович и мы, и как олени “раскосили” глаза, мы в душе не знаем. Своего дилера мы не сдадим.

Программа получает на вход координаты трех точек, в которых стоят олени (сначала координаты первого оленя, затем — второго и третьего). Координаты — пара целых чисел, не превосходящих 104 по модулю.
 

Ввод	Вывод
0 0 3 0 0 4	90.000000

Дед Мороз очень любит раздавать «подарочки» и если он долго их не раздаёт, то начинает грустить и поедать печеньки (не факт, что печеньки не олени). И он начинает толстеть, но когда он дарит хотя бы один подарочек, то возвращается к начальному весу (Т-Т ©Маша). На какой максимальный вес потолстеет Дед Мороз, если на одном отрезке он дарит по 1 подарку на каждый целый индекс, а всего он обойдёт m домов. Даны n отрезков пути для Деда Мороза на его траектории раздачи подарочков и сами отрезки. Также дано количество домов, которое он обойдёт.

Изначальный вес Деда Мороза 227 ± 1 кг.

Ввод	Вывод
3 12 2 6 3 9 3 4	3

На вход программы подаются произвольные алфавитно-цифровые символы. Ввод этих символов заканчивается точкой. Требуется написать программу, которая будет печатать последовательность строчных английских букв ('a' 'b'... 'z') из входной последовательности и частот их повторения. Печать должна происходить в алфавитном порядке.

Например, пусть на вход подаются следующие символы:

fhb5kbfыshfm.

В этом случае программа должна вывести

b2

f3

h2

k1

m1

s1

2

4

6

8

10

Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?

 

Вводится одно число N

 

Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число.
 

Ввод	Вывод
5	3

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

Помогите ему решить эту задачу. 
 

Входные данные
Первая строка входных данных содержит общее количество ценников N, 2 <= N <= 10⁵, N – чётное число. Следующие N строк содержат целые положительные числа, не превосходящие 10⁹, идущие в порядке неубывания по одному в строке – числа, записанные на всех ценниках (как старых, так и новых). Гарантируется, что входные данные корректны,то есть решение существует.

Выходные данные
Программа должна вывести N/2  целых чисел в порядке неубывания – стоимости товаров после понижения цен.

 

Примеры

№	Входные данные	Выходные данные	Примечание
1	6 30 40 42 45 56 60	30 42 45	До распродажи цены товаров были 40, 56, 60, после снижения цены на эти товары стали равны 30, 42, 45.

Для исполнения большого танца в круг выстроилось N танцоров (N чётное). Пронумеруем танцоров числами от 1 до N начиная от подиума по часовой стрелке. На каждом шаге танца танцоры разбиваются на пары (пару образуют два соседних по кругу танцора), и танцоры в паре меняются местам, причём на первом и всех последующих нечётных шагах танцор, стоящий в начале круга, образует пару с танцором, стоящим рядом с ним по часовой стрелке. Также пару образуют два танцора, следующие за ними по часовой стрелке, и т. д. На втором шаге и всех шагах с чётными номерами танцор, стоящий в начале

круга, образует пару с танцором, стоящим рядом с ним против часовой стрелки. Два танцора, следующие за ними против часовой стрелки, также образуют пару и т. д. 
 

На рисунке изображена начальная расстановка для N = 6 танцоров и два следующих шага танца. Расположение подиума отмечено точкой.
Определите, кто будет стоять рядом с танцором номер P через K шагов.

Программа получает на вход три целых числа N, P, K, записанные в отдельных строках. Первое число N – количество танцоров в кругу, N чётное. Второе число P – номер танцора, 1 ≤ P ≤ N. Третье число K – количество сделанных шагов после начала танца, 1 ≤ K. Максимальные значения для N и K <= 10⁹. 
 

Программа должна вывести два целых числа в порядке возрастания – номера танцоров, которые будут стоять рядом с танцором номер P после K шагов танца.


 

Ввод	Вывод	Примечание
6 5 2	2 4	Рисунок выше соответствует этому примеру.

Дана правильная рациональная несократимая дробь a / b. С этой дробью выполняется следующая операция: к числителю и знаменателю дроби прибавляется 1, после чего дробь сокращается. Определите, можно ли при помощи таких операций из дроби a / b получить другую правильную дробь c / d.

Программа получает на вход четыре целых числа a, b, c, d, причём 0 < a < b ≤ 10⁵, 0 < с < d ≤ 10⁵, числа a и b взаимно простые, числа с и d взаимно простые, a / b ≠ c / d.

Программа должна вывести одно натуральное число – сколько описанных операций нужно применить, чтобы из дроби a / b получить дробь с / d. Если это сделать невозможно, программа должна вывести число 0.

Ввод	Вывод	Примечание
1 3 2 3	2	Дана дробь 1 / 3. После первой операции получается дробь 2 / 4, которая сокращается до 1 / 2. После второй операции получается дробь 2 / 3.
2 3 1 3	0	Получить из дроби 2 / 3 дробь 1 / 3 невозможно.

 

Рабочий день закончился, и сотрудники бизнес-центра собрались по домам. Бизнесцентр представляет собой N-этажное здание, этажи пронумерованы от 1 до N снизу вверх. Все сотрудники хотят спуститься на парковку, которая расположена в подвальном помещении на один этаж ниже первого. Бизнес-центр оборудован лифтом, который может перевозить не более K человек одновременно. Лифт перемещается вверх или вниз на один этаж за одну секунду, посадка и высадка пассажиров происходят мгновенно. Изначально лифт расположен на уровне парковки. Известно, сколько людей хотят спуститься на парковку с каждого

из N этажей. Определите, какое минимальное время потребуется, чтобы перевезти на парковку всех сотрудников бизнес-центра.
 

Первая строка входных данных содержит наибольшее возможное число людей в лифте K, 1 ≤ K ≤ 10⁹

Вторая строка содержит число этажей в бизнес-центре N, 1 ≤ N ≤ 10⁵

 

Следующие N строк содержат целые неотрицательные числа – число людей, ожидающих лифт на 1, 2, … , N-м этаже соответственно, эти числа не превосходят 10⁹  каждое. В здании находится хотя бы один человек. 

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

Ввод	Вывод	Примечание
2 3 3 0 1	8	Лифт перевозит 2 человек, в здании 3 этажа. Лифт поднимается на первый этаж за 1 с, забирает 2 человек и за 1 с спускается на парковку, затем лифт поднимается на первый этаж, забирает 1 человека, вместе с ним поднимается на третий этаж, забирает 1 человека и спускается на парковку. Подъём на третий этаж занимает 3 с, спуск – ещё 3 с.

В зале ожидания на вокзале стоят N рядов из M кресел. Чтобы ожидающие не скучали, вместо некоторых кресел установлено K мощных Wi-Fi роутеров. Ожидающие стараются занять места ближе к роутерам, так как тогда они смогут смотреть ролики с Youtube или VK с более высоким разрешением, без задержек. Если пассажир сидит на месте с номером c в ряде r, а i-й роутер расположен на месте C_i в ряде R_i, то расстояние до i-го роутера вычисляется как max(|r−R_i|,|c−C_i|), где |x| – абсолютное значение x. Креслам в зале ожидания был присвоен приоритет от 1 до N⋅M−K, меньшие номера получили кресла с меньшим расстоянием до ближайшего роутера, среди кресел с одинаковым расстоянием до роутеров более удобными считаются кресла, стоящие в ряду с меньшим номером, а среди них — с меньшим номером места в ряду. На рисунке показан приоритет кресел в зале ожидания с 4 рядами из 7 кресел, в котором установлены 2 роутера (их позиции помечены черным цветом). Темно-серым цветом выделены кресла, стоящие на расстоянии 1 от роутеров, светло-серым — на расстоянии 2, белым — 3.
 

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

Первая строка ввода содержит четыре целых чисел — количество рядов N (2 ≤ N ≤ 10⁹) и мест в ряду M (2 ≤ M ≤ 10⁹), количество роутеров K (1 ≤ K ≤ 100, K < N⋅M), количество запросов Q (1 ≤ Q ≤ 100). Далее следует K строк, содержащих два целых числа — местонахождение роутеров: номер ряда Ri (1 ≤ R_i ≤ N) и номер места в ряду C_i (1 ≤ С_i ≤ M). Среди них нет совпадающих. Далее следует строка, содержащая Q целых чисел в диапазоне от 1 до N⋅M−K – приоритеты кресел.

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

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

произведение натуральных чисел a и b кратно числу с

С клавиатуры вводится три числа, каждое в отдельной строке: в первой строке вводится число a, во второй - b, в третьей - с