#113680

Квадродерево

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2011, Задача F ]

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

Опишем суть этой структуры данных. Квадродерево позволяет нам представлять в памяти таблицу размера \(2^n \times 2^n\) , состоящую из нулей и единиц. Все дерево состоит из ячеек, каждая ячейка отвечает за некоторую часть этой таблицы, при этом каждая часть является квадратом со стороной \(2^p\) . Первая ячейка отвечает за всю таблицу.

Если все элементы квадрата, за который отвечает ячейка, имеют одинаковое значение (\(0\) или \(1\)), то в ячейке просто хранится эта информация. Если же внутри квадрата существуют хотя бы два различных элемента, то весь квадрат делится на четыре непересекающихся квадрата со стороной \(2^{p−1}\) , после чего для каждой четверти создается отдельная ячейка, и ссылки на все четыре созданных ячейки записываются в ячейку, отвечающую за большой квадрат.

Правильное квадродерево для данной таблицы. Любой квадрат, у которого все четыре стороны выделены, является ячейкой квадродерева. Всего используется \(13\) ячеек.

Далеко не всегда подобный способ хранения таблицы приводит к сокращению объема памяти. Но не во всех задачах требуется абсолютно точно хранить всю таблицу, не потеряв значения ни одного элемента. Иногда можно потерять часть информации. А именно, разрешается изменить значения не больше, чем \(k\) элементов таблицы.

Выясните, какое минимальное возможное количество ячеек может быть в квадродереве, описывающем таблицу, получающуюся из данной изменением не более, чем \(k\) элементов.

Входные данные

Первая строка входного файла содержит два целых числа \(t = 2^n\) и \(k\) — размер таблицы и максимальное количество измененных ячеек соответственно (\(2 \le t \le 128, \ 1 \le k \le t^2\) ).

Гарантируется, что \(t\) является степенью двойки.

Следующие \(t\) строк содержат по \(t\) символов, каждый из которых является \(0\) или \(1\). Эти строки описывают заданную таблицу.

Выходные данные

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

Пояснения к примеру

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

Для ее хранения с помощью квадродерева необходимо \(9\) ячеек: одна для всей таблицы, четыре для четырех квадратов \(2 \times 2\), три из них содержат \(0\), а четвертый, соответствующий нижнему правому углу, разбивается еще на четыре.

Примеры

Входные данные

Выходные данные

#113681

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2011, Задача G ]

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

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

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

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

Входные данные

Первая строка входного файла содержит два числа \(n\) и \(k\) — количество шпаг, имеющихся у ученых, и минимальный возраст, необходимый для того, чтобы со шпаги можно было сделать копию (\(1 \le n \le 100 000, \ 1 \le k \le 10^8\)). Следующая строка содержит \(n\) чисел: \(a_1, \ a_2, \ \dots \ , \ a_n\), где \(a_i \ \ (0 \le a_i \le 10^9\) ) — возраст \(i\)-й шпаги.

Выходные данные

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

Если экземпляр является первой изготовленной шпагой, то выведите для соответствующей шпаги число \(0\).

Если возможных решений несколько, выведите любое.

Если ученые ошибаются, и не существует последовательности, в которой копии шпаг могли бы быть изготовлены, выведите единственное число \(−1\).

#113682

Светофор

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2011, Задача H ]

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

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

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

Светофор устроен следующим образом. В момент времени \(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\).

Входные данные

В первой строке задано вещественное число \(x \ (1 \le x \le 10^4 )\), с не более чем тремя знаками после десятичной точки. Во второй строке задано число
\(n \ (0 \le n \le 100 000)\) — количество машин на первой дороге. Далее, в \(n\) строках задано описание машин на первой дороге. Описание каждой машины состоит из двух вещественных чисел \(a_i\) и \(v_i\) — расстояния от машины до перекрестка и ее скорости, соответственно (\(1 \le a_i , \ v_i \le 10^4).\) Числа \(a_i\) и \(v_i\) заданы не более, чем с тремя знаками после десятичной точки.

В следующей строке задано число \(m \ (0 \le m \le 100 000, \ 1 \le n \ + \ m \le 100 000)\) — количество машин на второй дороге. Далее, в \(m\) строках задано описание машин на второй дороге. Описание каждой машины состоит из двух вещественных чисел \(b_i\) и \(w_i\) — расстояния от машины до перекрестка и ее скорости, соответственно \((1 \le b_i, \ w_i \le 10^4).\) Числа \(b_i\) и \(w_i\) заданы не более, чем с тремя знаками после десятичной точки.

Никакие две машины исходно не находятся в одной точке. Оба списка машин даны в порядке возрастания расстояния до светофора.

Выходные данные

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

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

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

Пояснения к примерам

В первом примере все машины подъезжают к перекрестку в момент \(1\). Сделав переключение светофора как раз в этот момент можно обеспечить проезд всех машин без ожидания.

Во втором примере на первой дороге ситуация развивается следующим образом. Сначала через \(1/15\) секунды третья машина догоняет вторую и ей приходится снизить скорость до \(5\) м/с. Затем они вместе догоняют первую машину в момент \(0.5\), им обеим приходится снизить скорость до \(1\) м/с. Так вместе они и подъезжают к перекрестку через \(2\) секунды после начала движения.

На второй дороге машины движутся с равной скоростью и подъезжают к перекрестку через 1, 5 и 7 секунд после начала движения, соответственно. При любом выборе \(g\) и \(r\) хотя бы одной машине придется ждать. Оптимально выбрать любое значение \(g\) от \(2\) до \(3\), включительно. В этом случае ждать будут первая и вторая машины на второй дороге, но одновременно на перекрестке будет находиться не более одной машины. Если выбрать \(g < 2\), то придется ждать трем машинам на первой дороге, а если выбрать \(g > 3\), то вторая и третья машины на второй дороге будут одновременно ждать на перекрестке.

Примеры

Входные данные

2.0
1
1.0 1.0
2
1.0 1.0
2.0 2.0

Выходные данные

0 1.000000000000000 1.000000000000000

Входные данные

4.0
3
2.0 1.0
4.0 5.0
5.0 20.0
3
1.0 1.0
5.0 1.0
7.0 1.0

Выходные данные

1 2.000000000000000 2.000000000000000

#113683

Гири

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2011, Задача I ]

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

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

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

Входные данные

Входной файл содержит единственное целое число \(n \ (1 \le n \le 100 000)\) — количество гирь.

Выходные данные

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

Если разбить все гири на три равных по весу множества нельзя, выведите «Impossible».

Если существует несколько решений, можно вывести любое.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

Impossible