Красивые последовательности

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 8192 KB.

ввод: input.txt
вывод: output.txt

 

Последовательность C1, C2,.., CK называется красивой, если любые два соседних числа в ней имеют разную четность. Например, последовательности [1, 16, 3], [8, 3], [2005], [1, 2, 3, 4, 5] - красивые. Ваша задача - посчитать количество красивых подпоследовательностей для заданной последовательности различных целых чисел A1, A2,..., AN. Например, из [1, 3, 4] можно выбрать 5 красивых подпоследовательностей: [1], [3], [4], [1, 4], [3, 4]. Подпоследовательности равные по своим элементам, но стоящие на занимающие разные позиции, следует считать различными.

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

Во входном файле в первой строке записано целое число N (1 <= N <= 5000) - длина заданной последовательности. Во второй строке записана последовательность A1, A2,..., AN. Числа разделяются пробелами. Все числа целые, помещаются в 32 битное знаковое число.

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

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

Пример

Ввод

Test #1
3
1 3 4

Test #2
5
1 3 4 6 7

Test #3
3
2 2 2

Вывод

Test #1
5

Test #2
15

Test #3
3

Лабиринт

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 8192 KB.

ввод: input.txt
вывод: output.txt

 

Лабиринт состоит из NxM комнат. Некоторые комнаты закрыты изнутри со всех четырех сторон и поэтому являются непроходимыми. Все остальные комнаты - открыты. Переходить из комнаты в комнату можно, если обе комнаты открыты и имеют общую стену. Каждая дверь закрытой комнаты украшена снаружи золотым барельефом. Его можно увидеть, если находиться в соседней открытой комнате. В лабиринте есть несколько входов. Можно войти только в один из них. Вход в лабиринт осуществляется сверху в одну из открытых комнат (через люк в потолке).
Какое наибольшее количество золотых барельефов можно увидеть, если подходящим образом выбрать вход в лабиринт и обойти все доступные от этого входа комнаты? Сколькими входами можно для этого воспользоваться?

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

В первой строке входного файла записаны размеры лабиринта - целые числа N, M (1 <= N, M <= 200). Далее в N строках записано по M символов - карта лабиринта. Символ "." означает открытую комнату, над которой нет входа; символ "*" - открытую комнату с входом в лабиринт над ней, а "+" означает закрытую комнату. В лабиринте могут отсутствовать как закрытые комнаты, так и входы в него. Покидать лабиринт запрещается.

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

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

Пример

Ввод

Test #1
3 3
.*.
.+.
+++

Test #2
4 5
**++*
.++..
++.+*
++.*+

Вывод

Test #1
5 1

Test #2
6 3

Точный расчет

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 8192 KB.

ввод: input.txt
вывод: output.txt

 

Новый провайдер сотовой связи "МегаТС" приобрел такую популярность, что все N однокласскиков перешли на его использование. Телефон каждого абонента использует определенную частоту - целое число от 1 до K. Известно, что разговор между двумя абонентами имеет неудовлетворительное качество, если оба телефона используют одну частоту. По утрам каждый ученик класса звонит своему однокласснику, чтобы обсудить предстоящий день. Звонит он каждый раз одному и тому же человеку. Звонок осуществляется с сотового телефона на сотовый. Таким образом, каждое утро совершается N телефонных разговоров. Про каждый разговор ребята знают его продолжительность. Помогите одноклассникам выбрать такие частоты, чтобы суммарная длительность неудовлетворительных по качеству телефонных разговоров была наименьшей. Очевидно, что порядок осуществления звонков на ответ не влияет.

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

В первой строке входного файла записаны два натуральных числа N, K (1 <= N, K <= 15000), где N - количество детей в классе, а K - количество различных частот. Далее в N строках записана информация о звонках. В строке j записано два целых числа Cj, Pj (1 <= Cj <= N; Cj <> j; 1 <= Pj <= 15000), где Cj номер школьника, которому звонит школьник j, а Pj - средняя продолжительность разговора.

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

Выведите в первую строку наименьшую суммарную продолжительность неудовлетворительных по качеству телефонных разговоров. Во вторую строку выведите последовательность целых чисел A1, A2,..., AN. Число Aj означает частоту, которую должен использовать телефон j-го ребенка. Если искомых последовательностей A несколько, то выведите любую.

Пример

Ввод

Test #1
2 1
2 1
1 1

Test #2
3 2
2 10
3 10
1 20

Вывод

Test #1
2
1 1

Test #2
10
1 1 2

Прямоугольники

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 8192 KB.

ввод: input.txt
вывод: output.txt

 

На координатной плоскости нарисовали прямоугольник WxH. Его стороны параллельны осям координат. Координаты его левого нижнего угла (0, 0), правого верхнего - (W, H). Далее в нем проводят отрезки. Каждый отрезок разрезает один из нарисованных прямоугольников вертикально или горизонтально. Он начинается на границе разрезаемого прямоугольника и заканчивается тоже на его границе. Например, первый отрезок обязательно рассекает первоначальный прямоугольник. В результате образуется два прямоугольника. Следующий отрезок разрезает один из двух получившихся, и т.д. Прямоугольники, которые подверглись разрезанию, называются интересными. Прямоугольники, которые не содержат внутри себя других прямоугольников (и, следовательно, любых других линий), называются элементарными. Плотностью интересного прямоугольника назовем количество элементарных прямоугольников внутри него. Плотностью всей картинки назовем сумму плотностей всех интересных прямоугольников на этой картинке.
Ваша задача - для заданной картинке посчитать ее плотность.

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

В первой строке записано натуральное число N (1 <= N <= 15000), где N - количество проведенных отрезков. Во второй строке записана пара чисел W, H (1 <= W, H <= 200). Далее в N строках записана информация о проводимых отрезках. Каждый отрезок задается координатами своих концов Xi1, Yi1, Xi2, Yi2. Все координаты - целые числа. Каждые отрезок либо горизонтальный, либо вертикальный. Числа в строках разделяются пробелами.

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

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

Пример

Ввод

Test #1
2
10 20
0 17 10 17
8 17 8 0

Test #2
4
8 8
0 4 8 4
4 8 4 4
4 0 4 4
4 6 8 6

Вывод

Test #1
5

Test #2
12