Жюри XVIII городской олимпиады школьников Санкт-Петербурга по информатике
Ограничение времени:
1 сек
Входной файл:
input.txt
Ограничение памяти:
64 Мб
Выходной файл:
output.txt
Условие
Привидение Петя любит играть со своими кубиками. Он любит выкладывать их в ряд и разглядывать свое творение.
Однако недавно друзья решили подшутить над Петей и поставили в его игровой комнате зеркало. Ведь всем известно,
что привидения не отражаются в зеркале! А кубики отражаются.
Теперь Петя видит перед собой N цветных кубиков, но не знает, какие из этих кубиков настоящие, а какие - всего лишь отражение в зеркале.
Помогите Пете! Выясните, сколько кубиков может быть у Пети. Петя видит отражение всех кубиков в зеркале и часть кубиков,
которая находится перед ним. Часть кубиков может быть позади Пети, их он не видит.
Формат входного файла
Первая строка входного файла содержит число N и количество различных цветов,
в которые могут быть раскрашены кубики - M.
Следующая строка содержит N целых чисел от 1 до M - цвета кубиков.
Формат выходного файла
Выведите в выходной файл в возрастающем порядке все такие K, что у Пети может быть K кубиков.
Имеется N кубиков, на гранях которых написаны буквы.
Требуется определить, можно ли из этих кубиков составить данное слово длиной K символов,
и если да, то вывести номера использованных кубиков.
При этом каждый кубик можно использовать только один раз.
Если решений несколько, выдать любое из них.
Формат входного файла
В первой строке входного файла содержится количество кубиков N.
Во второй строке — слово, в следующих N строках — по шесть символов без разделителей,
определяющих буквы на гранях кубиков. (Порядок букв не имеет значения).
Формат выходного файла
Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N,
задающих номера кубиков для каждой буквы слова, начиная с первой.
Если решения нет, выходной файл должен содержать единственное число 0.
Прямоугольная рамка была разрезана на N кусков.
Каждый кусок может представлять собой либо отрезок прямой, либо "уголок" — два отрезка,
соединённых под прямым углом.
По данным длинам отрезков требуется восстановить исходную рамку или определить,
что это невозможно.
Куски можно поворачивать, но нельзя отражать. Требуется использовать все куски.
Формат входного файла
Входной файл содержит число кусков N, за которым следуют N пар целых чисел aibi,
описывающих длину двух отрезков "уголка" i-го куска.
Если кусок является отрезком, то ai = 0 либо bi = 0.
Формат выходного файла
Выходной файл должен содержать два положительных целых числа WH —
ширину и высоту рамки, при этом W ≥ H.
Если решения не существует, следует выдать число − 1.
Если решений несколько, следует выдать решение с максимальным значением W.
I wish we had some way to handle it sanely, but I don't think a sane
solution to case-insensitivity exists.
Linus Torvalds
На компьютере под управлением операционной системы Linux
имеется каталог, содержащий N файлов.
Пользователю требуется скопировать эти
файлы на компьютер, работающий под управлением ОС Windows. К сожалению,
файловая система Windows имеет странное свойство. Несмотря на то, что
она сохраняет большие и малые буквы в именах файлов, имена,
отличающиеся только регистром букв, считаются одинаковыми.
Например, файлы с именами ChangeLog, CHANGELOG и changelog при копировании
на файловую систему Windows попадут в один и тот же файл.
Чтобы избежать потери данных, предлагается при копировании
переименовывать файлы по следующим правилам:
Файлы копируются в порядке перечисления в исходном каталоге.
Имена файлов считаются одинаковыми, если они совпадают с точностью до регистра.
Если при копировании очередного файла выяснилось, что
файл с таким именем уже был скопирован, то к имени текущего файла
добавляется суффикс "1".
Если имя, полученное после присоединения суффикса, также уже встречалось,
то перебираются суффиксы "2", "3", ..., "10", "11", ...
до тех пор, пока не найдётся суффикс, дающий уникальное имя.
Формат входного файла
Входной файл содержит количество имён N, за которым следует N строк с именами.
Имена состоят из латинских букв и цифр и имеют длину от 1 до M символов.
Формат выходного файла
Выходной файл должен содержать N строк с модифицированными именами файлов.
На шашечной доске размером N × N клеток расположены несколько белых и несколько черных шашек.
Горизонтали доски обозначены числами 1, 2, 3, … снизу вверх. (То есть первая строка входных данных описывает горизонталь доски с номером N, вторая N − 1 и т.д.)
Вертикали обозначены буквами a, b, c, … слева направо.
Клетка, таким образом, задается комбинацией из буквы и числа, например d12.
Ход шашки задается перечислением всех клеток, которые она посетила за этот ход,
включая начальную и конечную.
Обозначения клеток при этом разделяются знаком - (минус). Например: a1-c3-e1.
Шашка может побить (взять) шашку противоположного цвета,
"перепрыгнув" через нее по диагонали в любом направлении.
Если после этого имеется возможность взять еще одну шашку, то это можно сделать на том же ходу.
Требуется определить ход черных, соответствующий наиболее длинному взятию.
Если имеется несколько вариантов хода, выдать любой из них.
Формат входного файла
В первой строке входного файла содержится число N.
В следующих N строках — описание позиции, состоящее из символов '.' (точка),
'O' (заглавная латинская О),'X' (заглавная латинская X).
Они определяют пустую клетку, белую шашку и черную шашку соответственно.
Формат выходного файла
В выходном файле должна содержаться единственная строка вида
L1N1 − L2N2 − … − LKNK, где K ≥ 1,
или Impossible если взятие невозможно.
Центральным элементом набора из k чисел называется такой элемент, который
после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер
⌈k / 2⌉, считая с единицы).
Числа добавляются в изначально пустой набор в заданном порядке. Требуется определить
значения центрального элемента после добавления каждого числа.
Формат входного файла
Входной файла содержит количество чисел n, за которым следуют n целых чисел ai
в порядке их добавления в набор.
Формат выходного файла
Выходной файл должен содержать n целых чисел — значения центрального элемента после
каждого добавления.
Ник разрабатывает новый веб-сервер. В данный момент он работает над поддержкой списков контроля доступа.
Список контроля доступа позволяет запретить доступ к некоторым ресурсам на веб сайте на основании IP адреса пользователя.
Каждый IP адрес представляет собой четырехбайтовое число, записанное байт за байтом в десятичных числах, разделенных точками
"byte0.byte1.byte2.byte3". Каждый байт записан как десятичное число от 0 до 255 (включительно) без лидирующих нулей.
IP адреса собраны в IP сети.
IP сеть описывается двумя четерехбайтовыми числами — адресом сети и маской сети. Оба записываются в той же нотации, что и IP адрес.
Чтобы понять значение адреса сети и маски сети рассмотрим их двоичное представление.
Двоичное представление всех адресов состоит из 32 бит: 8 бит для byte0, далее 8 бит для byte1,
далее 8 бит для byte2, и затем 8 бит для byte3.
IP сеть содежрит набор из 2n IP адресов, где 0 ≤ n ≤ 32.
В маске сети всегда первые 32 − n бит установлены в 1, а n последних бит
установлены в 0 в двоичном представлении. Адрес сети имеет произвольные первые
32 − n бит, и n нулевых последних бит в двоичном представлении.
IP сеть содержит все IP адреса, чьи 32 − n первых
бит равны 32 − n первым битам адреса сети с произвольными n
последними битами.
Например, IP сеть с сетевым адресом 194.85.160.176 и сетевой маской
255.255.255.248 содержит 8 IP адресов от 194.85.160.176 до
194.85.160.183 (включительно).
IP сети обычно записываются как "byte0.byte1.byte2.byte3/s" где
"byte0.byte1.byte2.byte3" — это адрес сети, а s — количество бит
установленных в 1 в маске сети. Например, IP сеть из предыдущего абзаца записывается как 194.85.160.176/29.
Список котроля доступа содержит упорядоченный список правил. Каждое правило записано в одной из следующих форм:
"deny from <IP network>" — запрещает доступ к ресурсу любому IP из указанной IP сети.
"deny from <IP address>" — запрещает доступ к ресурсу указанному IP адресу.
"allow from <IP network>" — разрешает доступ к ресурсу любому IP из указанной IP сети.
"allow from <IP address>" — разрешает доступ к ресурсу указанному IP адресу.
Когда клиент запрашивает некоторый ресурс, его IP адрес сначала проверяется по списку контроля доступа.
Правила просматриваются в порядке их перечисления и применяется первое подходящее.
Если не подходит ни одно из правил, доступ разрешается.
Дан список котроля доступа и списовк запрашивающих IP адресов, найдите для каждого запроса, будет ли
разрешен доступ к ресурсу.
Формат входного файла
В первой строке входого файла содержится n — количество правил в списке контроля доступа.
Следующие n строк содержат правила по одному в строке.
IP сеть всегда обозначается как "byte0.byte1.byte2.byte3/s".
Следующая строка содержит m — количество IP адресов для проверки.
Следующие m строк содержат IP адреса для проверки по одному в строке.
Формат выходного файла
Для каждого запроса выведите 'A' если доступ к ресурсу будет открыт,
либо 'D' в противном случае. Выведите все ответы в одной строке, НЕ разделяйте их пробельными символами.
Ограничения
0 ≤ n ≤ 100000, 1 ≤ m ≤ 100000.
Примеры тестов
№
Входной файл (access.in)
Выходной файл (access.out)
1
4
allow from 10.0.0.1
deny from 10.0.0.0/8
allow from 192.168.0.0/16
deny from 192.168.0.1
5
10.0.0.1
10.0.0.2
194.85.160.133
192.168.0.1
192.168.0.2
На входе в университет висит огромная прямоугольная доска объявлений размером
h × w (h — высота, а w — ширина). Доска — это место, где вывешиваются всевозможные объявления
о ближайших контестах, изменениях в меню столовой и другая важная информация.
Первого сентября доска была пустой. Один за одним добавлялись объявления.
Каждое объявление — это полоска бумаги единичной высоты. Более точно,
i-ое объявление — это прямоугольник размером 1 × wi.
Когда кто-либо добавляет новое объявление на доску, он всегда выбирает
самую высокую возможную позицию для объявления. Среди всех возможных
самых высоких позиций он выбирает самую левую.
Если для нового объявления нет места, оно не помещается на доску.
Даны размеры доски и объявлений, ваша задача — найти номера рядов, в которые будут помещены объявления.
Формат входного файла
Первая строка входного файла содержит три целых числа h, w,
и n — размеры доски и количество объявлений.
Каждая из следующих n строк содержит целое число wi — ширину i-ого объявления.
Формат выходного файла
Для каждого объявления (в порядке, данном во входном файле)
выведите одно число — номер ряда, в который помещается объявление.
Ряды занумерованы от 1 до h, начиная с верхнего ряда.
Если объявление не может быть помещено на доску, выведите "-1" для этого объявления.
Доктор Странный действительно странный. На каждой лекции он вычисляет заполненность класса и если она маленькая,
уменьшает все оценки в семестре на 1. Поэтому студенты хотят максимизировать заполненность класса.
Заполненность класса — это минимум из заполненности рядов и заполненности колонок.
Заполненность колонок — это максимальное количество студентов в одной колонке,
а заполненность рядов — максимальное количество студентов в ряду.
Например, есть 16 студентов, изображенных на картинке слева (занятые парты
темные). Заполненность рядов этого расположения составляет 5 (
в четвертом ряду), а заполненность колонок 3 (1, 3, 5, 6 колонки).
Итак, заполненность класса равна 3. Но если студенты
пересядут как показано на картинке справа, то заполненность колонок
станет равна 4 (5-ая колонка), и тогда заполненность класса также станет равна 4.
Студентам Доктора Странного необходимо знать расположение, которое максимизирует
заполненность класса, поэтому они просят вас написать программу которая ее вычислит.
Формат входного файла
В первой строке входного файла содержатся три числа: n, r и c — количество студентов, рядов и колонок в классе.
Формат выходного файла
В первой строке выходного файла должно содержаться одно число — максимальная возможная заполненность класса.
Следующие r строк должны содержать оптимальное расположение студентов.
Каждая строка должна содержать описание одного ряда. Описание ряда — это строка из
c символов, либо ".", либо "#", где "."
означает пустую парту, а "#" — заполненную.
Если допустимо несколько оптимальных расположений, выведите любое.
