Задача A. (20081220) A + (-B)

Автор:Жюри зимних сборов 2009   Ограничение времени:1 сек
Входной файл:aplusminusb.in   Ограничение памяти:16 Мб
Выходной файл:aplusminusb.out  
Максимальный балл:50  

Формат входного файла

Во входном файле заданы два целых неотрицательных числа A и B (A,  B ≤ 1010 000), каждое на отдельной строке.

Формат выходного файла

В выходной файл выведите одно число, равное разности A и B.

Примеры тестов

Входной файл (aplusminusb.in) Выходной файл (aplusminusb.out)
1
5
3
2

Задача B. (20081220) Ботвинник и Фишер

Автор:Жюри зимних сборов 2009   Ограничение времени:15 сек
Входной файл:chess.in   Ограничение памяти:128 Мб
Выходной файл:chess.out  
Максимальный балл:50  

Условие

В неофициальном матче по шахматам встречаются шестой чемпион мира Михаил Ботвинник и одиннадцатый чемпион Роберт Фишер. Идёт сотая игра матча. Сделано уже больше сотни ходов. После десятого перерыва в партии Михаил и Роберт решили закончить партию максимально быстро, благо их не очень волновал её результат. К счастью, на доске осталось всего 4 фигуры. У каждого из гроссмейстеров осталось по одной тяжёлой фигуре (ладья или ферзь) и, естественно, королю. Игра считается законченной, когда один из королей заматован, или у каждой из сторон остался только король. В первом случае игрок, которого заматовали, проигрывает, а во втором объявляется ничья. Все другие правила окончания игры (в том числе правило троекратного повторения позиции и правило пятидесяти ходов) в этой партии отменены.

Ваша задача — найти самый быстрый способ закончить игру.

Формат входного файла

На первой строке находится описание позиции белых фигур, на второй — чёрных. Каждая фигура определяется тремя символами. Первый — это тип фигуры: K — это король, Q — ферзь, а R — ладья. Второй и третий символ содержат описание клетки, на которой стоит данная фигура, буква соответствует номеру вертикали, а цифра — горизонтали. Например, Ka1 обозначает, что король стоит в левой нижней клетке доски. Описания фигур внутри строки разделяются пробелом. Гарантируется, что позиция корректна. Право хода в данной позиции принадлежит чёрным. Первой фигурой в каждой строке является король.

Формат выходного файла

Выведите кратчайшую последовательность ходов, приводящую к концу игры. каждый ход записывается шестью символами: первый это название фигуры, следующие два это клетка, на которой фигура стояла до хода, четвёртый это дефис ('-'), а пятый и шестой — клетка, в которую фигура походила. Если оптимальных решений несколько разрешается вывести любое.

Примеры тестов

Входной файл (chess.in) Выходной файл (chess.out)
1
Ka1 Qb5
Ka3 Qa8
Qa8-a4
Qb5-b2
2
Ka1 Qf5
Ka3 Rh8
Rh8-f8
Qf5-f1
Rf8-f1

Задача C. (20081220) Деление уголком

Автор:Жюри зимних сборов 2009   Ограничение времени:2 сек
Входной файл:division.in   Ограничение памяти:64 Мб
Выходной файл:division.out  
Максимальный балл:50  

Условие

Вы отправились на машине времени в далёкое прошлое Франции с важной исторической миссией. Для укрепления своего положения в обществе Вам необходимо получить учёную степень.

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

Напишите программу, которая выводит процесс деления двух десятичных чисел уголком.

Формат входного файла

В двух строках входного файла заданы делимое и делитель, меньшие 10100.

Формат выходного файла

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

Примеры тестов

