Информатика

Пример

Входные данные	Выходные данные
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

Лифт

В 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 гр. против часовой стрелки.

 

Какие существуют подходы к измерению информации?

1. алфавитные и цифровой
2. алфавитный и содержательный
3. аналоговый и дискретный
4. аналоговый и линейный

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

\[\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}\).

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

Производится звукозапись с частотой дискретизации f Гц и глубиной кодирования b бит на отсчёт. Запись ведётся по c каналам. Определить, сколько целых секунд записи поместится в память объёмом V байт.

Чтобы не терять точность, переведите объём памяти в биты.

Ввод. Четыре целых числа, каждое на своей строке: \(f\), \(b\), \(c\) и \(V\), где \(1 \le f \le 10^6\), \(1 \le b \le 64\), \(1 \le c \le 8\), \(1 \le V \le 10^{15}\).

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