Информатика

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

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

Правила игры

Игра происходит на стандартной доске (8х8), которая располагается так, что у игрока, играющего белыми, левая нижняя клетка является черной, и с нее начинается нумерация как строк, так и столбцов. Строки доски нумеруются числами от 1 до 8, столбцы — латинскими буквами от a до h.
 

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

В начале игры каждый из двух игроков имеет по 12 шашек своего цвета (белого или черного соответственно). Белые шашки располагаются на клетках a1, a3, b2, c1, c3, d2, e1, e3, f2, g1, g3, h2. Черные шашки располагаются на клетках a7, b6, b8, c7, d6, d8, e7, f6, f8, g7, h6, h8.

Игроки совершают ходы по очереди. Игрок, играющий белыми, ходит первым.

Шашки в процессе игры бывают двух видов: обычная шашка и дамка. В начале игры все шашки обычные. Белая шашка становится дамкой, если она оказывается в строке 8. Соответственно, черная шашка становится дамкой, если она оказывается в строке 1.

Шашка может совершать ходы двух типов:

1. Простой ход заключается в перемещении одной из шашек на одну клетку вперед по диагонали. Например, белая шашка с e3 может сходить на d4 или f4 (если соответствующая клетка свободна). А черная шашка с e3 может сходить на d2 или f2.

2. Рубка заключается в том, что шашка перепрыгивает через шашку (или дамку) противника, находящуюся в диагонально соседней с ней клетке при условии, что следующая клетка этой диагонали свободна. Шашка противника, которую срубили, убирается с доски. Если сразу после окончания рубки та же самая шашка может продолжить рубку, она ее продолжает этим же ходом. Рубка возможна в любом из 4-х диагональных направлений. Если в процессе рубки шашка оказывается в 1-й строке (для черных) или в 8-й (для белых), она становится дамкой.

Дамка может совершать следующие ходы:>

3. Простой ход заключается в перемещении дамки по диагонали на любое число клеток (при этом все клетки, через которые происходит перемещение, должны быть свободны).

4. Рубка заключается в том, что шашка перепрыгивает через шашку (или дамку) противника, находящуюся на той же диагонали, что и рубящая дамка. Это можно делать при условии, что все клетки между рубящей дамкой и шашкой, которую рубят, а также клетка, следующая за шашкой, которую рубят, свободны. После рубки дамка может встать на любую клетку данной диагонали за клеткой, на которой стояла срубленная шашка (при условии, что все клетки на ее пути свободны). Если из своего нового положения дамка может совершить рубку, она должна ее совершить этим же ходом.

Входные данные
В первой строке входного файла записано одно число N — количество ходов, которое было сделано с начала партии. Это количество не превышает 1000.

В каждой из следующих N строк записаны описания ходов (нечетные ходы совершались белыми, четные — черными). Описание каждого хода занимает ровно одну строку и записывается в следующем виде.

Простой ход записывается в виде <начальная клетка>–<конечная клетка>. Например, ход с c3 на d4 записывается как c3-d4.

Рубка записывается в виде <начальная клетка>:<клетка после рубки>. Если рубка продолжается, то ставится еще одно двоеточие, и записывается клетка, где окажется шашка после следующей рубки и т.д. Например, e3:c5:e7 (шашка, изначально расположенная на e3, рубит шашку на d4 и оказывается на c5, после чего рубит шашку на d6 и оказывается на e7).

Рубка a1:h8 может быть осуществлена только дамкой (например, дамка с a1 рубит шашку, стоящую в c3, и заканчивает ход в h8). Рубка дамкой может быть и такой a1:d4:f6:h4 (дамка рубит шашку, стоящую на b2, затем продолжает рубку и рубит шашку на e5, и, наконец, рубит шашку на g5). При этом после каждой рубки указывается клетка, на которой останавливается дамка перед следующей рубкой.

Строки с описанием ходов не содержат пробельных символов.

Выходные данные
В выходной файл выведите изображение доски с расположенными на ней шашками. В первой строке выходного файла должна быть выведена 8-я строка доски, во второй — 7-я и т.д. В каждой строке должно быть ровно 8 символов, описывающих клетки столбцов с a по h.

