Информатика

В Волшебной стране используются монетки достоинством A₁, A₂,..., A_M. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы  сначала поступает число N (1 <= N <= 10⁹), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A₁, A₂,..., A_M (1 <= A_i <= 10⁹).

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

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
 

Ввод	Вывод
100 6 11 20 30 40 11 99	3 40 30 30

Примечание

Подсказки

В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a₁, a₂, …, a_N. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.

3
	1
		4
			1
				5
					9
						2
							6

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

Возьмем четырехзначное число, в котором не все цифры одинаковы, например, 6264. Расположим цифры сначала в порядке убывания - 6642; затем, переставив их в обратном порядке, получим 2466. Вычтем последнее число из 6642. На следующем шаге с полученной разностью проделаем тоже самое. Через несколько таких действий получится число, переходящее само в себя и называемое постоянной Капрекара. Если разность получается трехзначная, надо в начале добавить ноль.

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

Входные данные: вводится одна строка, в которой записано четырехзначное число.

Выходные данные: выведите в первой строке постоянную Капрекара, во второй – количество шагов для ее получения.

 

 

Примеры

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

 

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается (дублируется) последняя цифра.
3) Затем справа к числу дописывается бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.
4) К полученному результату дописывается справа ещё один бит чётности: 0, если в двоичном коде, полученного после пункта 3 числа, чётное число единиц, и 1, если нечётное
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого автомат получает число, большее 114. В ответе это число запишите в десятичной системе.
 

