SnarkNews summer series, round 3.

Problem A. Найди сумму

Input file: sum.in, Output file: sum.out, Time Limit: 1 sec, Memory Limit: 64 MB

Дана бесконечная последовательность (-1) + (-1) + 1 + (-1) + 2 + 3 + 4 + (-1) + 5 + 6 + ... Для любого целого неотрицательного k на 2^k-м месте расположены (-1). Остальные места занумерованы по порядку, начиная с 1. Найти сумму первых N элементов последовательности.

Input

Во входном файле задаётся N (0<N<10^8).

Output

В выходной файл выведите сумму первых N элементов заданной последовательности.

Sample Input


10

Sample Output


17

Problem B. Монеты

Input file: coins.in, Output file: coins.out, Time Limit: 1 sec, Memory Limit: 64 MB

Имеется N монет достоинствами P1, P2, ... , PN дуриков. Мальчик Петя хочет узнать S - количество способов выбрать из этих монет Q дуриков. Монеты одинакового достоинства считаются одинаковыми.

Input

Во входном файле в первой строке находятся два целых числа N и Q (1<=N<=50, 1<=Q<=5000). Во второй строке записано N целых чисел - P1, P2, ... , PN (1<=Pi<=100).

Output

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

Sample Input

5 3
1 2 1 1 2

Sample Output

2

Problem C. Печать

Input file: print.in, Output file: print.out, Time Limit: 3 sec, Memory Limit: 64 MB

В Московском Институте Оптимизаций был разработан новый протокол, который используется для передачи данных на принтер. Согласно этому протоколу в режиме печати текстовых файлов принтер "понимает" три команды:

  • Letter('<символ>'); - печатает символ, указанный в скобках;
  • Repeat(<число>); - повторяет печать последних N символов, где N - число, указанное в скобках;
  • End. - завершает печать файла.
Ваша задача заключается в том, чтобы написать программу, которая, получая на входе строку символов оптимальным образом, составляет программу для печати этой строки (оптимальным образом - значит программа должна содержать минимально возможное количество команд).

Input

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

Output

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

Sample InputSample Output
BABBAABBAB
8
Letter('B');
Letter('A');
Letter('B');
Letter('B');
Letter('A');
Repeat(4);
Letter('B');
End.
word
5
Letter('w');
Letter('o');
Letter('r');
Letter('d');
End.

Problem D. Морской бой

Input file: sea.in, Output file: sea.out, Time Limit: 1 sec, Memory Limit: 64 MB

Вам дано расположение кораблей на доске 10х10 при игре в морской бой. На ней по правилам должно быть размещено:

  • четырехпалубных - 1 шт.;
  • трехпалубных - 2 шт.;
  • двухпалубных - 3 шт.;
  • однопалубных - 4 шт.
K-палубный корабль представляется в виде вертикальной или горизонтальной полоски 1xK. Различные корабли не должны иметь общих точек. Ваша задача для данного набора досок указать, соответствуют ли они описанным правилам.

Input

В первой строке записано число N (1<N<10) - количество досок. Каждая доска описывается 10 строками по 10 символов. Символ "0" обозначает, что клетка пуста, а символ "*", что занята. Описания досок разделяются пустыми строками.

Output

Выведите N строк YES или NO. Первое слово выводите, если доска соответствует правилам, а второе в противном случае.

Sample Input

1
****000000
0000000000
***00***00
0000000000
00000000**
000**00000
00000000**
000*000000
00000*00*0
0*00000000

Sample Output

YES

Problem E. Автостоп

Input file: stop.in, Output file: stop.out, Time Limit: 1 sec, Memory Limit: 64 MB

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

Input

Во входном файле в первой строке записано два натуральных числа N и M (1<=N<=15000, 1<=M<=15000). Далее следует N чисел - последовательность координат фонарей. Затем M чисел - последовательность координат голосующих. Все координаты целые, по модулю не превосходящие 10^6. Числа во входном файле разделяются пробелами и/или переводами строк.

Output

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

Sample Input

2 2
5 10
4 8

Sample Output

1 2

Problem F. DoubleVision

Input file: double.in, Output file: double.out, Time Limit: 1 sec, Memory Limit: 64 MB

Компания DoubleVision проектирует чернила и шрифты, которые могут легко читаться и людьми и машинами. Они проектируют свои шрифты на прямоугольной сетке. Справа показан очень простой 5x3 проект для первых пяти цифр:

.o. .o. oo. oo. o.o
o.o .o. ..o ..o o.o
o.o .o. .o. oo. ooo
o.o .o. o.. ..o ..o
.o. .o. ooo oo. ..o
Чернила выглядят, как нормальные черные чернила, но под ними DoubleVision добавляет специальный полимер, который может быть распознан инфракрасным сканером. Человек видит черные чернила вместо полимера, а машина видит полимер вместо черных чернил. Единственная проблема заключается в том, что полимер гораздо дороже чернил, поэтому DoubleVision хочет использовать его как можно меньше. Они обнаружили, что для большинства шрифтов, для того чтобы пометить каждый символ единственным образом, достаточно не более двух пикселей полимера. Но добавляя полимер к одному или двум пикселям на символ, они решительно понижают затраты при обеспечении 100% точности в своих сканерах. Показанный ниже шрифт отражает это: пиксели, которые определяют каждый символ единственным образом, отмечены "#". (Имеются и другие варианты, которые работали бы.) Вы должны написать программу, которая определяет, можно ли данный шрифт пометить таким способом, и если это так, то пометить его.
 
.#. .o. #o. oo. o.#
#.o .#. ..o ..o o.o
o.o .o. .o. #o. ooo
o.o .o. #.. ..o ..o
.o. .o. ooo #o. ..o

Input

Входной файл начинается со строки, содержащей три положительных целых числа n, r и c, разделенных пробелом: n - число символов в шрифте, r - число строк в сетке, c - число столбцов в сетке. Следующие r строк содержат изображение каждого символа в формате, используемом в примерах: точка "." означает не закрашенную часть сетки, а малая "o" означает пиксель, смежные сетки отделяются пробелом. Длина каждой строки не превышает 79 символов (не считая символа конца строки), r не превышает 10.

Output

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

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

Sample InputSample Output
3 2 2
oo oo .o
o. .o o.
impossible
3 2 2
oo oo .o
o. .o oo
#o #o .o
#. .# ##
5 5 3
.o. .o. oo. oo. o.o
o.o .o. ..o ..o o.o
o.o .o. .o. oo. ooo
o.o .o. o.. ..o ..o
.o. .o. ooo oo. ..o
.#. .o. #o. oo. o.#
#.o .#. ..o ..o o.o
o.o .o. .o. #o. ooo
o.o .o. #.. ..o ..o
.o. .o. ooo #o. ..o
1 2 4
.o..
...o
.#..
...o