Белая клетка должна быть изображена символом “.” (точка), пустая черная клетка — символом “–“ (минус). Черная клетка, в которой стоит белая шашка — символом “w” (маленькая латинская буква w), а клетка с белой дамкой — символом “W” (заглавная латинская буква W). Аналогично клетка с черной шашкой должна быть изображена символом “b” (маленькая латинская буква b), а клетка с черной дамкой — символом “B” (большая латинская буква B)

Алеша Попович и Добрыня Никитич сражаются со стаей двух- и трехголовых драконов. Они по очереди взмахивают мечами, и одним махом могут отрубить любое (по своему желанию) число голов, но только у одного дракона. Отрубивший последнюю голову у последнего дракона получает в жены прекрасную принцессу.

Кто из богатырей (начинающий или второй) может получить в жены принцессу независимо от действий другого?

Входные данные
Во входном файле записано два числа N и M — количество двух- и трехголовых драконов соответственно (оба числа целые из диапазона от 0 до 100).

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

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

Дополнительные баллы начисляются участнику, если его программа прошла все тесты.

Участник может исправлять свое решение, и посылать его на проверку повторно (при этом решение проверяется на том же наборе тестов). При этом за каждую попытку из количества набранных по задаче баллов вычитается штраф, который равен 0 при 1-й попытке, а при каждой следующей возрастает на 2 (то есть 2 при второй, 4 — при третьей, 6 — при четвертой и т.д.).

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

Например, если участник делает первую попытку и набирает 10 баллов, его результат по задаче равен 10 баллов. Пусть на второй попытке участник посылает решение, которое набирает 8 баллов. С учетом штрафа за эту попытку участник имеет 6 баллов, однако результат команды по задаче остается равным 10. Пусть с 3-й попытки решение набрало 20 баллов, тогда (с учетом штрафа) результат участника по задаче становится равен 16 баллам. Наконец, пусть с 4-й попытки решение проходит все тесты, тогда участник получает сумму баллов за все тесты, плюс призовые баллы за прохождение всех тестов, минус 6 баллов штрафа (если, конечно, эта величина не меньше 16 баллов, которые уже были у данного участника).

Напишите программу, которая определяет результат данного участника по этой задаче.

Входные данные
Во входном файле записано сначала число N — количество тестов, на которых проверяются решения данной задачи (1≤N≤100). Далее идет N натуральных чисел, не превышающих 100, — баллы, которые начисляются за прохождение каждого из тестов. Далее идет целое число из диапазона от 0 до 100 — количество баллов, которое дополнительно начисляется за прохождение всех тестов.

Далее идет натуральное число M — количество попыток сдачи задачи (1≤M≤100). После чего идет M наборов по N чисел в каждом, задающих результаты проверки каждой из M попыток сдачи задачи на тестах. 0 обозначает, что соответствующий тест не пройден, 1 — пройден.

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

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

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

После этого ведущий задал участнику вопрос: какое наименьшее число секторов может быть на барабане? Напишите программу, отвечающую на этот вопрос.

Входные данные
Во входном файле записано сначала число N — количество чисел, которое назвал ведущий (2 ≤ N ≤ 30000). Затем записано N чисел, на которые указывала стрелка в процессе вращения барабана. Первое число всегда совпадает с последним (в конце стрелка указывает на тот же сектор, что и в начале). Числа, записанные в секторах барабана, — натуральные, не превышающие 32000.

Выходные данные
Выведите минимальное число секторов, которое может быть на барабане.

Как и в обычном тетрисе, поле в игре Strategy Tetris представляет собой "стакан" шириной в W клеток (1<W<10⁹) и бесконечной высоты. В этот стакан падают сверху N фигурок (1<N<100000). i-я фигурка представляет собой прямоугольник шириной в W_i клеток и высотой в одну клетку; самая левая клетка фигурки имеет абсциссу ai (1<a_i<W–W_i+1). Фигурки падают по обычным правилам: если при падении фигурка хотя бы одной своей клеткой ложится на какую-либо уже упавшую фигурку, то ее движение прекращается.

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

На рисунке ниже приведен пример заполнения стакана фигурками из примера входных данных (порядок заполнения соответствует выходному файлу, приведенному в примере).



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

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

