Вершины отрезка AB имеют координаты (Xa; Ya) и (Xb; Yb).
Требуется найти координаты вершин отрезка A * B * (X * a; Y * a) и (X * b; Y * b),
полученного путём поворота отрезка AB вокруг точки O(Xo; Yo) на β градусов.
Формат входного файла
Входной файл содержит целые числа Xa, Ya, Xb, Yb, Xo, Yo, β
Формат выходного файла
Выходной файл должен содержать четыре вещественных числа X * a, Y * a, X * b, Y * b с точностью 10 − 3.
Владивостокский программист приглашает коллегу к себе домой в гости на празднование Хэллоуина.
Оба программиста живут за городом.
Их дома расположены в точках с координатами (XA; YA) и (XB; YB).
В этом районе есть только одна асфальтированная дорога, представимая в виде отрезка с координатами
начала (XS; YS) и конца (XE; YE). Дорога является платной: за
любой въезд на дорогу (проезд по произвольному участку дороги или только пересечение —
не имеет значения) взимается плата в размере CR.
Остальная местность занята полями, которые
(в связи со скорым Хэллоуином) сплошь засажены тыквами.
При движении на автомобиле по полю взимается
плата в размере CF за каждый километр пути — ущерб за раздавленные тыквы.
Помогите программисту добраться к другу с минимальными затратами.
Обратите внимание, при сколь угодно малом приближении к дороге плата за въезд на неё не взимается.
Смотрите пример №3.
Формат входного файла
Во входном файле содержатся десять целых чисел: XAYAXBYBXSYSXEYECFCR
Формат выходного файла
Выходной файл должен содержать единственное число —
минимальные затраты при перемещении из A в B с абсолютной ошибкой не более 10 − 3.
Ограничения
− 103 ≤ XA, YA, XB, YB, XS, YS, XE, YE ≤ 103
1 ≤ CF ≤ 103
1 ≤ CR ≤ 106
Дома программистов находятся в разных точках и не находятся на дороге
Два радара, расположенные в точках с координатами (0, 0) и (100, 0),
обнаружили неопознанный объект.
По таинственной причине, связанной, возможно, с внеземной природой объекта,
радары оказались способны определить только направление на объект (пеленг),
но не расстояние до объекта.
Пеленг измеряется в градусах, против часовой стрелки,
начиная от направления "на восток"
(т. е. пеленг второго радара относительно первого равен 0°,
пеленг первого радара относительно второго — 180°).
Требуется найти координаты НЛО или определить, что это невозможно.
Формат входного файла
Во входном файле содержатся вещественные числа a и b, разделенные пробелами.
Формат выходного файла
В выходном файле должны содержаться два вещественных числа, x и y,
представляющие координаты объекта с точностью до 4 знаков после запятой.
Если определить координаты невозможно, следует вывести два числа 0 (нуль).
"Дети, нарисуйте в тетрадях квадрат" — сказала учительница.
Вася поставил на листе бумаги четыре точки, соединил их с помощью линейки.
Получился квадрат... ну, или во всяком случае какой-то четырёхугольник.
Васин сосед Петя согласился помочь исправить рисунок. За время,
пока учительница подойдёт для проверки Васиной работы, Петя успеет
стереть и перерисовать только одну вершину четырёхугольника.
Требуется написать программу, которая найдёт нужную вершину и
её новые координаты или определит, что это невозможно.
Формат входного файла
Входной файл содержит вещественные числа x1y1x2y2x3y3x4y4 —
координаты вершин четырёхугольника, перечисленные в порядке обхода.
Формат выходного файла
Выходной файл должен содержать числа Mxy, где целое M —
номер вершины, которую следует перенести (1 ≤ M ≤ 4),
а вещественные (x, y) — её новые координаты, c абсолютной ошибкой не более 10 − 3.
Если решения не существует, вывести единственное число 0 (ноль).
Если существует несколько решений, вывести решение с наименьшим значением M.
Пифагор заказал ремесленнику изготовить несколько прямоугольных треугольников
из ценных пород дерева для использования на занятиях по геометрии,
но ремесленник перепутал размеры, и треугольники получились не прямоугольные.
Чтобы не выбрасывать испорченный ценный материал,
ремесленник решил переделать получившиеся треугольники в прямоугольные,
постаравшись максимизировать их площади.
Напишите программу, которая по размерам сторон треугольника
находит максимальную площадь прямоугольного треугольника,
который можно вырезать из этого треугольника.
Формат входного файла
В первой строке входного файла содержится три числа,
разделенных пробелами — длины сторон треугольника.
Формат выходного файла
В первой строке выходного файла вывести
одно число — максимальную площадь прямоугольного треугольника,
получаемого из заданного треугольника, с точностью 10 − 5.
На уроке рисования ученики первого класса
Марсианской средней школы учились изображать землян и марсиан.
Рисунок как землянина, так и марсианина состоит из окружности и пяти отрезков.
Назовём отрезок торчащим из окружности,
если один его конец лежит внутри или на границе окружности,
а другой — снаружи.
Правильный рисунок марсианина должен состоять из окружности,
изображающей голову, с 5 торчащими отрезками, изображающими щупальца.
Правильный рисунок землянина должен состоять из окружности,
изображающей голову, с 1 торчащим отрезком, изображающим туловище.
Остальные 4 отрезка, изображающие руки и ноги,
должны иметь хотя бы одну общую точку с "туловищем" и лежать строго снаружи "головы".
Напишите программу, которая по данному рисунку определит,
кто на нём изображён.
Формат входного файла
Входной файл содержит описание окружности, состоящее из трёх целых чисел
xcycr — координаты центра и радиус.
Далее идут пять описаний отрезков, каждое из четырёх целых чисел
x1y1x2y2 — координаты начала и конца отрезка.
Формат выходного файла
Выходной файл должен содержать единственную строку:
TERRAN, если на рисунке землянин,
MARTIAN, если на рисунке марсианин
и UNKNOWN, если нарисовано ни то, ни другое.
Требуется написать программу, которая получает невзвешенный неориентированный граф и выводит все его вершины в порядке увеличения расстояния от данной вершины S.
Расстояние между вершинами A и B это длина кратчайшего пути из A в B.
Если есть несколько вершин, находящихся на одном и том же расстоянии от вершины S,
выведите их в произвольном порядке.
Формат входного файла
Входной файл содержит три целых числа N, M и S, где M — число рёбер, S — номер стартовой вершины.
Вершины пронумерованы целыми числами от 1 до N.
Каждая из следующих M строк содержит пару целых чисел — номера вершин, соединённых ребром.
Формат выходного файла
Выходной файл должен содержать последовательность из N номеров вершин, упорядоченных по возрастанию расстояния от S.
Если какая-то из вершин недостижима из S, выведите единственное число − 1.
Лабиринт размером N x N клеток задан массивом символов.
Символ '#' обозначеет стену, символ '.' — проход.
Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.
Требуется найти длину кратчайшего пути между левым верхним и
правым нижнем углами или определить, что пути не существует.
Формат входного файла
Первая строка входного файла содержит размер лабиринта N.
Следующие N строк содержат по N символов — описание лабиринта.
Формат выходного файла
Выходной файл должен содержать единственное целое число — длину кратчайшего пути,
либо −1, если пути не существует
Ограничения
1 ≤ N ≤ 1500, левый верхний угол лабиринта всегда свободен.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
details.in
Ограничение памяти:
256 Мб
Выходной файл:
details.out
Условие
Предприятие «Авто-2010» выпускает двигатели для известных
во всем мире автомобилей. Двигатель состоит ровно из n деталей,
пронумерованных от 1 до n, при этом деталь с номером i
изготавливается за pi секунд.
Специфика предприятия «Авто-2010» заключается в том,
что там одновременно может изготавливаться лишь одна деталь двигателя.
Для производства некоторых деталей необходимо иметь предварительно
изготовленный набор других деталей.
Генеральный директор «Авто-2010» поставил перед предприятием
амбициозную задачу — за наименьшее время изготовить деталь с номером 1,
чтобы представить ее на выставке.
Требуется написать программу, которая по заданным зависимостям порядка
производства между деталями найдет наименьшее время,
за которое можно произвести деталь с номером 1.
Система оценивания
Решения, правильно работающие только для тестов, в которых n не превосходит 10,
будут оцениваться из 40 баллов.
Решения, правильно работающие только для тестов, в которых n не превосходит 100,
будут оцениваться из 60 баллов.
Решения, правильно работающие только для тестов, в которых n не превосходит 1000,
будут оцениваться из 80 баллов.
Формат входного файла
Первая строка входного файла содержит число n — количество деталей двигателя.
Вторая строка содержит n натуральных чисел p1, p2… pn,
определяющих время изготовления каждой детали в секундах.
Каждая из последующих n строк входного файла описывает характеристики
производства деталей. Здесь i-ая строка содержит число деталей ki,
которые требуются для производства детали с номером i, а также их номера.
Известно, что не существует циклических зависимостей в производстве деталей.
Формат выходного файла
В первой строке выходного файла должны содержаться два числа:
минимальное время (в секундах), необходимое для скорейшего производства
детали с номером 1 и число k деталей, которые необходимо для этого произвести.
Во второй строке требуется вывести через пробел k чисел — номера деталей
в том порядке, в котором следует их производить
для скорейшего производства детали с номером 1.
Хакер Вася решил собрать карманный персональный компьютер (КПК).
Согласно найденной им в Интернет инструкции компьютер собран правильно тогда,
когда ток из каждой микросхемы может пройти в каждую и притом единственным путем.
Вася собрал компьютер, но сомневается в правильности сборки. Напишите программу,
которая по данному Васей описанию схемы определит,
какие провода нужно удалить, какие оставить и
какие придется добавить, чтобы компьютер был собран правильно.
Так как Васе не хочется выполнять много работы, он просит вас удалять и добавлять провода
таким образом, чтобы суммарное число добавленных и удаленных проводов было минимально.
Формат входного файла
Входной файл содержит числа N и M — соответственно число микросхем и проводов в КПК, за
которыми следуют M пар чисел aiaj, означающие, что i-ая и j-ая микросхемы
соединены проводом. Ток по проводу может течь в любом направлении.
Формат выходного файла
Выходной файл содержит сначала число K1 — количество проводов, которые нужно оставить в схеме,
затем K1 пар чисел aiaj — описание проводов. После этого следует
число K2 — число проводов, которые нужно добавить в схему,
затем K2 пар чисел aiaj — описание проводов.
Если решений несколько, выведите любое из них.
Отдел инновационных технологий фирмы "Division Computers" решил, что повысить
производительность в написании программ можно, если использовать модульное
программирование, т.е. когда когда каждый программист пишет свою часть отдельно.
Когда все программисты сдали в отдел свою работу, выяснилось, что
некоторым модулям для правильного функционирования требуются другие модули, при
этом если i-тому модулю нужен j-тый, то и наоборот j-тому модулю нужен i-тый.
Вам, как одному из программистов отдела, поручено написать программу, которая
по сведениям о связях между модулями определила бы, сколько минимальных программ можно
из них собрать. Минимальной считается программа, которую нельзя разделить на более мелкие части.
Формат входного файла
Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за
которыми следуют M пар чисел aiaj, означающие, что i-тый и j-тый модули
не могут функционировать друг без друга.
Формат выходного файла
Выходной файл должен содержать число получившихся после сборки программ.
Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела.
Как известно, количество денег в копилке можно определить, только разбив ее.
Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.
Друг подсказал Васе, что можно оценить минимальное количество денег в копилке,
зная вес пустой копилки и вес копилки с монетами.
Дано E — вес пустой копилки, F — вес копилки с монетами,
N — количество достоинств монет,
Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N).
Требуется определить минимальную сумму, которая может содержаться в копилке.
Формат входного файла
В первой строке входного файла содержатся числа EFN.
В следующих N строках находятся по два числа — CiWi.
Все числа во входном файле — целые.
Формат выходного файла
В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке.
Если заданный вес копилки F не может быть достигнут с монетами заданного типа,
то в выходной файл следует записать число − 1.
Однажды Марфа Геннадьевна выиграла в лотерею большую сумму денег и решила
потратить часть выигрыша на благотворительность.
Чтобы определить, сколько денег отдать на благотворительность, Марфа
Геннадьевна придумала игру. Она записала N чисел a1, a2, ..., aN
по кругу (по часовой стрелке).
Начинает Марфа Геннадьевна с числа a1.
Начальная сумма денег равняется a1.
Затем Марфа Геннадьевна кидает игральный кубик (на разных гранях кубика
нарисовано 1, 2, 3, 4, 5 и 6 точек). Если на кубике выпало число x,
то Марфа Геннадьевна отсчитывает x чисел по часовой стрелке.
Например, если выпало число 3, то Марфа Геннадьевна
перейдёт от числа a1 к числу a4.
Число, к которому перешла Марфа Геннадьевна, прибавляется к сумме.
Марфа Геннадьевна бросает кубик M раз и каждый раз прибавляет
очередное число к сумме.
Марфе Геннадьевне интересно, какая наибольшая сумма денег может
получиться при такой игре, поэтому ей нужна программа, вычисляющая
наибольшую сумму.
Формат входного файла
Входной файл содержит целые числа NM, за которыми следуют N
целых чисел a1a2... aN.
Формат выходного файла
Требуется вывести в выходной файл целое число — максимальную сумму.
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
Формат входного файла
Первая строка входного файла содержит заданный шаблон длиной не более 80 символов.
Формат выходного файла
Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2 * 109.
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
????(?
2
Задача I. Наибольшая общая подпоследовательность
≡
You are to write a program that receives a weighted directed graph and finds
distances from source vertex S to all other vertices. Distance from S to
some vertex W is the minimal length of path going from S to W.
Length of path is the sum of weights of its edges.
Vertices are numbered with integers from 1 to N.
Input file format
First line of input file contains three integers NM and S,
where M is the number of edges. Next M lines contain three
integers each —
starting vertex number, ending vertex number and weight of some edge respectively.
All weights are positive.
There is at most one edge connecting two vertices in every direction.
Output file format
Output file must contain N integers — distances from
source vertex to all vertices.
If some vertices are not reachable from S, corresponding numbers must be −1.
Constraints
1 ≤ N ≤ 1000.
All weights are less or equal than 1000.
You are to write a program that receives a weighted directed graph and finds
all distances from fixed vertex S to all other vertices. Distance from S to
some vertex W is the minimal length of path going from S to W. Length of path
is the sum of weights of its arcs.
Input file format
Input file contains two integers N, M and S.
Vertices are numbered with integer numbers from 1 to N. S is the number of
source vertex. M is the number of arcs. Each of next M lines contain three
integers — numbers of starting and ending vertices of some arc and its weight
respectively. All weights are positive. There is at most one arc connecting
two vertices in every direction.
Output file format
Output file must contain N numbers. Each I-th number is the distance from
vertex S to vertex I. If some vertices are not reachable from S, corresponding
numbers must be −1.
Constraints
1 ≤ N, M ≤ 100000
All weights are less or equal 1000.
You are to write a program that finds shortest distances from vertex S
to all other vertices in a given directed weighted graph.
Graph consists of N vertices, numbered from 1 to N, and M edges.
Input file format
Input file contains two integers NMS, followed my M triplets of integers
ui vi wi — starting vertex, ending vertex and weight or the edge.
There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.
Output file format
Output file must contain a vector of N integers — distances from vertex S to other vertices.
The distance from any vertex to itself is considered to be 0.
If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.
Constraints
0 ≤ N, M ≤ 1000.
All weights are less than 1000 by absolute value.
Однажды учитель физкультуры решил провести на уроке новое упражнение.
Ученики выполняют упражнение в парах. При этом важно, чтобы рост
учеников в паре отличался не более чем на k сантиметров.
Учитель построил перед собой класс из n учеников.
Однако выяснилось, что ребята встали не по росту, а в некотором произвольном порядке.
Не желая тратить время на перепостроение, учитель решил действовать по следующему алгоритму.
Он находит в строю пару стоящих рядом учеников, рост которых
отличается не более чем на k сантиметров и отправляет их выполнять упражнение.
Это действие учитель повторяет до тех пор, пока такие пары существуют.
Если таких пар нет, оставшиеся в строю ученики отправляются играть в волейбол.
Помогите учителю выбрать пары таким образом, чтобы их получилось как можно больше.
В первом примере имеется 7 учеников. Учитель может вызвать учеников 2 и 3
(их рост 175 и 170, разница не превосходит k = 5),
после чего они выйдут из строя, и останутся ученики с номерами 1, 4, 5, 6, 7.
Вторую пару составляют ученики 1 и 4, имеющие нулевую разницу в росте (рост обоих равен 180).
Ученики с номерами 5 и 7 имеют один и тот же рост 200,
но учитель не может их вызвать, поскольку они стоят не рядом друг с другом.
Если бы учитель вызвал сначала учеников 1 и 2, то оставшиеся ученики не смогли бы
образовать ни одной пары.
Система оценивания
Рекомендуется рассмотреть следующие частные случаи:
n < 4;
k = 0;
Формат входного файла
Во начале входного файла записаны целые числа n и k.
Далее следует n целых чисел hi. Число hi обозначает рост ученика,
стоящего в строю i-ым.
Формат выходного файла
Первым числом выходного файла должно быть количество найденных пар p.
Далее должно следовать p пар чисел, обозначающих исходные номера учеников,
отправляющихся выполнять упражнение, в порядке их вызова учителем.
You are to write a program that finds shortest distances between all pairs
of vertices in a directed weighted graph.
Graph consists of N vertices, numbered from 1 to N, and M edges.
Input file format
Input file contains two integers N and M, followed my M triplets of integers
ui vi wi — starting vertex, ending vertex and weight or the edge.
There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.
Output file format
Output file must contain a matrix of size NxN.
Element in the j-th column of i-th row mush be the shortest distance between
vertices i and j.
The distance from the vertex to itself is considered to be 0.
If some vertex is not reachable from some other,
there must be empty space in corresponding cell of matrix.
Constraints
0 ≤ N ≤ 100.
All weights are less than 1000 by absolute value.
Студент Вася каждый день ездит на машине в университет учиться. Система дорог города, в котором живет
Вася, представляет собой на карте прямоугольную сетку состоящую из N × M перекрестков.
Дом, от которого отъезжает Вася, находится в левом верхнем углу карты, а университет — в правом нижнем углу.
Все перекрёстки снабжены светофорами, работающими в необычном режиме.
По всем направлениям перекрёстка одновременно горит либо зелёный, либо красный свет.
Вася уже давно ездит по этим дорогам и для каждого светофора знает все промежутки времени, когда он светит красным.
Итак, Васе нужно успеть на первую пару! Но Вася — порядочный гражданин и не станет проезжать на красный свет.
В то же время, скорость автомобиля и состояние дорог в городе позволяют ему перемещаться
между светофорами настолько быстро, что временем перемещения можно пренебречь.
(Т. е. время проезда между перекрёстками равно нулю).
Определите такой маршрут до университета, чтобы время прибытия было минимально возможным.
Формат входного файла
Входной файл содержит 2 целых числа NM.
Далее следует N × M расписаний светофоров, перечисленных в порядке обхода карты построчно.
Первое число i − го расписания ci — количество временных отрезков i − го светофора,
за которым следует ci пар целых чисел — временные отрезки, когда i − ый светофор светит красным.
Отрезки не пересекаются и отсортированы по возрастанию левой границы.
Формат выходного файла
Выходной файл должен содержать единственное целое число — момент времени, когда Вася приедет в университет.
You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.
Input file format
Input file contains two integers N, M.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three
integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are
positive. There is at most one edge connecting two vertices.
Output file format
Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree,
output file must contain −1.
Constraints
1 ≤ N, M ≤ 100000
All weights are less or equal 1000.
You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.
Input file format
Input file contains two integers N, M.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three
integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are
positive. There is at most one edge connecting two vertices.
Output file format
Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree,
output file must contain −1.
Constraints
1 ≤ N ≤ 1000
All weights are less or equal 1000.
Компания-разработчик компьютерных игр решила выпустить обновлённую версии
классической аркадной игры Lode Runner.
Игра проходит в лабиринте, состоящем из горизонтальных платформ, соединённых лестницами.
Лабиринт изображается в виде поля шириной W и высотой H клеток, каждая клетка
которого содержит один из символов "." (ASCII 46) — свободное место,
"X" (ASCII 88) — платформа и "#" (ASCII 35) — лестница.
По правилам игры, все платформы должны быть строго горизонтальными и не соприкасаться друг с другом
(т.е. два символа "X" могут соседствовать только по горизонтали).
Каждая лестница должна быть строго вертикальной и соединять две платформы
(т.е. представлять собой вертикальную полосу из символов "#",
над верхним и под нижним символом которой находятся символы "X").
Лестницы могут соприкасаться друг с другом, находясь на соседних вертикалях.
Из каждого символа платформы должна быть возможность перейти к любому другому символу,
двигаясь только по платформам по горизонтали и лестницам по вертикали.
Таким образом, непосредственное перемещение с одной лестницы на другую,
а также между платформой и соседней по горизонтали лестницей невозможно.
Когда разработка игры подходила к концу, из компании неожиданно уволился дизайнер уровней.
Изучив результаты его работы, руководитель проекта выяснил, что
дизайнер успел правильно расположить платформы, но символы, обозначающие лестницы,
были расставлены им как попало.
Поскольку времени на поиск нового дизайнеры уже не оставалось, было решено
доработать имеющиеся уровни, заменив некоторые символы "." на "#" или наоборот.
После этой доработки все лестницы должны соответствовать правилам игры.
Кроме того, чтобы максимально сохранить первоначальный замысел дизайнера,
количество замен следует минимизировать.
Требуется написать программу которая по данному описанию уровня игры
строит уровень, соответствующий правилам и получающийся из данного
минимально возможным количеством замен символов "." и "#" друг на друга.
Формат входного файла
Первая строка входного файла содержит целые числа WH.
Следующие H строк содержат по W символов каждая — описание уровня.
Формат выходного файла
Выходной файл должен содержать H строк по W символов каждая — исправленное описание уровня.
Если оптимальных решений несколько, выведите любое из них.
Гарантируется, что хотя бы одно решение существует.
На заводе по сборке матрешек установлен автомат для их упаковки. Принцип его действия таков.
Изначально на столе стоит N неупакованных матрешек, пронумерованных от 1 до N, причем вторая матрешка
может вкладываться в первую, третья во вторую, четвертая в третью и т.д. матрешка с большим номером может вкладываться
в матрешку с меньшим.
За один такт автомат может взять две матрешки и вложить меньшую в большую, причем если в матрешках
уже содержаться другие матрешки, то они все вкладываются в самую большую, при этом номера матрешек остаются прежними.
Если матрешка уже вложена в другую, то автомат упаковывает ту матрешку в которую она вложена.
Программа автомата состоит из чисел N, K и следующих за ними K пар чисел ai, bi — номера матрешек, которые автомат
упакует за i-тый такт.
По заданной программе автомата для каждой матрешки определите номер самой большой матрешки в которую она оказалось
вложенной после завершения программы.
Формат входного файла
Во входном файле содержатся два числа NиK, в следующих K строках находится программа автомата.
Формат выходного файла
В выходном файле должно содержаться N чисел — для каждой матрешки номер самой большой матрешки,
в которую она оказалось вложенной.
Клуб программистов еженедельно проводит тренировки для всех желающих.
Каждая тренировка завершается поеданием вкусной пиццы.
На одной из таких тренировок пицца разделена на N различных по размеру кусочков.
Но разделена не полностью — все кусочки всё ещё соединены расплавленным сыром.
В связи с этим, чтобы взять какой-то кусочек, нужно отрезать его от соседей.
Так как пицца имеет форму круга, у каждого из кусочков есть ровно два соседа.
Участники тренировки выстраиваются в очередь за пиццей в порядке занятых мест.
Так как интенсивное программирование пробуждает аппетит, каждый участник берёт кусочек пиццы наибольшего размера из всех оставшихся.
Если наибольший кусочек всё еще соединён со своими соседями, участник отрезает его.
Леонид — очень талантливый программист, поэтому он может занять на тренировке любое место, какое пожелает.
Леонид также очень ленив, поэтому он не хочет самостоятельно отрезать себе пиццу.
Помогите Леониду понять, какой наибольший кусочек пиццы он может получить, чтобы ему не пришлось отрезать этот кусочек от соседних.
Формат входного файла
Входной файл содержит целое число N — количество кусочков, на которые разделена пицца.
Далее следует N различных целых чисел ai — размеры кусочков пиццы, перечисленные в порядке обхода по кругу.
Формат выходного файла
Выходной файл должен содержать единственное целое число — размер наибольшего кусочка пиццы, который может достаться Леониду.
Ограничения
1 ≤ N ≤ 105
1 ≤ ai ≤ 109
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
n
1
21
1 ≤ n ≤ 3
2
31
1 ≤ n ≤ 103
1
3
48
1 ≤ n ≤ 105
1, 2
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Данная задача — тест. Требуется ответить на приведённые вопросы и отправить ответ в тестирующую систему в указанном ниже формате.
За каждый правильный ответ будут начисляться баллы.
Баллы за все вопросы, кроме нулевого, будут видны после окончания тура.
Вопрос 0
Сколько будет 2 + 4?
Вопрос 1
На диаграмме показано количество участников олимпиады по трём предметам в трёх регионах России
Какая из диаграмм правильно отражает соотношение участников из всех регионов по каждому предмету?
Вопрос 2
Сколько шестерок в семеричной записи числа 3432019 + 24012022 - 343?
Вопрос 3
Укажите наименьшее основание системы счисления, в которой запись числа 321 трёхзначна.
Вопрос 4
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(0) = 4, F(1) = 1
F(n) = F(n − 1) ⋅ 6 + F(n − 2) ⋅ 4, при n ≥ 2
Чему равно значение функции F(7)? В ответе запишите только натуральное число.
Вопрос 5
У Дмитрия есть доступ к сети Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 220 бит в секунду. У Глафиры нет скоростного доступа в Интернет, но есть возможность получать информацию от Дмитрия по телефонному каналу со средней скоростью 212 бит в секунду. Глафира договорилась с Дмитрием, что он скачает для него данные объемом 10 Мбайт по высокоскоростному каналу и ретранслирует их Глафире по низкоскоростному каналу.
Компьютер Дмитрия может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Дмитрием данных до полного их получения Глафирой?
В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.
Вопрос 6
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 8. Система команд Кузнечика: Вперед 85 – Кузнечик прыгает вперёд на 85 единиц, Назад 45 – Кузнечик прыгает назад на 45 единиц. Какое наименьшее количество раз должна встретиться в программе команда «Назад 45», чтобы Кузнечик оказался в точке 18?
Вопрос 7
Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
Складываются первая и вторая, а также вторая и третья цифры исходного числа.
Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходное число: 348. Суммы: 3+4 = 7; 4+8 = 12. Результат: 712.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1216.
Вопрос 8
Ниже на четырех языках программирования записан рекурсивный алгоритм F
Бейсик
Алгоритмический
FUNCTION F(k)
PRINT k
IF k < 5 THEN
F(k + 1)
F(k + 2)
F(k + 3)
END IF
END FUNCTION
алг цел F(цел k)
нач
вывод k
если k < 5 то
F(k + 1)
F(k + 2)
F(k + 3)
все
кон
Паскаль
Си
function F(k: integer): integer;
begin
write(k);
if k < 5 then begin
F(k + 1);
F(k + 2);
F(k + 3);
end;
end;
int F(int k) {
int F;
print(k);
if (k < 5) {
F(k + 1);
F(k + 2);
F(k + 3);
}
return F;
}
Чему будет равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)
Вопрос 9
В детскую игрушку «Набор юного шпиона» входят два одинаковых комплекта из 3 флажков различных цветов. Сколько различных тайных сообщений можно передать этими флажками, условившись менять выставленный флажок каждые 8 минут и наблюдая за процессом 56 минут? Наблюдатель видит вынос первого флажка и 6 перемен флажка. При этом возможна смена флажка на флажок того же цвета.
Вопрос 10
Запись десятичного числа в системах счисления с основаниями 13 и 17 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?
Вопрос 11
У исполнителя Калькулятор три команды, которым присвоены номера:
прибавить 1
умножить на 5
умножить на 3
Сколько есть программ, которые число 1 преобразуют в число 26?
Вопрос 12
Определите асимптотическую сложность следующего алгоритма:
Си
Бейсик
for (i = 0; i <= pow(n, 3); ++i)
for (j = 0; j <= pow(n, 2); ++j){
for (b = 0; b <= n; ++b){
a = pow(n, 2);
for (jk = 0; jk <= pow(a, 3); ++jk)
print(b, jk, j, i);
}
if (i % pow(n, 2) == 0)
for (bi = 0; bi <= pow(b, 3); ++bi){
k = pow(a, 3);
for (bk = 0; bk <= k; ++bk)
print(bk, bi, j, i);
}
}
FOR i = 0 TO n ^ 3
FOR j = 0 TO n ^ 2
FOR b = 0 TO n
a = n ^ 2
FOR jk = 0 TO a ^ 3
PRINT b, jk, j, i
NEXT jk
NEXT b
IF i MOD n ^ 2 = 0 THEN FOR bi = 0 TO b ^ 3
k = a ^ 3
FOR bk = 0 TO k
PRINT bk, bi, j, i
NEXT bk
NEXT bi
NEXT j
NEXT i
Паскаль
Алгоритмический
for i := 0 to n ** 3 do
for j := 0 to n ** 2 do begin
for b := 0 to n do begin
a := n ** 2;
for jk := 0 to a ** 3 do
write(b, jk, j, i);
end;
if i mod n ** 2 = 0 then
for bi := 0 to b ** 3 do begin
k := a ** 3;
for bk := 0 to k do
write(bk, bi, j, i);
end;
end;
нц для i от 0 до n ** 3
нц для j от 0 до n ** 2
нц для b от 0 до n
a := n ** 2
нц для jk от 0 до a ** 3
вывод b, jk, j, i
кц
кц
если mod(i, n ** 2) = 0 то
нц для bi от 0 до b ** 3
k := a ** 3
нц для bk от 0 до k
вывод bk, bi, j, i
кц
кц
все
кц
кц
Θ(n3)
Θ(n5)
Θ(n12)
Θ(n2)
Вопрос 13
Определите количество вызовов функции f при исполнении следующего алгоритма:
int f(int n) {
int f;
if (n >= 32258064516)
f = f(n / 3) + 1;
if (n < 32258064516 && n >= 666666666)
f = f(n - 5) + 1;
if (n < 666666666)
f = 1;
return f;
}
print(f(1000000000000));
FUNCTION f(n)
IF n >= 32258064516 THEN f = f(n / 3) + 1
IF n < 32258064516 AND n >= 666666666 THEN f = f(n - 5) + 1
IF n < 666666666 THEN f = 1
END FUNCTION
PRINT f(1000000000000)
Паскаль
Алгоритмический
function f(n: integer): integer;
begin
if n >= 32258064516 then
f := f(n div 3) + 1;
if (n < 32258064516) and (n >= 666666666) then
f := f(n - 5) + 1;
if n < 666666666 then
f := 1;
end;
write(f(1000000000000));
алг цел f(цел n)
нач
если n >= 32258064516 то
f := f(n / 3) + 1
все
если n < 32258064516 и n >= 666666666 то
f := f(n - 5) + 1
все
если n < 666666666 то
f := 1
все
кон
вывод f(1000000000000)
Формат выходного файла
В качестве решения принимается текстовый файл, содержащий по одному числу в строке —
ответы на каждый из вопросов.
При отправке файла следует выбрать в тестирующей системе среду разработки "Answer text".
Если вы не знаете ответа на какой-то из вопросов, укажите вместо ответа число 0.
У Ильи имеется карта сокровищ размера H × W клеток.
Маленький брат Ильи — Никита, взял эту карту "поиграть".
Игра заключалась в следующем: какое-то количество раз карта была сложена вдвое по вертикали или по горизонтали.
Складывая карту по вертикали, Никита брал её за нижнюю сторону, по горизонтали — за правую сторону.
После этого он соединял взятую сторону с противоположной стороной.
При этом верхний левый угол карты всегда оставался неподвижным.
Линия сгиба всегда проходила точно по границе между клетками.
В итоге сложенная карта оказалось размером N × M клеток.
Но этого Никите было мало, он взял иглу и начал протыкать некоторые клетки насквозь, включая все слои, получившиеся в процессе складывания.
Как только Илья увидел это, он немедленно остановил брата.
Илья побоялся разворачивать карту, так как она может порваться.
Карта порвётся, если после разворачивания слишком много отверстий будут находиться рядом друг с другом.
Требуется написать программу, которая определит, сколько отверстий находится в каждой из Q прямоугольных областей развёрнутой карты.
Формат входного файла
Первая строка входного файла содержит два целых числа H и W — высоту и ширину исходной карты.
Вторая строка входного файла содержит два целых числа N и M — высоту и ширину сложенной карты.
Далее следует N строк по M символов в каждой — описание карты.
Символом 'X' (ASCII 88) отмечается клетка, которую проткнул Никита, символом '.' (ASCII 46) отмечается нетронутая клетка.
Далее следует строка, содержащая одно целое число Q — количество прямоугольных областей, интересующих Илью.
Далее в Q строках содержится по четыре числа в каждой. xi, yi, ui, vi — описание i-й прямоугольной области карты.
xi, yi — координаты левого верхнего угла прямоугольника, ui, vi — координаты правого нижнего угла прямоугольника.
Нумерация клеток по вертикали сверху вниз с 1 до H, нумерация клеток по горизонтали слева направо с 1 до W.
Гарантируется, что свёрнутая карта получена из исходной путём преобразований, описанных в задаче.
То есть существую такие целые числа a и b, что N × 2a = H и M × 2b = W.
Формат выходного файла
Выходной файл должен содержать Q строк, каждая из которых содержит по одному целому числу.
Число в строке номер i должно быть равно количеству отверстий, которые попали в i-ю прямоугольную область.
Ограничения
1 ≤ H, W ≤ 109
1 ≤ N, M ≤ 103
1 ≤ Q ≤ 105
1 ≤ xi ≤ ui ≤ H,
1 ≤ yi ≤ vi ≤ W
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
H, W
xi, yi, ui, vi
Q
1
12
1 ≤ H, W ≤ 103
xi = ui, yi = vi
1 ≤ Q ≤ 105
2
8
1 ≤ H, W ≤ 103
1 ≤ Q ≤ 102
3
14
1 ≤ H, W ≤ 103
1 ≤ Q ≤ 105
1-2
4
11
1 ≤ H, W ≤ 109
xi = ui, yi = vi
1 ≤ Q ≤ 105
1
5
9
1 ≤ H, W ≤ 109
(ui − xi + 1)(vi − yi + 1) ≤ 106
Q = 1
6
16
1 ≤ H, W ≤ 109
(ui − xi + 1)(vi − yi + 1) ≤ 106
1 ≤ Q ≤ 102
2, 5
7
17
1 ≤ H, W ≤ 109
1 ≤ Q ≤ 102
2, 5-6
8
13
1 ≤ H, W ≤ 109
1 ≤ Q ≤ 105
1-7
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Учитель математики придумал игру для развития навыков устного счёта.
Учитель записывает на доске таблицу A из N × N натуральных чисел.
Затем он вызывает к доске двух учеников, и указывает одно из чисел в таблице (Aij).
Первый ученик должен выбрать другое число в той же строке,
что и указанное учителем (Aiq, q ≠ j), и сложить с указанным числом.
Второй ученик должен выбрать другое число в той же столбце,
что и указанное учителем (Apj, p ≠ i), и перемножить с указанным числом.
Если результаты вычислений у двух учеников совпали (Aij + Aiq = Aij × Apj),
то ученики получают пятёрки.
Чтобы игра была честной, учитель указывает только на такие элементы,
для которых существует хотя бы одна подходящая пара чисел.
Учитель хочет вызвать как можно больше учеников,
указывая каждым на ранее не использованный элемент в таблице.
Требуется написать программу, которая определит количество элементов таблицы,
для которых существует хотя бы одна подходящая пара чисел.
По втором примере учитель может выбрать число.
2 (2 + 8 = 2 × 5), 4 (4 + 8 = 4 × 3) либо 3 (3 + 9 = 3 × 4). Если вместо 13 поставить число 5, ответ не изменится, хотя для числа 2 появится второй способ выбора подходящей пары чисел.
Формат входного файла
Входной файл содержит целое число N — размер таблицы,
за которым далее следует N строк по N чисел Aij.
Формат выходного файла
Выходной файл должен содержать единственное целое число — количество элементов Aij,
для которых существуют p ≠ i, q ≠ j, такие что Aij + Aiq = Aij × Apj.
Ограничения
1 ≤ N ≤ 500,
1 ≤ Aij ≤ 109
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
После просмотра нескольких документальных фильмов о природе, лесник Шон очень беспокоится о местонахождении деревьев в своём лесу.
Дело в том, что в одном из таких фильмов деревья просто так взяли и ушли.
Конечно это было необходимо из-за событий, которые происходили в фильме.
Но Шон абсолютно уверен, что в реальности такие события не могут случиться по ряду обстоятельств.
Поэтому он считает, что у деревьев в его лесу нет никакой уважительной причины, чтобы отлучаться.
То есть деревьям нельзя просто так взять и уйти.
В текущий момент у Шона нет никакой информации о том, где растёт каждое из деревьев.
Поэтому он не может с полной уверенностью сказать, что деревья в его лесу неподвижны.
Всего в лесу растёт N деревьев.
Лес является непрерывным отрезком на прямой от 1 до L.
Все деревья растут в разных целочисленных точках.
У Шона есть сканер, который позволяет определить наличие хотя бы одного дерева на каком-то участке леса.
К сожалению, заряда сканера хватит только на K сканирований.
Необходимо помочь Шону определить местоположение всех деревьев в лесу.
Можно считать, что все сканирования Шон совершает в течение одного дня.
За столь короткий промежуток времени рядом с лесом не могло произойти никаких событий, которые заставили бы деревья просто так взять и уйти.
Протокол взаимодействия
Сначала на вход программе-решению подаётся целое число L — длина леса.
Для каждого теста жюри зафиксировало числа N и K — количество деревьев и максимальное количество запросов на сканирование участка леса.
Гарантируется, что K запросов достаточно, чтобы решить задачу.
Эти числа не сообщаются программе-решению.
Ограничения на N и K в различных подзадачах приведены в таблице системы оценивания.
Если решение делает более K запросов к программе жюри, то на этом тесте оно получает в качестве результата тестирования "Wrong answer".
Чтобы сделать запрос программа-решение должна вывести строку вида "? l r", где l и r (1 ≤ l ≤ r ≤ L) — целые числа, крайние левая и правая точка сканируемого участка леса.
В ответ на запрос программа жюри подаёт на вход программе-решению либо строку "Yes", либо строку "No", в зависимости от того, есть ли хотя бы одно дерево в запрашиваемом участке.
Если программа-решение определила ответ на задачу, она должна вывести две строки: в первой "ok?", во второй N целых чисел — список точек, в которых растут деревья в порядке возрастания координат.
После этого программа-решение должна завершиться.
Гарантируется, что в каждом тесте положение всех деревьев является фиксированным, и не меняется в зависимости от запросов, произведенных программой-решением.
После каждого запроса и вывода ответа необходимо выполнить сброс буфера.
Например, в Pascal необходимо написать flush(output), в C++ — cout.flush().
Ограничения
1 ≤ N ≤ 103
1 ≤ L ≤ 109
1 ≤ xi ≤ L
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
N
L
K
1
14
N = 1
1 ≤ L ≤ 2500
K = 100
2
12
N = 1
1 ≤ L ≤ 106
K = 47
1
3
17
N = 1
1 ≤ L ≤ 109
K = 37
1-2
4
15
35 ≤ N ≤ 100
35 ≤ L ≤ 103
K = N2
5
11
1 ≤ N ≤ 103
1 ≤ L ≤ 104
K = 100 + 100 * N
1, 4
6
13
1 ≤ N ≤ 103
1 ≤ L ≤ 106
K = 43 * N
1-2, 4-5
7
18
1 ≤ N ≤ 103
1 ≤ L ≤ 109
K = 33 * N
1-6
Получение информации о результатах окончательной проверки
По запросу сообщается результат окончательной проверки на каждом тесте.
Однажды Петя пришел домой и похвастался Васе, что научился быстро находить геометрические фигуры на картинках и поспорил, что теперь находит их гораздо лучше Васи.
Тогда Вася решил найти сложную картинку и посоревноваться со своим младшим братом в нахождении геометрических фигур.
Картинка представляет из себя набор из N строк по M символов в каждом. Каждый символ может принимать значения с кодами от 33 до 126 в кодировке ASCII.
Петя и Вася решили искать на картинке ромбы специального вида. Контур таких ромбов можно задать уравнением |x − a| + |y − b| = r, где a — номер столбца центра фигуры, b — номер строки центра фигуры, а r — ее радиус. Фигура засчитывается только в том случае, если все клетки ее контура содержат один и тот же символ, а также не вылезают за границы картинки. Также не учитываются фигуры, радиус r которых равен 0.
Вася решил сжульничать и написать программу, которая найдет все ромбы за него. Однако он не хочет попадаться, поэтому просит вас написать программу за себя.
Отправка решения и тестирование
Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты.
Этот файл можно скачать ЗДЕСЬ.
В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче
в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").
Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле.
Если правильный ответ на какой-то из тестов получить не удалось, выведите вместо него число − 1.
Формат входного файла
Первая строка входного файла содержит целое число T — количество тестов.
Следующие строки содержат описания тестов.
Первая строка каждого теста содержит два целых числа N, M — размеры картинки.
Следующие N строк содержат M символов — описание картинки.
Формат выходного файла
Выходной файл должен содержать T ответов на тесты. Каждый ответ состоит из одной или двух строк.
Первая строка содержит целое число K — количество ромбов на картинке. Вторая строка содержит K четверок a, b, r, c, разделенных пробелами, где целые числа a и b — строка и столбец центра ромба, целое число r — радиус ромба и c — символ, которым заполнен его контур. Четверки, описывающие каждый ромб, можно выводить в любом порядке.
В случае, если ответ на тест найти не удалось, выведите для этого теста одну строку с − 1.
