Археологический раздел НИИЧАВО решил заняться изучением древнефлатландских волшебных шпаг. После изучения всех имеющихся в наличии образцов было выяснено, что почти все шпаги на самом деле являются копиями друг друга.

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

Поскольку изготовление копии волшебной шпаги снижает ее магическую силу, ученые установили, что с каждой шпаги было сделано не более двух копий. Также было установлено, что копия могла быть изготовлена не ранее чем через \(k\) лет после изготовления оригинала.

В распоряжении ученых оказались \(n\) шпаг, про каждую из которых им известен ее возраст. Ученые хотят выяснить, какая из шпаг была изготовлена первой, а для всех остальных шпаг выяснить, с какой из шпаг она была скопирована. К сожалению, информации о возрасте может быть недостаточно, чтобы восстановить эту информацию однозначно, но ученых устроит любой возможный вариант

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

В одном городе на перекрестке, на котором пересекаются две односторонние дороги, решили установить светофор.

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

Светофор устроен следующим образом. В момент времени \(0\) он загорается зеленым для машин на первой дороге и красным для машин на второй дороге. Далее, через \(g\) секунд он переключается на красный для машин на первой дороге и зеленый для машин на второй дороге, после чего через \(r\) секунд переключается обратно на зеленый для первой дороги, и т.д.

Таким образом, светофор горит зеленым для первой дороги в моменты времени \((k(r + g), \ k(r + g) + g)\) для целых \(k\) и зеленым для второй дороги
— в \((k(r + g) + g, (k + 1)(r+g)).\) Переключения же происходят в моменты \(k(r+g)\) и \(k(r+g)+g\). Когда светофор горит зеленым для первой дороги, по ней могут ехать машины, а по второй — нет, и наоборот. Будем считать что в момент переключения, могут проезжать машины с обеих дорог. Считается что машина проехала в момент переключения, если момент, когда она проехала, и момент переключения отличаются не более чем на \(10^{−5}\).

В соответствии с технической документацией период работы светофора зафиксирован и должен быть равен \(x\), иначе говоря, должно выполняться равенство \(r+g=x\). С соблюдением этого условия значения \(r\) и \(g\) можно выбрать любыми неотрицательными вещественными числами.

Для выбора оптимальных значений \(r\) и \(g\) было проведено исследование трафика на дорогах и получены следующие данные.

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

В момент \(0\) на первой дороге расположены \(n\) машин, \(i\)-я из них находится на расстоянии \(a_i\) метров от перекрестка и движется в его сторону со скоростью \(v_i\) м/с.

Аналогично, на второй дороге расположены \(m\) машин, \(i\)-я из них находится на расстоянии \(b_i\) метров от перекрестка и движется в его сторону со скоростью \(w_i\) м/с.

Чтобы пробок в городе было меньше, необходимо выбрать такие \(g\) и \(r\), чтобы максимальное число машин, которые одновременно стоят на перекрестке, было как можно меньше.

Помогите управлению дорожного движения выбрать оптимальные \(g\) и \(r\).

Ваня, Сережа и Дима любят физические нагрузки. Больше всего им нравится поднимать тяжести. Ребята очень давно начали заниматься гиревым спортом и уже собрали набор гирь для тренировок. Этот набор состоит из \(n\) гирь с различными целыми весами от \(1\) до \(n\).

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

Помогите спортсменам разделить набор из \(n\) гирь с весами \(1, \ 2, \ \dots, \ n\) на три равные по весу части.

У юного биолога Антона в красивой стеклянной колбе живут \(n\) бактерий.

Добавляя различные реактивы в колбу, Антон может контролировать число бактерий. Так, если \(p\) — некоторое простое число, то Антон умеет в домашних условиях получать вещество \(C_pH_{2p \ + \ 1}OH\), которое, будучи добавленным в колбу, уменьшает число бактерий ровно в \(p\) раз. Если же число бактерий не делилось на \(p\), то результат действия вещества не определен, и эксперимент теряет научную точность. Этого Антон допустить не желает, поэтому он применяет вещество \(C_pH_{2p \ + \ 1}OH\) только когда число бактерий делится на p.

Кроме того, у Антона на кухне есть неограниченный запас диэтиламида лизергиновой кислоты (\(C_{20}H_{25}N_{30}\)). При добавлении в колбу с бактериями диэтиламида лизергиновой кислоты, число бактерий возводится в квадрат.

Антон хочет, чтобы в колбе стало \(m\) бактерий. При этом он хочет добавлять какие-либо вещества в колбу наименьшее возможное число раз. Помогите ему сделать это.

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

В этот раз Борис задал Вове следующую головоломку: на шахматном поле размером \(8 \times 8\) клеток стоит одна шахматная фигура — конь. Необходимо расположить на поле еще две шахматные фигуры — ладью и слона, таким образом, чтобы они били коня, но не били друг друга, и конь не бил их. Так как Вова еще не очень силен в программировании, он попросил вас помочь ему с решением данной головоломки.

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

Ладья бьет те клетки, которые находятся на той же горизонтали или вертикали, что и она. Слон бьет те клетки, которые находятся на той же диагонали, что и он.