На плоскости задано N векторов – направленных отрезков, для каждого из которых известны координаты начала и конца (вектор, у которого начало и конец совпадают, называется нуль-вектором, можно считать, что нуль-вектор лежит на любой прямой, которая через него проходит). Введем следующие три операции над направленными отрезками на плоскости:

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

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

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

Заметим, что если складываемые векторы противоположно направлены и имеют одну и ту же длину, то результатом их сложения является нуль вектор.

3) В любой точке плоскости можно породить два противоположно направленных отрезка равной (в том числе и нулевой) длины:

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

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

Входные данные
В первой строке записано число N – количество заданных векторов (1 < N ≤ 1000). В каждой из следующих N строк через пробел записаны четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты – целые числа, по модулю не превосходящие 1000.

Выходные данные
В первой строке следует записать число M – количество векторов в полученной системе (1 ≤ M ≤ N). В каждой из следующих M строк через пробел должны находиться четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты – вещественные числа, записанные с 6 цифрами после точки.

Как показывает опыт, для создания успешной футбольной команды важны не только умения отдельных её участников, но и сплочённость команды в целом. Характеристикой умения игрока является показатель его профессионализма (ПП). Команда является сплочённой, если ПП каждого из игроков не превосходит суммы ПП любых двух других (в частности, любая команда из одного или двух игроков является сплоченной). Перед тренерским составом молодёжной сборной Москвы была поставлена задача сформировать сплочённую сборную с максимальной суммой ПП игроков (ограничений на количество игроков в команде нет).

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

Входные данные
В первой строке записано целое число N (1≤N≤30000). В последующих N строках записано по одному целому числу P_i (0≤P_i≤60000), представляющему собой ПП соответствующего игрока.

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

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

Информация, записанная на билете, кодируется K числами (0 или 1). При этом непосредственно на билете записывается последовательность из N чисел (N>=K) так, что числа, записанные на расстоянии K, совпадают. Таким образом, для проверки подлинности билета достаточно проверить, что все числа на расстоянии K совпадают. К сожалению, при считывании информации с билета иногда могут происходить ошибки — считается, что одно из чисел может исказиться (то есть 0 заменится на 1, или 1 — на 0). Такой билет все равно нужно считать подлинным. Во всех остальных случаях билет считается поддельным.

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

Входные данные
В первой строке входного файла записаны числа N и K (1<=N<=50000, 1<=K<=1000, K<=N). Во второй строке записано N чисел, каждое из которых является 0 или 1 — информация, считанная с билета.

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

По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит "Мы с радостью продадим Вам метр ткани за P_i бурлей, однако если Вы купите не менее R_i метров, то получите прекрасную скидку — каждый купленный метр обойдется Вам всего в Q_i бурлей". Чтобы воплотить в жизнь лозунг "экономика страны должна быть экономной", правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:

1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;

2) магазин номер i готов продать ему не более F_i метров ткани.

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

Входные данные
В первой строке записаны два целых числа N и L (1≤N≤100, 0≤L≤100). В каждой из последующих N строк находится описание магазина номер i — 4 целых числа P_i, R_i, Q_i, F_i (1≤Q_i≤P_i≤1000, 1≤R_i≤100, 0≤F_i≤100).

Выходные данные
Первая строка должна содержать единственное число — минимальное необходимое количество бурлей.

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

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

После того, как к удивлению тётушки Полли, её забор был покрашен, она поручила Тому Сойеру обновить краску на плитках, которыми был вымощен их квадратный двор. Двор был покрыт NxN одинаковыми квадратными плитками, каждая из которых когда-то давно была покрашена в один из K цветов (K<N). Краска на плитках потускнела и Тому Сойеру поручили их покрасить, на этот раз в один любой цвет (из тех же К цветов). Покрасить нужно все плитки, в том числе и те, которые уже были покрашены в этот цвет раньше.

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

Входные данные
В первой строке записаны через пробел два числа: N — количество плиток в одном ряду (1<N≤200) и K (1≤K<N). В каждой из следующих N строк записаны N натуральных чисел, обозначающих номера цветов красок, в которые когда-то были выкрашены соответствующие плитки данного горизонтального ряда. Номера цветов — натуральные числа в диапазоне от 1 до K.

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

Если перекрасить все плитки, следуя придуманным Томом правилам, нельзя, выведите два раза число 0.

