Язык программирования

Вам дано положительное целое число N (\(1<=N<=10^{18}\)). Найдите количество пар целых чисел u и v (\(0<=u, v<=N\)) таких, что существуют два неотрицательных целых числа a и b, удовлетворяющих \(a\ xor\ b=u\) и \(a+b=v\). Здесь xor обозначает побитовое исключающее ИЛИ. Поскольку ответ может быть очень большим, вычислите его по модулю \(10^9+7\).

Входные данные
На вход подается положительное целое число N (\(1<=N<=10^{18}\)).

Выходные данные
Выведите количество возможных пар целых чисел u и v (\(0<=u, v<=N\)) , по модулю \(10^9+7\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3	5	u=0,v=0 (Пусть a=0,b=0, тогда 0 xor 0=0, 0+0=0) u=0,v=2 (Пусть a=1,b=1, тогда 1 xor 1=0, 1+1=2) u=1,v=1 (Пусть a=1,b=0, тогда 1 xor 0=1, 1+0=1) u=2,v=2 (Пусть a=2,b=0, тогда 2 xor 0=2, 2+0=2) u=3,v=3 (Пусть a=3,b=0, тогда 3 xor 0=3, 3+0=3)
2	1422	52277
3	1000000000000000000	787014179

 

Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.
Аркадий и Борис Стругацкие, Понедельник начинается в субботу
Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: a−(a⊕x)−x=0 для заданного a, где знаком  ⊕  обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Поскольку данное уравнение предназначалось для решения на машине Алдан-3, все вычисления производились над целыми неотрицательными числами по модулю 2³². Ойра-Ойра быстро нашел x, являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько всего существует решений данного уравнения. Так как все вычисления производятся по модулю 2³², Кристобаля Хунту интересует количество таких решений x, что 0 ≤ x ≤ 2³². Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

Входные данные
В первой строке задано одно целое число a (0 ≤ a ≤ 2³²−1).

Выходные данные
Выведите одно целое число — количество неотрицательных решений уравнения.

Примечание
Определим операцию побитового ИЛИ (XOR). Пусть даны два целых неотрицательных числа x и y, рассмотрим их двоичные записи (возможно с ведущими нулями): x_k...x₂x₁x₀ и y_k...y₂y₁y₀. Здесь x_i это i-й бит числа x, а y_i это i-й бит числа y. Пусть r=x⊕y — результат операции XOR над числами x и y. Тогда двоичной записью r будет r_k...r₂r₁r₀, где:
В первом примере решениями уравнения являются 0 и 2147483648=2³¹, так как 0−(0⊕0)−0=0−0−0=0 и 0−(0⊕ 2147483648)−2147483648=−4294967296=−2³²=0 по модулю 2³².

Во втором примере решениями уравнения являются 0, 2, 2147483648=2³¹ и 2147483650=2³¹+2.

В третьем примере решениями являются все x, для которых выполнено 0 ≤ x ≤ 2³².
 

Примеры

№	Входные данные	Выходные данные
1	0	2
2	2	4
3	4294967295	4294967296

Некоторый заводской цех представляет собой прямоугольник размером M на N метров (1 <= M, N <= 30). Инженер-конструктор Петя создал робота, который  может перемещаться по территории цеха и выполнять некоторую общественно-полезную работу. Робот может перемещаться только по плитам, размером 1 на 1 метр, которыми выложен пол цеха, и только параллельно осям координат.

У робота есть 4 регистра состояния, A, B, C и D. Каждый регистр может принимать одно из двух значений - TRUE или FALSE. На некоторых плитах цеха стоят радио-триггеры, которые переключают состояние каких-то регистров робота. Также на некоторых других плитах могут находиться радиомаяки, которые в зависимости от истинности формулы, соответствующей данному маяку, заставляют робота повернуть на 90 градусов налево или направо. В случае истинности совершается поворот направо.

Спецслужбы заинтересовались разработкой Пети, и решили проверить пригодность робота для работ в условиях радиации, под водой, в кратерах вулканов, на других планетах и много где еще. Для испытаний из цеха было вынесено все оборудование, поставлено некоторое количество радиомаяков и триггеров. Начиная с некоторой пустой плиты X₀, Y₀ под начальным углом A0 (0,90,180 или 270 градусов, отсчитывая от направления вверх по часовой стрелке) был запущен робот. Изначально состояния всех регистров робота - FALSE.

Аккумуляторных батарей робота хватит на K (0 < K <= 10⁹) перемещений на соседнюю плиту. После этого он остановится. Кроме того, возможен такой вариант, что Петя неправильно расставил триггеры и маяки, поэтому на некотором шаге робот врежется в стену цеха. Необходимо определить, уцелеет ли робот после испытаний и на какой клетке он остановится в случае положительного ответа на первый вопрос.

Оси координат направлены из левого верхнего угла - точки (1,1) - соответственно вправо и вниз. M - размер цеха по горизонтали, а N - по вертикали. Количество триггеров - P - не превосходит 10000, а радиомаяков - Q - 25.

Входные данные
На первой строке входного файла записаны 8 чисел - M,N,P,Q,K,X0,Y0,A0. Далее на Р строках записаны триггеры в формате "X Y R", где R - название регистра. Далее на Q строках записаны радиомаяки в формате "X Y F", где F - булева функция от переменных A..D длиной не более 250 символов, заданная корректной формулой, причем:

-    A, B, C, D, TRUE, FALSE – корректные формулы
-    Если F – корректная формула, то «(F)» и «NOT F» – корректные формулы 
-    Если F и G – корректные формулы, то «F AND G», «F OR G» и «F XOR G» – корректные формулы 
-    Операция NOT имеет наивысший приоритет, остальные операции имеют одинаковые приоритеты и выполняются слева направо, т.е. A AND NOT B OR C XOR D эквивалентно (((A AND (NOT B)) OR C) XOR D)
-    регистр букв не имеет значения
-    корректная формула не содержит лишних пробелов
Выходные данные
В случае успешного исхода вывести координаты плиты, где остановится робот. В случае краха эксперимента вывести в выходной файл единственное число «-1».

Примеры

№	Входные данные	Выходные данные
1	8 8 1 9 420000001 3 4 180 3 3 A 3 5 FALSE 6 5 FALSE 6 2 FALSE 3 2 A     3 1 FALSE 1 1 FALSE 1 8 FALSE 2 8 FALSE 2 2 TRUE	3 5

Примечание

В соответствии с рисунком, робот будет двигаться по «восьмерке» суммарной длиной 42 метра. Следовательно, прохождение 42n+1 метра эквивалентно прохождению 1 метра, т.е. робот остановится на плите с координатами 
«3 5».
 

Благотоворительные организации каждый год собирают деньги на теплую одежду бедным. У главного героя этой задачи есть целых две куртки, но это не мешает ему страдать. Одна из его курток — зимняя, а вторая — демисезонная (в ней приятно ходить осенью или весной). Куртки подобраны идеально: в зимней куртке комфортно при температуре в x градусов или ниже, а в демисезонной – при температуре выше x градусов. В общем, жить бы ему и радоваться. Но откуда бы тогда появиться задаче?

Проблема нашего героя в том, что он, надевая сегодня не ту куртку, которую носил вчера, по- стоянно забывает переложить проездной, ключи и прочие полезные вещи в карман новой куртки. Немного подумав, он решил, что не совсем подходящая к сегодняшней температуре куртка — это не так плохо, как забытые вещи. Поэтому, если сегодня незначительно теплее, чем граничная температура, он все равно пойдет в зимней куртке, аналогично для демисезонной. Чуть более формально это звучит так: он меняет куртку с зимней на демисезонную, только если сегодня за окном есть хотя бы x + d  градусов, а с демисезонной на зимнюю — если за окном x − d  градусов или холоднее. Иногда ему, конечно, не очень комфортно на улице, но зато все вещи точно с собой.

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

Входные данные
В первой строчке даны два вещественных числа x и d — граница температуры между куртками и отклонение температуры, которое герой задачи считает незначительным (−89≤x≤55, 1≤d≤6 ).

Во второй строчке дано целое число n, 1≤n≤10⁵ — количество дней в архиве прогноза погоды.

В третьей строчке перечислены n вещественных чисел ti — температура в i-й день (−89≤t_i≤55 ).

Выходные данные
Выведите одно число: количество дней, в которые герою задачи было некомфортно в той куртке, в которой он вышел в этот день
 

Примеры

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

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

Примеры

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

Первая строка входного файла содержит число n. Вам нужно вывести целое число m, где m - округленное до целого число n.
Пример.

Input	Output
3,2	3
-5,6	-6

Программистка Полиночка стала изучать оператор ввода, чтобы ее программы стали более универсальными и работали на разных наборах значений. Ей даются значения двух переменных: первая строка входного файла содержит число детей в классе, вторая -  количество девочек в классе. Ей нужно вывести на экран количество мальчиков. То есть если, например, количество детей в классе 25, из них 10 девочек, то Полиночка должны вывести, что в классе 15 мальчиков.

Пример.

Input	Output
19 10	9

Пример

Входные данные	Выходные данные
Hello, world!	# ## ######### !,Hdelorw
Twas brillig, and the slithy toves Did gyre and gimble in the wabe; All mimsy were the borogoves, And the mome raths outgrabe.	# # # # # # # # # # # # ### #### ## ###### #### ############## ############## ## # # ############## ### ######################## ,.;ADTabdeghilmnorstuvwy

В лаборатории биоинформатики ученые проводят эксперименты по распространению искусственно созданных вирусов. Для эксперимента используется специальная лабораторная установка, представляющая собой таблицу из n × m ячеек. В каждую ячейку помещается живая клетка. Ученые заражают вирусом некоторые клетки, всего исходно заражается не более 8 клеток.
Каждую секунду среди незараженных клеток, имеющих зараженную клетку в соседней по стороне ячейке, ровно одна клетка заражается вирусом.
Ученые заинтересовались, какие конфигурации зараженных клеток могут получиться через t секунд. Для начала они хотят посчитать число таких конфигураций. Помогите им это сделать.

Формат входных данных
В первой строке входного файла находятся целые числа n, m и t (1 ≤ n, m ≤ 100, 1 ≤ t ≤ 6) — размеры таблицы и количество секунд. Каждая из следющих n строк содержит m символов. Символ «.» означает, что в изначальной конфигурации клетка не заражена, а символ «*» — что заражена. Количество «*» в таблице не превышает 8. Гарантируется, что незараженных клеток в исходной конфигурации не меньше t.

Формат выходных данных
Выведите количество различных возможных конфигураций таблицы после t секунд.
 

Ввод	Вывод
2 2 1 *. ..	2
2 2 2 *. ..	3
2 2 3 *. ..	1

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

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

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

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

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

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

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

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

Пояснение

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

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

\[\frac{\Delta F}{F} = \left(\frac{R_p}{R_\star}\right)^{2} \qquad\Longrightarrow\qquad R_p = R_\star\sqrt{\frac{\Delta F}{F}}\]

Радиус звезды \(R_\star\) задан в радиусах Солнца, где \(R_\odot = 6{,}957 \cdot 10^{8}\) м. Вычислить радиус планеты в радиусах Юпитера, где \(R_{\mathrm{J}} = 7{,}1492 \cdot 10^{7}\) м.

Проверьте порядок величины: для глубины около одного процента и звезды солнечного радиуса должна получиться планета размером примерно с Юпитер.

Ввод. Два вещественных числа, каждое на своей строке: \(R_\star\) в радиусах Солнца и глубина транзита \(\Delta F/F\), где \(0 \lt R_\star \le 1000\) и \(0 \lt \Delta F/F \le 1\).

Вывод. Радиус планеты в радиусах Юпитера с шестью знаками после запятой.

Формат вывода. Ответ выводится ровно с шестью знаками после запятой, например print(f"{x:.6f}"). Функция round для вывода не годится: она отбрасывает незначащие нули, и 2.00709 не совпадёт с 2.007090.

Видимая звёздная величина \(m\) и абсолютная звёздная величина \(M\) связаны с расстоянием до звезды соотношением

\[m - M = 5\lg d - 5\]

где \(d\) выражено в парсеках. Отсюда

\[d = 10^{\,(m - M + 5)/5}\]

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

Здесь возведение в степень с дробным показателем: в Python это оператор **. Проверьте себя определением абсолютной звёздной величины: если \(m = M\), расстояние равно ровно 10 парсекам.

Ввод. Два вещественных числа, каждое на своей строке: \(m\) и \(M\), где \(-30 \le m \le 30\) и \(-30 \le M \le 30\).

Вывод. Расстояние в парсеках с шестью знаками после запятой.

Формат вывода. Ответ выводится ровно с шестью знаками после запятой, например print(f"{x:.6f}"). Функция round для вывода не годится: она отбрасывает незначащие нули, и 2.00709 не совпадёт с 2.007090.

Тело обращается вокруг центрального тела массой \(M\) по орбите с большой полуосью \(a\). Период обращения

\[T = 2\pi\sqrt{\frac{a^{3}}{GM}}\]

где \(G = 6{,}67430 \cdot 10^{-11}\) м³·кг⁻¹·с⁻².

Вычислить период обращения в сутках (1 сутки = 86400 с).

Проверьте себя: для орбиты Земли, где \(a = 1{,}496 \cdot 10^{11}\) м и \(M = 1{,}989 \cdot 10^{30}\) кг, должно получиться около 365 суток.

Ввод. Два вещественных числа, каждое на своей строке: \(a\) в метрах и \(M\) в килограммах.

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

Формат вывода. Ответ выводится ровно с шестью знаками после запятой, например print(f"{x:.6f}"). Функция round для вывода не годится: она отбрасывает незначащие нули, и 2.00709 не совпадёт с 2.007090.

Тело брошено с поверхности земли со скоростью \(v\) под углом \(\alpha\) к горизонту. Сопротивление воздуха не учитывается. Дальность полёта

\[L = \frac{v^{2}\,\sin 2\alpha}{g}\]

Вычислить дальность.

Угол задан в градусах, а тригонометрические функции принимают радианы: переведите угол функцией math.radians. Учтите, что \(\sin 2\alpha \ne 2\sin\alpha\).

Проверьте себя предельными случаями: при \(\alpha = 0\) и при \(\alpha = 90^\circ\) дальность обращается в ноль, а максимум достигается при \(\alpha = 45^\circ\).

Ввод. Три вещественных числа, каждое на своей строке: \(v\) в м/с, \(\alpha\) в градусах и \(g\) в м/с², где \(0 \le v \le 10^4\), \(0 \le \alpha \le 90\), \(0 \lt g \le 100\).

Вывод. Дальность полёта в метрах с шестью знаками после запятой.

Формат вывода. Ответ выводится ровно с шестью знаками после запятой, например print(f"{x:.6f}"). Функция round для вывода не годится: она отбрасывает незначащие нули, и 2.00709 не совпадёт с 2.007090.

Три резистора соединены параллельно. Их общее сопротивление находится из

\[\frac{1}{R} = \frac{1}{R_1} + \frac{1}{R_2} + \frac{1}{R_3}\]

Вычислить \(R\).

Ввод. Три вещественных числа, каждое на своей строке: \(R_1\), \(R_2\), \(R_3\) в омах, где \(0 \lt R_i \le 10^6\).

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

Формат вывода. Ответ выводится ровно с шестью знаками после запятой, например print(f"{x:.6f}"). Функция round для вывода не годится: она отбрасывает незначащие нули, и 2.00709 не совпадёт с 2.007090.

Период малых колебаний математического маятника длиной \(L\) при ускорении свободного падения \(g\) равен

\[T = 2\pi\sqrt{\frac{L}{g}}\]

Вычислить период.

 

Ввод. Два вещественных числа, каждое на своей строке: \(L\) в метрах и \(g\) в м/с², где \(0 \lt L \le 10^6\), \(0 \lt g \le 100\).

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

Формат вывода. Ответ выводится ровно с шестью знаками после запятой, например print(f"{x:.6f}"). Функция round для вывода не годится: она отбрасывает незначащие нули, и 2.00709 не совпадёт с 2.007090.

Палитра изображения содержит \(N\) различных оттенков. Определить наименьшее целое число бит, которого достаточно для кодирования номера оттенка, то есть наименьшее \(i\), при котором

\[2^i \ge N\]

Напрашивается решение math.ceil(math.log2(N)). Оно работает не всегда: логарифм вычисляется приближённо, и на больших \(N\) результат может отличаться от истинного на единицу. Проверьте своё решение на \(N = 2^{50}\) и \(N = 2^{50} + 1\).

Точный ответ даёт (N - 1).bit_length(): метод возвращает число значащих двоичных разрядов, а у числа \(N - 1\) их ровно столько, сколько бит нужно для \(N\) значений.

Ввод. Одно целое число \(N\), где \(1 \le N \le 10^{18}\).

Вывод. Одно целое число — количество бит.