Информатика

На плоскости задано 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), затем вводятся два кода, каждый в своей строке.

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

По введенному натуральному числу K, не превосходящему 1 000 000, выдать K-ое по счету простое число.

Входные данные
Во входном файле находится одно натуральное число K.

Выходные данные
В выходной файл выведите K-е простое число.

Наиболее известная игра, дошедшая до нас из Японии – это Судоку. Новая игра должна затмить ее славу. Про нее известно следующее. Нам дан квадрат, разделенный сеткой на 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 цифр после точки. Выведите любое оптимальное расположение. Входные данные гарантируют, что решение существует (Фил не стал бы покупать ковер, который не помещается в комнату).

Что такое функция в контексте программирования на C++?

1. Набор операторов, выполняемых случайным образом.
2. Повторно используемая последовательность операторов, предназначенная для выполнения определенной работы.
3. Уникальный набор операторов, который можно использовать только один раз.
4. Способ хранения данных в памяти программы.
5. Команда для завершения работы программы.
6. Механизм для создания графического интерфейса.

Даша имеет 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

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

На шахматной доске (8x8) стоит одна белая шашка. Сколькими способами она может пройти в дамки?

(Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

Входные данные
Вводятся два числа от 1 до 8: номер столбца (считая слева) и номер строки (считая снизу), где изначально стоит шашка.

Выходные данные
Вывести одно число - количество путей в дамки.

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

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

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

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

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

Входные данные
Вводится одно число N (0<=N<=30).

Выходные данные
Вывести N строк треугольника Паскаля (числа выводятся через пробел).