Рассмотрим бесконечную клетчатую бумагу. Покрасим некоторые узлы сетки в черный цвет, а остальные будем считать белыми. Узел V< называется внутренним, если он внутренний по вертикали и внутренний по горизонтали. Узел внутренний по горизонтали, если слева и справа от V расположены по крайней мере по одному черному узлу. Узел внутренний по вертикали, если сверху и снизу от V расположены по крайней мере по одному черному узлу.

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

Входные данные
Первая строка содержит одно целое число n (0 ≤ n≤ 100 000) – количество черных узлов в начале. Каждая из следующих n строк содержит два целых числа – координаты очередного черного узла, по модулю не превосходящие 10⁹.

Выходные данные
Выведите число черных вершин после окончания всех перекрасок. Если процедура никогда не закончится, то выведите –1.

Когда археологи проводили раскопки в древних городах Майя, они обнаружили множество непонятных иероглифов. Пример иероглифа показан справа, он обозначает имя Кьак-у-пакал, это имя военного и религиозного лидера в древнем городе Майя Чичен-Итца (см. А.В.Восс, Г. Дж.Кремер Кьак-у-пакал, Хун-пик-токь и Коком). Этот иероглиф можно увидеть во многих местах древнего города.

Вообще говоря, иероглифы Майя не являются иероглифами в прямом смысле этого слова, а, скорее, являются композицией отдельных глифов. Все известные глифы занумерованы целыми числами от 1 до 9999. Учеными был разработан специальный язык, с помощью которого можно представлять иероглиф в виде обычного текста. Например, иероглиф Кьак-у-пакал кодируется как “((669:604).(586:(27:(534.534))))”.

Приведем формальную грамматику этого языка:

<block> ::= <glyph id>|'('<block>'.'<horizontal group>')'|'('<block>':'<vertical group>')'

<horizontal group> ::= <block>['.'<horizontal group>]

<vertical group> ::= <block>[':'<vertical group>]

Код иероглифа описывает процесс его составления. Глифы комбинируются горизонтально и вертикально (с помощью ':' и '.') в блоки, которые, в свою очередь, комбинируются во все большие и большие блоки, до тех пор, пока не будет достигнута нужная конфигурация.

Как обычно, в процессе реализации забыли о важной части — обратном восстановлении обычного текста в иероглиф. Это предстоит сделать вам.

Входные данные
Единственная строка входного файла содержит строку, описывающую иероглиф Майя в виде обычного текста. Длина строки не превышает 255 символов. Строка не содержит пробелов.

Выходные данные
Выведите текст, составленный из символов '+', '-', '|', ' ' (ASCII коды 43, 45, 124, 32), '0'..'9' и переводов строки. Все блоки одной группы должны иметь одинаковый размер. Номер глифа (glyph id) с одним пробелом перед ним, должен быть помещен в левый верхний угол блока. Вывод должен быть как можно короче. Гарантируется, что для всех тестов существует изображение, содержащее максимум 100 000 байт.

Определите кодовое расстояние между двумя двоичными кодами длины D

Входные данные
Сначала вводится число D – длина кодов (целое, положительное, не превышает 100), затем вводятся два кода, каждый в своей строке.

Выходные данные
Выведите одно число –расстояние между этими кодами.

Наиболее известная игра, дошедшая до нас из Японии – это Судоку. Новая игра должна затмить ее славу. Про нее известно следующее. Нам дан квадрат, разделенный сеткой на n×n клеток, а каждая клетка содержит картинку одного из k типов. Игрок должен переместить их, чтобы получить максимально возможное число одинаковых первых рядов (два ряда считаются одинаковыми, если оба заполнены одинаковыми картинками и в одинаковом порядке). По виду таблицы определите, сколько одинаковых рядов в ней можно сложить (если менять картинки как угодно).

Например, если нам дана такая таблица:

одно из результирующих состояний в игре будет:

Входные данные
Первая строка входных данных содержит два числа n (1≤n≤40000) и k (1≤k≤50000). Каждая из следующих k строк содержит число картинок в таблице каждого из k типов. Все числа больше 0, их сумма в точности равна n².

