Информатика

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

 

В первой строке входного файла указано число N (0≤N≤1500). В следующих N строках заданы по 4 целых числа x1, y1, x2, y2 — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего (0≤x1≤x2≤10⁹, 0≤y1≤y2≤10⁹). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.

 

В выходной файл выведите единственное число — ответ на задачу.
 

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

На прямой задано некоторое множество отрезков с целочисленными координатами концов \([L_i, R_i]\). Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок \([0, M]\), (M — натуральное число), содержащее наименьшее число отрезков.

 

В первой строке указана константа M (\(1<=M<=5000\)). В каждой последующей строке записана пара чисел Li и Ri (\(|L_i|,|R_i| < 50000\)), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.

 

В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка \([0; M]\). Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка \([0; M]\) исходным множеством отрезков \([L_i, R_i]\) невозможно, то следует вывести единственную фразу “No solution”.

 

Примеры

№	Входные данные	Выходные данные
1	1 -1 0 -5 -3 2 5 0 0	No solution
2	1 -1 0 0 1 0 0	1 0 1

Выборы президента США проходят по непрямой схеме. Упрощённо схема выглядит так. Сначала выборы проходят по избирательным округам, на этих выборах голосуют избиратели (то есть все граждане, имеющие право голоса). Затем голосование проходит в коллегии выборщиков, на этих выборах каждый избирательный округ представлен одним выборщиком, который голосует за кандидата, победившего на выборах в данном

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

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

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

Программа получает на вход два целых числа N и K (1 ≤ N ≤ 10³ , 1 ≤ K ≤ 10⁶ ) и должна вывести одно целое число – искомое количество избирателей.

Ввод	Вывод	Примечание
5 3	6	Чтобы данный кандидат получил большинство в коллегии выборщиков, необходимо, чтобы 3 из 5 выборщиков проголосовали за него, то есть кандидат должен одержать победу в 3 округах. Каждый округ состоит из 3 избирателей, поэтому для победы в округе необходимо набрать 2 голоса в данном округе.

На автобусных билетах указываются их номера. Номера всех билетов всегда записываются при помощи одного и того же количества цифр, при этом число используемых цифр чётно. При необходимости числа дополняются ведущими нулями. К примеру, если для записи используют 4 цифры, то 514 будет записано как 0514. Билеты отпечатаны на лентах, билеты на каждой ленте нумеруются подряд числами от 00...01 до 99...99.

Счастливым считается тот билет, у которого сумма цифр первой половины равна сумме цифр второй половины, например, билеты 1001 и 123051 счастливые, а 7778 и 39 – нет. Сегодня Дима зашел в автобус, и кондуктор выдал ему билет с номером N. Поскольку Диме ехать достаточно долго, а заняться чем-нибудь надо, он стал думать, какой номер будет иметь следующий счастливый билет, выданный из той же ленты, что и Димин билет. Если в текущей ленте не осталось счастливых билетов, Диму интересует номер минимального счастливого билета из новой ленты.

В первой и единственной строке входного файла содержится номер Диминого билета N, записанный с ведущими нулями. Количество цифр в записи числа N не превосходит 100 000 и чётно.

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

Ввод	Вывод	Примечание
0514	0523	Диме был выдан счастливый билет (сумма цифр обеих половин равна 5), но Диму не интересует номер его билета, его интересует номер следующего счастливого билета.

 

 

Для того чтобы компьютеры поддерживали актуальное время, они могут обращаться к серверам точного времени SNTP (Simple Network Time Protocol). К сожалению, компьютер не может просто получить время у сервера, потому что информация по сети передаётся не мгновенно: пока сообщение с текущим временем дойдёт до компьютера, оно потеряет свою актуальность. Протокол взаимодействия клиента (компьютера, запрашивающего точное время) и сервера (компьютера, выдающего точное время) выглядит следующим образом:
 

1) Клиент отправляет запрос на сервер и запоминает время отправления A (по клиентскому времени).

2) Сервер получает запрос в момент времени B (по точному серверному времени) и отправляет клиенту сообщение, содержащее время B.

3) Клиент получает ответ на свой запрос в момент времени C (по клиентскому времени) и запоминает его. Теперь клиент, из предположения, что сетевые задержки при передаче сообщений от клиента серверу и от сервера клиенту одинаковы, может определить и установить себе точное время, используя известные значения A, B, C.

Вам предстоит реализовать алгоритм, с точностью до секунды определяющий точное время для установки на клиенте по известным A, B и C. При необходимости округлите результат до целого числа секунд по правилам арифметики (в меньшую сторону, если дробная часть числа меньше ½, иначе в большую сторону). 

