Афанасий – автор детских раскрасок. Недавно он решил, что изготовлять раскраски будет по совершенно новой технологии. А именно, изначально он отмечает на листе бумаги n точек, и соединяет эти точки отрезками так, чтобы никакие два отрезка не пересекались и из каждой точки выходило не более трех отрезков. В результате лист бумаги распадается на фигуры. Дети раскрашивают каждую образовавшуюся фигуру в уникальный цвет. Раскраска считается тем лучше, чем больше цветов потребуется детям, чтобы ее раскрасить. Помогите Афанасию выбрать такое расположение n точек и отрезков между ними, чтобы количество цветов было максимально.
По заданному числу n выведите такой плоский граф, что:
в нём n вершин,
степень каждой вершины не превышает трех,
число граней максимально.
Одно натуральное число n, 1 ≤ n ≤ 1000.
В первых n строках выведите по два целых числа ai, bi (|ai| ≤ 109, |bi| ≤ 109), разделенных пробелом. В i-ой строке – координаты i-ой вершины графа (1 ≤ i ≤ n). Никакие две пары координат не должны совпадать.
В следующей строке выведите целое число m (0 ≤ m ≤ 10000) – число ребер графа.
В следующих m строках выведите по два натуральных числа ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi), разделенных пробелом, которые задают отрезок, соединяющий вершины ui и vi. Каждый отрезок должен быть упомянут ровно один раз. Из каждой точки должно выходить не более трех отрезков, любые два различных отрезка не должны иметь общих точек, кроме своих концов.
2
-1000000000 -1000000000
1000000000 1000000000
0
7
0 0
4 0
0 2
4 2
1 1
3 1
2 1
10
1 2
1 3
1 5
2 4
2 6
3 4
3 5
4 6
5 7
6 7
Денис Борисов как-то решил попробовать свои силы на рынке опционов. Дело очень выгодное, ведь если получится что-нибудь заработать, то можно будет заработать еще больше на обучающих видео о том, как зарабатывать на опционах. Дело шло очень хорошо. Но чтобы оптимизировать процесс, Денису нужна программа, которая будет делать некоторые расчеты.
У Дениса есть список торговых площадок, на которых он может торговать опционами. На площадке номер i стоимость одного опциона составляет ai рублей, а стоимость каждого дополнительного опциона составляет bi рублей. Так, например, чтобы купить k опционов на площадке номер i, нужно заплатить ai + (k - 1)·bi рублей. Денису регулярно приходят письма от партнеров. Письмо с номером i содержит информацию о дополнительной торговой площадке (два целых числа ai, bi), а также запрос о том, за какую минимальную стоимость можно купить ci опционов на одной из площадок, информация о которой известна на данный момент.
Дополнительно известно, что партнеры – люди серьезные и любят порядок. Поэтому информацию о площадках они решили присылать в порядке невозрастания чисел bi. И все бы ничего, но программу сортировки они взяли с одного очень известного сайта, на котором автор сайта умышленно допустил ряд ошибок в алгоритме. Ошибки в алгоритме привели к тому, что числа bi были отсортированы не совсем верно, а именно с точностью до пяти позиций. То есть для массива bi выполнено соотношение bi ≤ bj, при i ≥ j + 5.
Помогите Денису справиться с поставленной задачей. Напишите программу, которая будет отвечать на письма партнеров.
В первой строке записано число 1 ≤ n ≤ 105.
В следующих n строках записаны по три целых числа 1 ≤ ai, bi, ci ≤ 106.
Выведите n чисел, по одному в строке – ответы на каждое из писем от партнеров Дениса.
3
3 1 4
1 2 2
2 1 3
6
3
4
Студент Иннокентий обучает младшую сестру Машеньку программированию. Недавно он показал ей такую функцию:
Затем он написал два натуральных числа a и b (1 ≤ a < b ≤ 2·109) и попросил вычислить значение выражения F(a, F(a+1, ... F(b - 1, b)...)). Например, для чисел 5 и 6 искомое выражение имеет вид F(5, 6), а для чисел 14 и 17 искомое выражение имеет вид F(14, F(15, F(16, 17))).
К удивлению брата, Машенька легко справилась с этой задачей. Попробуйте и вы.
В единственной строке через пробел записаны два целых числа a и b, (1 ≤ a < b ≤ 2·109).
Выведите единственное целое число – ответ на задачу.
14 17
62
Однажды студенту Пафнутию перед сдачей зачета по металлургии приснился страшный сон. Он оказался в комнате очень странной формы, внутри которой стояла огромная доменная печь. Проснувшись, он начал вспоминать детали сна. В частности, он вспомнил, что одна стена комнаты имела вид параболы с вершиной в точке (0, H), и эта парабола пересекала ось Ox в точках ( ± T, 0), а вторая стена представляла из себя отрезок, соединяющий точки (T, 0) и ( - T, 0). Теперь ему интересно доменную печь какого максимального размера можно разместить внутри данной комнаты. Доменную печь Пафнутий для простоты считает кругом. Пафнутий справился с данной задачей, попробуйте и Вы.
В первой строке записано число T, во второй – число H, 0 ≤ T, H ≤ 20000. Оба числа даны с 6-ю знаками после запятой.
Выведите единственное число – максимально возможный радиус R доменной печи, с абсолютной погрешностью не более 10 - 6.
10.000000
10.000000
5.000000
На равнинной местности расположен форт, состоящий из трех башен и прямых стен, соединяющих эти башни. Каждую ночь графу Сильвестру, командиру гарнизона, приходится расставлять N стражей. Стражи могут занимать посты внутри форта, на стенах форта или на башнях.
Сильвестр считает расстановку стражей правильной, если их посты расположены выпукло относительно друг друга: для каждого стража точка, в которой расположен его пост, не может принадлежать выпуклой оболочке точек, в которых расположены посты остальных стражей. Другими словами, выпуклая оболочка точек, в которых расположены посты стражей, должна являться выпуклым N-угольником.
Чтобы не портить каждый свой вечер тактическими размышлениями, граф Сильвестр поручает стражам случайно выбрать себе пост в любой точке форта, равномерно и независимо друг от друга.
Какова вероятность того, что при таком случайном выборе постов для N стражей, полученная расстановка будет правильной?
В первых трех строках даны координаты башен: координаты каждой башни задаются парой целых чисел x, y, - 2000 ≤ x, y ≤ 2000. Гарантируется, что координаты башен попарно различны. В четвертой строке дано количество стражей N, 1 ≤ N ≤ 10.
В единственной строке выведите вероятность правильной расстановки стражей с абсолютной погрешностью не более 10 - 4.
-15 -15
15 -15
0 15
3
1.0000000000
-15 -15
15 -15
0 15
4
0.6666666667
График главного программиста Пети очень напряженный. Каждый день у Пети назначено по два совещания. График совещаний расписан на N дней вперед. У каждого совещания есть время начала и время окончания. Совещания, которые проходят в один день, могут накладываться друг на друга произвольным образом. На работе у Пети действуют следующие правила:
Так как Петя очень рассеянный, то при внесении расписания совещаний в компьютер он допустил K опечаток. Каждая из опечаток состоит в том, что он записал время начала совещания или время окончания совещания с ошибкой в T часов. Возможна ситуация, что время начала и время окончания одного и того же совещания записаны с ошибкой, это считается за две опечатки. При этом получилось новое расписание, которое обладает следующими свойствами:
В первой строке дано целое число N – количество дней, для которых был составлен график совещаний, 1 ≤ N ≤ 1000.
Во второй строке дано целое число K – количество опечаток, которые допустил Петя, 1 ≤ K ≤ 4·N.
В третьей строке дано целое число T – количество часов, на которое ошибался Петя, 1 ≤ T ≤ 10.
В следующих N строках записано по четыре целых числа ai, bi, ci, di, где ai – время начала первого совещания в i-й день, bi – время окончания первого совещания в i-день, ci – время начала второго совещания в i-й день, di – время окончания второго совещания в i-й день, 8 ≤ ai, bi, ci, di ≤ 18, ai ≤ bi, ci ≤ di, ai ≤ ci, 1 ≤ i ≤ N.
Программа должна вывести расписание, которое получилось у Пети в следующем формате: в i-й строке должны быть записаны через пробел четыре числа – время начала первого совещания в i-й день, время окончания первого совещания в i-й день, время начала второго совещания в i-й день, время окончания второго совещания в i-й день.
Если есть несколько вариантов расписания, удовлетворяющих условиям задачи, то следует вывести любое из них.
1
1
1
11 13 16 17
11 12 16 17
Студент МИСиСа Вася любит придумывать новые игры. В частности, однажды он придумал совершенно новую и уникальную игру. Игра Васи происходит на прямоугольном поле размера M × N клеток. Будем считать, что левая верхняя клетка имеет координаты (1, 1). В каждой клетке изначально написано некоторое число. В игру играет Q человек. Каждый человек за один ход может выбрать некоторый прямоугольник, стороны которого параллельны сторонам поля, и прибавить ко всем его клеткам некоторое целое число A.
Затем по результирующему полю в конце игры Вася производит начисление очков (каким образом оно происходит пока не решил и сам Вася). Тем не менее Вася просит Вас помочь по начальной конфигурации поля и ходам игроков рассчитать результирующее игровое поле.
В первой строке записано единственное целое число 1 ≤ Q ≤ 105 – количество игроков.
В следующих Q строках записаны ходы игроков. Каждая из строк содержит пять целых чисел: Y1, X1, Y2, X2, A, где (Y1, X1) – строка и столбец верхнего левого угла выбранного игроком прямоугольника, а (Y2, X2) – строка и столбец нижнего правого угла выбранного игроком прямоугольника. 1 ≤ X1 ≤ X2 ≤ N, 1 ≤ Y1 ≤ Y2 ≤ M. - 100 ≤ A ≤ 100 – число, которое должно быть прибавлено в каждой клетке выбранного прямоугольника.
В (Q + 2)-й строке записаны два числа M и N, 5 ≤ M, N ≤ 1000 – высота и ширина поля. В следующих M строках записаны через пробел по N чисел – элементы матрицы. Все элементы матрицы – целые числа, по модулю не превышающие 100.
Выведите ровно M строк, в каждой строке по N целых чисел через пробел – значения элементов матрицы после ходов всех Q игроков.
2
2 4 6 8 1
4 5 9 9 3
10 10
0 0 0 0 0 8 0 0 0 0
0 0 0 0 0 0 8 0 0 0
0 0 0 0 0 0 0 8 0 0
0 0 0 0 0 0 0 3 0 0
0 0 0 0 0 0 0 5 1 1
0 0 0 0 0 0 0 1 2 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 8 0 0 0 0
0 0 0 1 1 1 9 1 0 0
0 0 0 1 1 1 1 9 0 0
0 0 0 1 4 4 4 7 3 0
0 0 0 1 4 4 4 9 4 1
0 0 0 1 4 4 4 5 5 2
0 0 0 0 3 3 3 3 3 0
0 0 0 0 3 3 3 3 3 0
0 0 0 0 3 3 3 3 3 0
0 0 0 0 0 0 0 0 0 0
Назовем число, записанное LED-цифрами, симметричным, если его запись обладает осевой симметрией с вертикальной либо горизонтальной осью. К примеру: 88 – симметричное, 87 – не симметричное, 1338 – симметричное, 258 – не симметричное, 582 – симметричное, 15821 – не симметричное и т.п. Вам даны два числа: A и B, A ≤ B. Найти количество симметричных чисел в отрезке [A, B] (включая A и B).
В единственной строке записаны через пробел два целых числа: A и B, 0 ≤ A ≤ B ≤ 1018.
Выведите единственное целое число – количество симметричных чисел в отрезке [A, B]. Ответ выводить по модулю 109 + 7.
1 24
7
Не так давно в МИСиС прошли недели, посвященные живописи и искусству. В частности, в течение данных недель студентам были представлены разные картины.
Каждая картина оценивается своей красотой n. Красота картины определяется по формуле n = x2 + y3, где x – натуральное число, характеризующее художественные достоинства картины, а y – стоимость картины в тысячах долларов (также натуральное число). Две картины, у которых совпадают оба параметра x и y, считаются одинаковыми.
Теперь студентам МИСиС интересно, какое существует максимальное количество различных картин, имеющих красоту n.
В единственной строке записано целое число n, 1 ≤ n ≤ 1018.
Выведите единственное число – количество различных картин с красотой n.
1
0
17
2
Студент МИСиСа Петя также как и Вася любит придумывать разные игры. Вдохновившись творением Васи он придумал свою еще более новую и уникальную игру.
Игра Пети также происходит на прямоугольном поле размера M × N клеток. Будем считать, что левая верхняя клетка имеет координаты (1, 1). Значения во всех клетках изначально равны нулю. В игру играет Q человек. Каждый человек за один ход может выбрать некоторый прямоугольник, стороны которого параллельны сторонам поля, и прибавить ко всем его клеткам некоторое целое число A.
Теперь Петю очень интересует, какое максимальное значение элемента получилось на результирующем поле. Помогите ему в этом.
В первой строке записано единственное целое число 1 ≤ Q ≤ 104 – количество игроков.
В следующих Q строках записаны ходы игроков. Каждая из строк содержит пять целых чисел: Y1, X1, Y2, X2, A, где (Y1, X1) – строка и столбец верхнего левого угла выбранного игроком прямоугольника, а (Y2, X2) – строка и столбец нижнего правого угла выбранного игроком прямоугольника. 1 ≤ X1 ≤ X2 ≤ N, 1 ≤ Y1 ≤ Y2 ≤ M. - 100 ≤ A ≤ 100 – число, которое должно быть прибавлено в каждой клетке выбранного прямоугольника.
В (Q + 2)-й строке записаны два числа M и N, 5 ≤ M ≤ 109, 5 ≤ N ≤ 4000 – высота и ширина поля.
Выведите ровно одно целое число – максимальное значение элемента матрицы после ходов всех Q игроков.
2
2 4 6 8 1
4 5 9 9 3
10 10
4