Входной файл (division.in) Выходной файл (division.out)
1
50082003928
491
50082003928 |491
491         +{-
2
239
717
239 |717
~~~~+{-
3
239
17
239 |17
17  +{-
4
667700
6677
667700 |6677
6677   +{-
5
12
7
12 |7
~7 +{-

Задача D. (20081220) Мультиплексор

Автор:Жюри зимних сборов 2009   Ограничение времени:2 сек
Входной файл:multiplexor.in   Ограничение памяти:256 Мб
Выходной файл:multiplexor.out  
Максимальный балл:50  

Условие

Мультиплексор в TestSys — это программа для одновременной организации контестов в разных местах с использованием TestSys. Например, если в одно и то же время проходят тренировки в Петергофе и Санкт-Петербурге, самый простой способ их организовать — с помощью мультиплексора. Тренировки по интернету тоже проводятся при помощи мультиплексора.

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

Конфигурационный файл мультиплексора состоит из нескольких разделов. Описание каждого раздела соответствует одному порту. Заголовок раздела состоит из одной строки вида:

A.port

где port — произвольное целое число между 0 и 65 535, а `.' означает произвольное количество пробелов (ASCII-код 32) и табуляций (ASCII-код 9). Для каждого порта определены некоторые правила. Описание каждого правила находится на отдельной строке, выглядящей так:

F.from.T.to[.I.id list][.P.password]

Квадратные скобки означают «может быть опущено», как и обычно. Параметр from может быть либо в форме IP , либо в форме IP/mask. В этой задаче IP всегда выглядит как a.b.c.d, где a, b, c и d — любые целые числа в интервале 0..255. mask — это целое число между 0 и 32, интерпретируется следующим образом. Каждый IP-адрес можно рассматривать как 32-битное двоичное число: a соответствует битам с 31 по 24 (старшие), b — битам с 23 по 16, c — с 15 по 8, d — с 7 по 0 (младшие). Эти биты записаны в обычном порядке, то есть, например, старший бит a является старшим битом всего числа, а младший бит d является младшим битом всего числа. Например, адрес 195.19.228.2 будет соответствовать двоичному числу 110000110001001111100100000000102=0xC313E402=3272860674 (или  − 1022106622, если рассматривать знаковый тип). Значение маски определяет количество значимых старших битов адреса. Остальные биты могут быть произвольными. Например, под 195.19.228.2/24 подходит любой адрес, начинающийся на 195.19.228 («195.19.228.*»), а 195.19.228.2/20 означает, что адрес должен быть в интервале 195.19.224.0--195.19.239.255. Если параметр mask опущен, маска считается равной 32 (все биты значимые). Пакет подходит под правило, если источник пакета находится в указанном диапазоне. Есть ещё три условия для того, чтобы пакет подошёл под правило. Во-первых, конечно, пакет должен быть получен через порт port, который указан в заголовке раздела. У всех разделов указаны разные порты. Ещё два правила — это правила соответствия идентификатора и пароля. Правило соответствия пароля очень простое: пароль, содержащийся в правиле, должен совпадать (с учётом регистра) с паролем к правилу (если правило не содержит пароля, любой принимается, если в пакете нету пароля, он принимается только в случае отсутствия пароля у правила). Пароль всегда состоит из не более, чем 64 букв и цифр. Правило соответствия идентификатора несколько сложнее. id list может иметь вид id или firstid-lastid. В первом случае необходимо точное совпадение id и id, указанного в пакете (с теми же оговорками, что и в правиле соответствия пароля, аналогично, идентификатор состоит из не более, чем 64 букв и цифр). Во втором случае firstid и lastid должны быть целыми числами одинаковой длины (ведущие нули разрешены). Пакет удовлетворяет правилу, если идентификатор, указанный в пакете имеет ту же длину, что и firstid и lastid, является числом и лежит между firstid и lastid включительно. Длины этих чисел во входном файле никогда не будут больше пяти. В случае, когда пакет удовлетворяет всем четырём условиям, он должен быть направлен хосту to, где to — IP-адрес (IP). Правила проверяются в порядке их следования. Как только найдено удовлетворяющееся правило, пакет немедленно перенаправляется и система переходит к обработке следующего пакета. Если пакет не подходит ни под одно правило, он перенаправляется в NULL device (то есть игнорируется).

Формат входного файла

Входной файл начинается с нескольких строк, описывающих конфигурацию мультиплексора. После последнего раздела идёт разделяющая строка, состоящая из трёх дефисов («---»). После этого начинаются пакеты. Пакеты описываются в том же виде, что и правила, с тремя исключениями: во-первых, в адресе источника не разрешается маска (mask), во-вторых, адрес назначения отсутствует (поскольку мы знаем, что этот пакет для нас), параметр to содержит номер порта, на который пришёл пакет, в-третьих, идентификатор не может быть указан в виде диапазона (firstid-lastid). В файле нет пустых строк. Количество разделов не менее одного и не более 32, и для каждого порта определено не менее одного и не более 32 правил. Количество пакетов не превышает 3000.

Формат выходного файла

Для каждого пакета выведите на отдельной строке адрес, на который его надо перенаправить. Если пакет перенаправлен в NULL device, выведите /dev/null вместо адреса.

Примеры тестов

Входной файл (multiplexor.in) Выходной файл (multiplexor.out)
1
A       12345
F       192.168.64.90/24   T       195.19.228.2
F       195.19.228.2       T       192.168.64.90   I       00-29
A       13456
F       195.19.228.2/28    T       195.19.228.213  P       passwd
F       0.0.0.0/0          T       195.19.228.2    I       ttt     P       secret
A       23917
F       1.2.3.4            T       195.19.228.2    I       1
{-}{-}{-}
F       192.168.64.239     T       12345           I       abc
F       192.168.65.0       T       12345
F       195.19.228.2       T       12345           I       1
F       195.19.228.2       T       12345           I       23      P       super
F       1.2.3.4            T       23917           I       01
F       1.2.3.4            T       23917           I       1
F       1.2.3.4            T       23917
F       195.19.228.16      T       13456           P       passwd
F       195.19.228.16      T       13456           I       ttt     P       passwd
F       195.19.228.16      T       13456           I       ttt     P       secret
F       195.19.228.15      T       13456           P       passwd
F       195.19.228.15      T       13456           I       ttt     P       passwd
195.19.228.2
/dev/null
/dev/null
192.168.64.90
/dev/null
195.19.228.2
/dev/null
/dev/null
/dev/null
195.19.228.2
195.19.228.213
195.19.228.213

Задача E. (20081222) Суммы без модуля

Автор:Пётр Митричев   Ограничение времени:3 сек
Входной файл:sum.in   Ограничение памяти:64 Мб
Выходной файл:sum.out  
Максимальный балл:100  

Условие

Участники сборов приезжают на сборы группами, и их необходимо заселить в гостиницу. Недолго думая, администратор гостиницы селит i-ю группу в комнаты с номерами с li по ri включительно, по одному человеку в комнату (соответственно, в i-й группе ri − li + 1 человек). Комнаты не резиновые, а именно вмещают лишь k − 1 человек. Как только в комнату заселяется k-й человек, все обитатели этой комнаты обижаются и уезжают домой (включая только что заселившегося).

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

Формат входного файла

В первой строке записаны три натуральных числа — число комнат n (1 ≤ n ≤ 100 000), характеристика вместимости комнаты k (2 ≤ k ≤ 5), и количество произошедших на сборах событий m (1 ≤ m ≤ 100 000). В последующих m строках описаны сами произошедшие события в хронологическом порядке, по одному на строке.

Каждое событие описывается тремя целыми числами. Заезд очередной группы участников описывается как "1 l r", где l и r задают диапазон номеров комнат для заселения (1 ≤ l ≤ r ≤ n). Очередной прием пищи описывается как "2 s t", где s и t (1 ≤ s ≤ t ≤ n) задают диапазон номеров комнат, приглашенных в столовую.

Формат выходного файла

На каждый запрос второго вида выведите количество кушающих участников на отдельной строке.

Примеры тестов

Входной файл (sum.in) Выходной файл (sum.out)
1
3 3 9
1 1 3
1 1 2
1 1 1
2 1 3
2 1 2
1 1 3
1 3 3
2 1 3
2 1 2
3
2
1
1

Задача F. (20081222) Разрезы

Автор:Илья Разенштейн   Ограничение времени:2 сек
Входной файл:cuts.in   Ограничение памяти:64 Мб
Выходной файл:cuts.out  
Максимальный балл:100  

Условие

Рассмотрим ориентированный взвешенный граф G = (V,E) с двумя выделенными вершинами s и t. Веса всех ребер — натуральные числа. Назовем s − t разрезом пару множеств вершин S и T такую, что выполняются следующие условия:

Назовем величиной разреза (S,T) суммарный вес ребер, которые направлены из S в T. Упорядочим все s − t разрезы G по неубыванию величины. Вам нужно вывести первые k разрезов в этом порядке.

Формат входного файла

В первой строке записаны два натуральных числа n и m — количество вершин и ребер в графе (1 ≤ n ≤ 50, 1 ≤ m ≤ 300). В следующих m строках находятся описания ребер — три натуральных числа a, b и c, которые задают ребро, идущее из вершины a в вершину b с весом c (1 ≤ a, b ≤ n, 1 ≤ c ≤ 109). Гарантируется, что в графе нет кратных ребер и петель (однако могут быть два ребра, направленные друг навстречу другу). Последняя строка содержит одно натуральное число k — количество разрезов, которые необходимо вывести (1 ≤ k ≤ 300, k не превосходит общее количество разрезов в графе).

Вершины s и t имеют номера 1 и n соответственно.

Формат выходного файла

Выведите искомые k разрезов по одному на строке. Разрез задается строкой, состоящей из n символов. i-й символ равен нулю, если вершина с номером i лежит в S, в противном случае i-й символ должен равняться единице. Если несколько разрезов имеют одинаковую величину, то вы можете вывести их в любом порядке.

Примеры тестов

Входной файл (cuts.in) Выходной файл (cuts.out)
1
6 6
1 2 1
2 3 2
2 4 3
3 5 3
4 5 2
5 6 1
16
011111
000001
011001
011101
010101
010001
011011
001001
000101
001011
010111
001111
000011
010011
000111
001101

Задача G. (20081222) Комната

Автор:Пётр Митричев (идея), Александр Калужин (текст)   Ограничение времени:2 сек
Входной файл:room.in   Ограничение памяти:64 Мб
Выходной файл:room.out  
Максимальный балл:100  

Условие

В комнате находятся N рядов стульев. На них необходимо усадить девочек и мальчиков следующим образом: в первом ряду должно располагаться ровно N человек, во втором — N − 1 человек, \dots, в N-м ряду будет один человек. То есть:

В первом ряду на каждом стуле может сидеть либо мальчик, либо девочка. В последующих рядах вводятся некоторые ограничения, а именно: на i-м месте ряда будет сидеть девочка тогда и только тогда, когда на предыдущем ряду на i-м и (i + 1)-м местах сидят две девочки или два мальчика. В противном случае на i-м месте будет сидеть мальчик.

Ваша задача — для заданного N вычислить максимальное возможное количество мальчиков при таких ограничениях.

Формат входного файла

В первой и единственной строке входного файла находится единственное натуральное число N (1 ≤ N ≤ 10101).

Формат выходного файла

Выходной файл должен содержать единственное число без ведущих нулей — ответ на поставленную задачу.

Примеры тестов

Входной файл (room.in) Выходной файл (room.out)
1
5
10
2
13
61

Задача H. (20081225) Палиндромное кодирование

Автор:Жюри зимних сборов 2009   Ограничение времени:2 сек
Входной файл:palin.in   Ограничение памяти:64 Мб
Выходной файл:palin.out  
Максимальный балл:100  

Условие

В одной секретной лаборатории разработали новый сверхсекретный способ архивации данных. Этот метод настолько уникален, что позволяет все данные сжимать примерно в 2 раза. Заключается он в следующем. Шифруемый файл представляется в виде последовательности из нулей и единиц. Потом из этой последовательности выбирается непустая подпоследовательность, которая является палиндромом. Затем из оставшейся части выбирается непустая последовательность, которая является палиндромом и т.д. Таким образом, из исходной последовательности остаётся только несколько палиндромов. Но ведь от палиндромов теперь можно хранить только одну половину!

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

Однако комиссия по проверке не согласилась принимать такой алгоритм, сказав, что программа архивации работает нестабильно и по-разному архивирует один и тот же файл. Для унификации был придуман следующий метод: изо всех способов разбить на минимальное число палиндромов выбирается такой, в котором первый палиндром лексикографически наименьший. Изо всех таких — тот, в котором второй наименьший. И так далее.

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

Формат входного файла

В первой и единственной строке входного файла содержится непустая строка из нулей и единиц длиной не более 3 000 000 символов.

Формат выходного файла

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

Примеры тестов

Входной файл (palin.in) Выходной файл (palin.out)
1
1001
1
1001

Задача I. (20081225) Б-деревья

Автор:Жюри зимних сборов 2009   Ограничение времени:5 сек
Входной файл:btrees.in   Ограничение памяти:64 Мб
Выходной файл:btrees.out  
Максимальный балл:100  

Условие

Если б дерево умело говорить...

Б-дерево — структура для хранения данных во вторичной памяти (например, на жёстком диске). Б-дерево обладает несколькими свойствами:

Обратите внимание, что корень может являться листом.

Два Б-дерева считаются различными, если они различны как графы с помеченными вершинами, или если вершина с одинаковыми пометками содержит различное количество ключей. Например, существует всего 8 различных Б-деревьев с четырьмя ключами и со степенью ветвления 2 (см. рисунок).

Посчитайте количество различных Б-деревьев с n ключами в листьях и степенью ветвления t.

Формат входного файла

В первой строке находятся два натуральных числа n и t — количество ключей в листьях и степень ветвления, соответственно (1 ≤ n ≤ 500, 2 ≤ t ≤ 109).

Формат выходного файла

В первой строке выведите единственное число без ведущих нулей — количество Б-деревьев с n ключами в листьях и степенью ветвления t.

Примеры тестов

Входной файл (btrees.in) Выходной файл (btrees.out)
1
4 2
8
2
20 2
17220826

Задача J. (20081225) Динамический массив

Автор:Жюри зимних сборов 2009   Ограничение времени:30 сек
Входной файл:dynarray.in   Ограничение памяти:512 Мб
Выходной файл:dynarray.out  
Максимальный балл:100  

Условие

Требуется реализовать структуру данных, которая представляет из себя динамический массив, поддерживающий следующие операции:

Элементы массива нумеруются с единицы.

Формат входного файла

В первой строке находятся два натуральных числа n и m — начальное количество элементов в массиве и количество операций (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000). Во второй строке находится n целых чисел a1, a2, , an  — элементы исходного массива (0 ≤ ai ≤ 106). Следующие m строк содержат описания операций в формате "1 u p" (u ≥ 1, u не превосходит текущего размера массива, 0 ≤ p ≤ 106), "2 u p" (u ≥ 0, u не превосходит текущего размера массива, 0 ≤ p ≤ 106) или "3 u v p" (1 ≤ u ≤ v, v не превосходит текущего размера массива, 0 ≤ p ≤ 106).

Формат выходного файла

В выходном файле должны находиться ответы на запросы  — по одному в строке.

Примеры тестов

Входной файл (dynarray.in) Выходной файл (dynarray.out)
1
5 5
1 3 5 4 2
3 2 4 4
1 3 3
3 2 4 4
2 2 10
3 2 4 4
2
3
2

Задача K. (20081226) Сумма цифр в строке

Автор:Жюри зимних сборов 2009   Ограничение времени:2 сек
Входной файл:digitsum.in   Ограничение памяти:64 Мб
Выходной файл:digitsum.out  
Максимальный балл:100  

Условие

Построим бесконечную последовательность строк S0, S1, S2, из двух символов — цифр 1 и 2 — следующим образом: S0 = 1; Si + 1 получается из Si одновременной заменой всех цифр 1 на строки 11212, а всех цифр 2 — на 1121212.

Так, S1 = 11212, S2 = 11212112121121212112121121212, .

Заметим, что каждая строка содержит в качестве префиксов все предыдущие.

Определим S как бесконечную последовательность цифр, содержащую в качестве префиксов все строки Si. Определим Srl как подстроку S, состоящую из всех её элементов с номерами от l до r, включительно. Например, S61 = 112121, S1717 = 2.

По данным числам l и r найдите сумму цифр в строке Srl.

Формат входного файла

Первая строка входного файла содержит целое число t (1 ≤ t ≤ 50000) — количество запросов. В следующих t строках записаны запросы; i-я из них содержит два целых числа li и ri, разделённых одним пробелом (1 ≤ li ≤ ri ≤ 109).

Формат выходного файла

Выведите в выходной файл t чисел, по одному числу на строке — ответы на запросы в том порядке, в котором они заданы во входном файле.

Примеры тестов

Входной файл (digitsum.in) Выходной файл (digitsum.out)
1
2
1 6
17 17
8
2

Задача L. (20081226) Разрез пополам

Автор:Жюри зимних сборов 2009   Ограничение времени:8 сек
Входной файл:half.in   Ограничение памяти:64 Мб
Выходной файл:half.out  
Максимальный балл:100  

Условие

Дан неориентированный граф из n вершин, где n чётно. Необходимо разбить вершины графа на два равных по размеру множества так, чтобы количество рёбер с концами в разных множествах было минимально.

Формат входного файла

Первая строка содержит два целых числа n и m — количество вершин и рёбер графа (2 ≤ n ≤ 30, n чётно).

Следующие m строк содержат описания рёбер — каждое ребро задано номерами своих концов. Вершины нумеруются с единицы. Гарантируется, что в графе нет кратных рёбер и петель.

Формат выходного файла

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

Примеры тестов

Входной файл (half.in) Выходной файл (half.out)
1
6 8
1 2
6 1
2 3
5 2
2 6
4 3
4 5
6 5
1 2 6

Задача M. (20081226) Следующая строка

Автор:Жюри зимних сборов 2009   Ограничение времени:2 сек
Входной файл:next.in   Ограничение памяти:64 Мб
Выходной файл:next.out  
Максимальный балл:100  

Условие

Назовём строку из нулей и единиц простой, если она лексикографически меньше любого своего собственного суффикса. Например, строка "00101" простая, а "00000" — нет (любой её собственный суффикс меньше всей строки).

Необходимо по простой строке найти следующую в лексикографическом порядке простую строку такой же длины.

Формат входного файла

Входной файл содержит простую строку длины n (2 ≤ n ≤ 104).

Формат выходного файла

В выходном файле должна находиться следующая в лексикографическом порядке простая строка длины n. Гарантируется, что она существует.

Примеры тестов

Входной файл (next.in) Выходной файл (next.out)
1
00111
01011

0.779s 0.015s 41