Выходные данные
Выведите в первой строке максимальное количество одинаковых рядов, которые можно построить из этих картинок. В следующих n строках выведите содержание таких рядов: в каждой строке должно находиться одно число – номер соответствующей картинке в порядке ее появления во входных данных. Если решений несколько, выведите любое из них.

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

К сожалению, ими нельзя покрыть пол комнаты полностью, так как она имеет форму выпуклого многоугольника. Фил хочет минимизировать непокрытую часть пола, располагая ковры оптимальным образом.

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



Входные данные
Первая строка входных данных содержит два целых числа n и r — число углов в комнате (3 ≤ n ≤ 100) и радиус ковров (1 ≤ r ≤ 1000, оба ковра имею один и тот же радиус). Следующие n строк содержат по два числа x_i и y_i — координаты i-го угла  \((–1000 \le x_i; y_i \le 1000)\) . Углы описаны в порядке обхода комнаты по часовой стрелке. Координаты углов различны и соседние стены не коллинеарны.

Выходные данные
Выведите   \(x_1, y_1, x_2, y_2\), где(\(x_1, y_1\)) и (\(x_2, y_2\)) обозначаю центры ковров. Координаты должны иметь точность не менее 4 цифр после точки. Выведите любое оптимальное расположение. Входные данные гарантируют, что решение существует (Фил не стал бы покупать ковер, который не помещается в комнату).

Даша имеет n ювелирных украшений. Каждое украшение имеет стоимость wi и значимость для Даши vi. В связи с финансовым кризисом Даша решила продать некоторые украшения и сохранить только k из имеющихся. Чтобы решить, что именно сохранить, Даша вводит параметр важности для набора из выбранных k украшений, который вычисляет по следующей формуле:
\(\frac{\sum_{j=1}^k v_i}{\sum_{j=1}^k w_i}\)

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

Входные данные
Первая строка ввода содержит числа n – количество ювелирных изделий у Даши и k – количество ювелирных изделий, которые планируется оставить (1 ≤ k ≤ n ≤ 100000).

В следующих n строках содержатся по два числа – v_i и w_i (0 ≤ v_i ≤ 10⁶,1≤w_i≤10⁶, обе суммы всех значений vi и wi не превосходят 10⁷ каждая).

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

Введем следующие операции надо прямоугольной таблицей символов. Пусть нам дана матрица А, состоящая из m строк (первый индекс) и n столбцов (второй индекс). Определим результирующую матрицу В для каждой из операций следующим образом:

• Транспозиция относительно главной диагонали (код операции '1'): B_j,i=A_i,j
• Транспозиция относительно другой диагонали (код операции '2'): B_n-j+1,m-i+1=A_i,j
• Горизонтальное отражение (код операции 'H'): B_m-i+1,_j=A_i,j
• Горизонтальное отражение (код операции 'V'): B_i,n-j+1=A_i,j
• Поворот на 90 ('A'), 180 ('B'), или 270 ('C') градусов по часовой стрелке: B_j,m-i+1=A_i,j (для 90º)
• Поворот на 90 ('X'), 180 ('Y'), или 270 ('Z') градусов против часовой стрелки: B_n-j+1,i=A_i,j (для 90º)

Вам дана последовательность не более 100000 операций над исходной матрицей. Выведите полученную в результате этих операций матрицу.
Входные данные
В первой строке входных данных находятся значения m и n (0<m,n≤300). В каждой из следующих m строк находятся по n печатных символов (т.е. не используются символы с кодами от 33 до 126).

Последняя строка содержит описание операций, которые были выполнены над этой матрицей, путем записи без пробелов из кодов. Операции выполняются по порядку слева направо.

Выходные данные
Выведите сначала два целых числа − число строк и столбцов в результирующей матрице. Затем выведите саму матрицу в том же формате, что и во входных данных.

Напишите программу, моделирующую работу детерминированного конечного автомата (ДКА). Описание автомата и входная строка вводятся на стандартном потоке ввода. Результат работы автомата над данной строкой выводится на стандартный поток вывода.