Юра Баранкин заполнял таблицу истинности функции \(((x \rightarrow z) \wedge (z \rightarrow w)) \vee (y \equiv (x \vee z))\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из трёх различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

?	?	?	?	F
1	1			0
1			1	0
	1			0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных w, x, y, z. 
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
 

Лифт

В 2086 году в программу зимней олимпиады решено было добавить соревнования по перетягиванию каната на льду. Для проведения финала соревнования организаторы нашли n кусков каната. Для повышения зрелищности соревнования решено было сделать связать некоторые из этих кусков в один как можно более длинный канат.

Когда начались работы по связыванию, выяснилось, что на узел, связывающий два куска каната между собой, уходит по d сантиметров каната с каждого из связываемых концов. Также, оказалось, что связывать так, что получающиеся узлы находятся близко друг к другу, невозможно: расстояние между соседними узлами должно быть хотя бы d сантиметров. Например, если d = 10, то после связывания кусков каната длиной 25 и 50 сантиметров, получается канат длиной 55 сантиметров, в 15 сантиметрах от одного из краев которого находится узел.

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

Формат входных данных
В первой строке заданы числа n (1 ≤ n ≤ 100 000) и d (1 ≤ d ≤ 1000) — количество кусков каната и длина каната, уходящая на завязывание узла. Во второй строке заданы n чисел ai (1 ≤ a_i ≤ 1000) — длины имеющихся кусков каната.

Формат выходных данных
Выведите единственное число — максимальную длину каната, которую можно получить.
 

Ввод	Вывод
2 10 25 50	55
5 2 4 5 6 7 8	14

Организаторы Всероссийской командной олимпиады школьников по программированию всегда ответственно относятся ко всем этапам проведения соревнования. Недавно организаторам были доставлены футболки для участников олимпиады. Они были сложены в ящик, который является кубом со стороной в один метр. Ящик был поставлен в углу комнаты прямоугольной формы размером m × n метров. Чтобы никто случайно не забрал ящик, на его верхней грани красной краской написали слово «ВКОШП».

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

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

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

Помогите организаторам — посчитайте, сколько раз надпись «ВКОШП» коснется пола при оптимальном перекатывании куба с футболками.

Формат входных данных
В первой строке задано два числа n и m (1 ≤ n, m ≤ 10⁹ ) — размеры комнаты в метрах.

Формат выходных данных
Выведите одно число — сколько раз надпись «ВКОШП» окажется на нижней грани при оптимальном перемещении ящика.
 

Ввод	Вывод
1 2	0
3 3	1

Пояснение

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

Мальчик Вася очень любит геометрию. Кроме того, ему очень нравится забивать гвозди в доску. Сегодня он изучает свою любимую металлическую пластину, которую он собирается прибить к деревянной доске.

Пластина имеет форму, ограниченную многоугольником без самопересечений и самокасаний. В первой вершине многоугольника пластина имеет маленькую петлю.

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

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

Формат входных данных
В первой строке входного файла задано число n (3 ≤ n ≤ 2 000) — количество вершин многоугольника. В следующих n строках заданы координаты вершин многоугольника в порядке обхода. В следующей строке задано число m (1 ≤ m ≤ 2 000) — количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих m строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины. Все координаты во входном файле целые и не превосходят 10⁶ по модулю.

Формат выходных данных
Выходной файл должен содержать m строк. В i-й строке выведите два вещественных числа α_i и β_i , где α_i — максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в i-ю точку, а β_i — максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки. Если гвоздь не мешает пластине поворачиваться, выведите α_i = β_i = 360. Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит 10⁻⁶ .
 

Ввод	Вывод
4 0 0 -3 -3 0 -6 3 -3 3 -8 0 -2 0 2 -1	360.000000000000 360.000000000000 45.000000000000 225.000000000000 251.565051177078 18.434948822922

Пояснение


На рисунке выше изображен тест из примера. Прямоугольник показывает начальное положение пластины.
Точками показаны позиции, в которые Вася планирует забить гвоздь.
Гвоздь, забитый в первую точку, не мешает пластине поворачиваться.
Гвоздь, забитый во вторую точку, позволяет повернуть пластину на 45 гр.  по часовой стрелке или на 225 гр. против часовой стрелки.

 

Входные данные
Дано число N (1 <= N <= 100000) – кол-во запросов. В следующих N строках содержится символ ‘+’ или ‘-’ и число a (1 <= a <= 1000000000). Если символ – ‘+’, то число a добавляется в множество, иначе – удаляются все значения a, которые были добавлены ранее.
Гарантируется, что при удалении числа, оно содержится в множестве.

Выходные данные
Требуется вывести в порядке возрастания все уникальные элементы в множестве после выполнения всех запросов или «-1», если в множестве нет элементов.

 

Примеры

№	Входные данные	Выходные данные
1	3 + 1 + 2 - 1	2
2	3 + 1 + 1 - 1	-1
3	3 + 1 + 1 + 1	1

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.
3) К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите количество исходных чисел N, из которых с помощью этого алгоритма могут быть получены числа R, лежащие в диапазоне 64 ≤ R < 72.
 

Юра Баранкин заполнял таблицу истинности функции \((y \rightarrow (z \wedge x)) \vee (x \equiv y)\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из двух различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных x, y, z.

?	?	?	F
0		0	0
1			0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных x, y, z. 
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
 

Вам дается массив a размера n и q запросов к нему. Есть запросы двух типов:

• 1 l_i r_i — осуществить циклический сдвиг отрезка [l_i, r_i] вправо. То есть, для каждого такого x, что l_i ≤ x < r_i, a_x + 1 становится равным прежнему значению a_x, а a_li становится равным прежнему значению a_ri;
• 2 l_i r_i — перевернуть отрезок [l_i, r_i].

 
Необходимо вывести массив после обработки всех запросов.
 
Входные данные
В первой строке записаны два целых числа n и q (1 ≤ n, q ≤ 2·10⁵).
Во второй строке записаны n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).
Дальше идут q строк. В i-й из них записаны три целых числа t_i, l_i, r_i, где t_i — тип i-го запроса, [l_i, r_i] — отрезок, на котором запрос выполняется (1 ≤ t_i ≤ 2, 1 ≤ l_i ≤ r_i ≤ n).
 
Выходные данные
Выведите m чисел, i-е из которых равно числу на позиции b_i после обработки всех запросов.

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

(c) Курбатов Е., 2018