Возможно, что, пока клиент ожидал ответа, по клиентскому времени успели наступить новые сутки, однако известно, что между отправкой клиентом запроса и получением ответа от сервера прошло менее 24 часов. 

Программа получает на вход три временные метки A, B, C, по одной в каждой строке. Все временные метки представлены в формате «hh:mm:ss», где «hh» – это часы, «mm» – минуты, «ss» – секунды. Часы, минуты и секунды записываются ровно двумя цифрами каждое (возможно, с дополнительными нулями в начале числа). 
 

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

Ввод	Вывод	Примечание
15:01:00 18:09:45 15:01:40	18:10:05	Клиент отправил запрос в 15:01:00 по своим часам, сервер получил запрос в 18:09:45 по своим часам. Клиент получил ответ в 15:01:40, в этот момент точное время будет 18:10:05.

Дима – программист, поэтому на его компьютере всегда открыто много окон. Так как у Димы не очень большой монитор, на нём может отображаться только одно окно. В каждый момент времени оконный менеджер хранит список открытых окон, первое окно списка отображается на мониторе. Для переключения окон Дима использует сочетание клавиш Alt + Tab. Если удерживать эту кнопку нажатой в течение T секунд, то. T + первое по счёту окно в текущей нумерации переместится на первую позицию, а относительный порядок остальных окон не изменится. 

Например, на рисунке ниже показано, что произойдёт с порядком окон, если нажимать на Alt + Tab в течение 3 секунд. Если держать Alt + Tab N – 1 секунду, то первым станет последнее окно из списка. Список открытых окон «зациклен», за последним окном следует первое окно из списка, т. е. если удерживать Alt + Tab нажатым N секунд, то окно, которое было первым в списке, останется на первом месте.

Если удерживать Alt + Tab N + 1 секунду, на первое место переместится второе по счёту окно и т.д.

В начале рабочего дня любимая среда разработки Димы имела номер M в списке открытых окон. В течение дня Дима K раз использовал сочетание клавиш Alt + Tab. Определите, на какой позиции находится его любимая среда разработки в конце дня.

Входные данные:
Первая строка входных данных содержит целое число N, \(1 <= N <= 10^5\) – количество окон на экране.
Вторая строка содержит целое число M, \(1 <= M <= N \)– номер, который имела любимая среда разработки Димы в начале дня.
Третья строка содержит целое число K, \(1 <= K <= 10^5\) – количество раз, которое Дима нажимал Alt + Tab. В последующих K строках содержатся целые положительные числа, не превосходящие 10⁵  – длительность каждого нажатия в секундах.
Выходные данные:

Как известно, комета Бармалея видна с Земли каждые C лет. Любопытно, что это происходит в годы, кратные C, т.е. C, 2×C, 3×C и т.д. Не каждому суждено увидеть эту комету хотя бы однажды в жизни. Впрочем, находятся счастливые долгожители, заставшие её прилёт даже несколько раз.

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

Бармалео Бармалей родился 1 января в год A и умер 31 декабря в год B. Сколько раз за его жизнь комета была видна с Земли? Мы считаем, что он мог видеть комету, даже будучи младенцем или глубоким стариком, т.е. если она прилетала в год A или B.

Программа получает на вход три целых числа A, B и C (1 ≤ A ≤ B ≤ 2×10⁹ , 1 ≤ C ≤ 2×10⁹ ) и должна вывести одно целое число – количество раз, которое комета была

видна между годами A и B включительно.

Ввод	Вывод	Примечание
1850 1900 50	2	Комета пролетала около Земли в 1850 и 1900 годах. Бармалео Бармалей застал оба раза.

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

Напишите программу, которая вычисляет минимальное время путешествия, используя информацию о "кротовых норах".

В первой строке ввода содержится целое число N (1 ≤ N ≤ 100). Далее следует строка, содержащая 6 целых чисел — координаты начальной (x_s,y_s,z_s) и конечной (x_t,y_t,z_t) точки путешествия. Далее следует N строк, содержащих 6 целых чисел — координаты концов "кротовых нор". Все координаты измеряются в парсеках и находятся в диапазоне от 0 до 10000, и нет точек с совпадающими координатами.

Вывести минимальное время путешествия в секундах с точностью не менее 10⁻⁶.
Примеры

№	Входные данные	Выходные данные
1	1 0 0 0 100 100 0 1 1 1 50 100 10	52.722246

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

 

Входные данные содержит одно натуральное число N (\(N <= 2^{30}\)).

 

Выведите ответ на задачу.
 

 

Примеры

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