Входные данные
Описание автомата задаётся в следующей форме. Сначала задаётся функция перехода автомата. Функция перехода задаётся в виде троек CUR CHAR NEW, где CUR — идентификатор исходного состояния — произвольная символьная строка, не содержащая пробельные символы. CHAR — символьная строка длиной ровно 1 символ. NEW — идентификатор целевого состояния — произвольная символьная строка, не содержащая пробельные символы. Элементы описания перехода могут отделятся друг от друга произвольным количеством пробельных символов. Описание функции перехода завершается строкой "END" в качестве идентификатора исходного состояния. Элементы CHAR и NEW отсутсвуют.

Далее перечисляются заключительные состояния автомата. Каждое состояние — это символьная строка. Список состояний завершается символьной строкой "END". Далее задаётся начальное состояние автомата — символьная строка. Затем задаётся проверяемое слово — символьная строка. Все элементы входного файла могут отделяться друг от друга произвольным количеством пробельных символов. Можете предполагать, что входные данные корректны, то есть удовлетворяют спецификации и действительно задают детерминированный конечный автомат.

Выходные данные
Результат работы автомата должен быть напечатан в следующем виде. Сначала напечатайте число 1, если данный автомат допускает данную цепочку, и 0 в противном случае. Затем напечатайте количество символов, прочитанных во входной цепочке к моменту принятия автоматом решения. Наконец, напечатайте идентификатор состояния, в котором в данный момент находился автомат.

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

Для своих клиентов, играющих на рынке ценных бумаг, компания "WebMarket" решила открыть значения этого показателя и более того, автоматизировать покупку ценных бумаг с заданным порядковым номером по значению надежности. Аналитики проанализировали идею, и решили, что наличие такого функционала будет способствовать привлечению новых клиентов на рынок "WebMarket", повышению объемов сделок, а значит, и повышению прибылей "WebMarket". Важно также отметить, что торговля на базе этого показателя может позитивно сказаться на российском фондовом рынке и cделать его более здоровым. Алгоритмы оценки надежности уже написаны, средства выделены, необходимая реклама проведена. Осталось только написать сам код.

Ценные бумаги в базе данных имеют три атрибута:

• code — непустая строка латинских символов и цифр длины 30 или меньше
• id — целочисленный идентификатор (начиная с 0)
• reliability — целое число из диапазона [−2³¹,2³¹)

.
Каждой новой ЦБ выдается следующий по порядку id и значение её надёжности устанавливается в 0. Если ценная бумага отзывается с рынка, ее id для новых бумаг не используется.

База данных получает запросы, которые позволяют вводить новые ЦБ на рынок, получать текущую информацию о ЦБ, отзывать ЦБ с рынка, менять значение надежности у ЦБ и находить ЦБ, которая стоит на n-м месте, если упорядочить ЦБ по убыванию надежности, а при одинаковых значениях по возрастанию идентификатора.

При добавлении ЦБ с кодом, который раньше встречался, но соответствующая ЦБ была отозвана с рынка, ей назначается новый идентификатор.

Входные данные
Первая строка входа содержит число запросов N. (1≤N≤100000). Затем идут N  строк, каждая из которых содержит один запрос. Запросы бывают 4 типов:

• ISSUE code: добавить новую ЦБ code в базу данных, или вывести информацию о ЦБ, если она уже есть в базе
  • если ЦБ code существует, то вывести EXISTS id reliability
  • если ЦБ code не существует, то вывести CREATED id 0
• DELETE code: удалить ЦБ code из базы
  • если ЦБ code существует, то вывести OK id reliability
  • если ЦБ code не существует, то вывести BAD REQUEST
• RELIABILITY code reliability: увеличить количество очков ЦБ, гарантируется, что значение останется в диапазоне [−2³¹,2³¹)
  • если ЦБ code существует, то вывести OK id new_reliability
  • если ЦБ code не существует, то вывести BAD REQUEST
• FIND n: найти n-ю ЦБ (начиная с 0)
  • если база не пуста, найти ЦБ, которая имела бы порядковый номер n (нумерация начинается с 0), если все ЦБ упорядочить сначала по убыванию баллов, а группы ЦБ с одинаковыми баллами упорядочить по времени их добавления (то есть по возрастанию id); а если n больше, чем количество ЦБ в базе, то найти последнюю ЦБ в этом порядке; для обоих случаев вывести OK code id reliability
• если база пуста, то вывести EMPTY

Выходные данные
Таким образом, на каждый запрос на входе нужно вывести одну строку с результатом.