#2839

Темы: [Массив констант]

Источники: [ Личные олимпиады, Школьная личная олимпиада ФМШ №2007 г. Москвы, 2010, 8 класс, Задача C ] [ Личные олимпиады, Школьная личная олимпиада ФМШ №2007 г. Москвы, 2010, 9 класс, Задача A ]

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

Входные данные

Вводятся два числа, разделенных пробелом - число, месяц.

Выходные данные

Вывести одно число - количество дней.

Примеры

Входные данные

2 1

Выходные данные

Входные данные

31 12

Выходные данные

#2858

Лестница

Темы: [Динамическое программирование: два параметра] [Динамическое программирование: один параметр]

Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из М ступенек различной длины и высоты. Лестница построена из каменных блоков 1x1x1 метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек N. Для этого они могут также устанавливать каменные блоки 1x1x1. Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться.

Входные данные

В первой строке через пробел заданы два целых числа M и N (1 ≤ N < M ≤ 100). Далее идут M строк, содержащих пару целых чисел L и H - длина и высота i-ой ступеньки соответственно (1 ≤ L, H ≤ 101). Ступеньки нумеруются снизу вверх.

Выходные данные

В выходной файл выведите единственное число - ответ на задачу.

Примеры

Входные данные

Выходные данные

#2859

Раскраска кубиков

Темы: [Бинарный поиск в массиве] [Жадный алгоритм]

На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все \(n\) своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке \(a_1\), \(a_2\), ..., \(a_n\). Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами \(i_1\), \(i_2\), ...., \(i_k\) покрашены в один цвет, то \(a_{i_1} \lt a_{i_2}\lt ... \lt a_{i_k}\). Петя хочет использовать как можно меньше цветов. Помогите ему!

Входные данные

Первая строка входного файла содержит число \(n\) - количество кубиков у Пети (\(1\le n \le 250000\)). В следующей строке записано \(n\) чисел \(a_1\), \(a_2\), ..., \(a_k\), \(-2^{31}\le a_i \le 2^{31} - 1\).

Выходные данные

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

Примеры

Входные данные

10
2 3 1 3 2 1 2 2 4 3

Выходные данные

5
1 1 2 2 3 4 4 5 1 3

#2860

Лестницу в треугольник

Темы: [Элементарная геометрия]

Рассмотреть прямые, проходящие через какой либо угол. Угол наклона определяется однозначно.

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

Входные данные

В первой строке дано число 0 ≤ N ≤ 1000. Далее записаны N строк. Каждая строка содержит два целых чисел через пробел 0 < x_i, y_i < 10⁶ - координаты вершины i-й ступени (ступени перечисляются в порядке сверху вниз, слева направо).

Выходные данные

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

Примеры

Входные данные

Выходные данные

2
2 3
3 2

4.0000 4.0000

2
1 3
3 1

0 0

#2861

Тир

Темы: [Перебор]

Шесть стрелков решили повысить свою меткость и зашли в тир пострелять. В тире было установлено шесть мишеней, и каждый стрелок выстрелил во все мишени. После чего они собрались в баре, и каждый рассказал, сколько раз он попал в мишень. Бармен, запомнил, что сказал каждый из них, и на следующий день посчитал, сколько дырок в каждой мишени. Требуется помочь бармену определить: не ошибся ли кто-то из "снайперов", и сколько существует вариантов стрельбы (то есть, кто в какие мишень попадал), при которых получаются такие результаты. Считается, что две пули в одну дырку не попадают.

Входные данные

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

Выходные данные

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

Примеры

Входные данные

1 0 0 0 1 0

1 0 0 1 0 0

Выходные данные

Входные данные

5 5 5 5 5 0

5 5 5 5 5 0

Выходные данные

1
1 1 1 1 1 0 
1 1 1 1 1 0 
1 1 1 1 1 0 
1 1 1 1 1 0 
1 1 1 1 1 0 
0 0 0 0 0 0