#653

Несоставляемое число

Темы: [Быстрая сортировка]

Даны N натуральных чисел. Найти минимальное натуральное число, не представимое суммой никаких из этих чисел, если в эту сумму каждое исходное число может входить не более одного раза.
Ограничения: 1 <= N <= 10 000, значения исходных чисел от 1 до 1 000 000 000.
Ввод: В первой строке находится число N, в следующих N строках - по одному натуральному числу.
Вывод: Вывести одно число.
Примеры

Ввод 1    Ввод 2
4         4
1         1
1         2
1         4
5         8
Вывод 1   Вывод 2
4         16

#654

SMS

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

Сообщения SMS сотового телефона MOBILA составлены из прописных латинских букв. Если буква первая на кнопке, нужно нажать эту кнопку один раз, чтобы добавить букву в сообщение. Если буква вторая - нужно нажать кнопку дважды и т.д. Так, чтобы набрать слово "SMS", нужно нажать

(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)

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

(ABC)(пауза)(ABC)

Если на кнопке три буквы, то, как только такая кнопка нажата три раза, последняя буква добавляется в сообщение немедленно, а следующие нажатия той же кнопки относятся к следующей букве сообщения. Аналогично, если на кнопке четыре буквы, то после четырёх нажатий в сообщение будет добавлена последняя буква. То есть последовательность нажатий

(ABC)(ABC)(ABC)(ABC)(пауза)(ABC)

соответствует сообщению "CAA". К сожалению, сотовые телефоны этой модели давно не производятся, и остался только один такой телефон. Он может произвольно вставлять и игнорировать паузы во время ввода сообщения, что может привести к некоторым изменениям в сообщениях. Например, введя MOSCOWQUARTERFINAL, можно получить вместо этого OMSCMNWQTTARTERPDEINAL. Вы получили SMS-сообщение и знаете, что оригинальное сообщение содержало N букв. Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое Вы получили.

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

В первой строке задана длина оригинального сообщения \(N\). Вторая строка содержит полученное SMS-сообщение. 1 <= \(N\) <= 80, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения - от 1 до 80 букв.

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

Вывести число сообщений из \(N\) букв, которые, будучи набранными на на этом телефоне, могут превратиться в данное сообщение.

Примеры

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

8
ADGJMPTW

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

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

9
ADGJMPTW

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

#656

Дуга на сфере

Темы: [Вычислительная геометрия]

На поверхности планеты, являющейся шаром радиусом \(R\), заданы две точки своими широтой и долготой. Найти минимальную длину пути по поверхности этой планеты из одной точки в другую.

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

В первой строке находится число \(R\), во второй строке заданы широта и долгота первой точки, в третьей строке - широта и долгота второй точки. Широта в градусах от -90 до 90, долгота в градусах от -180 до 180, 100 <= \(R\) <= 10 000, все числа вещественные.

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

Вывести длину пути с двумя знаками после запятой.

Примеры

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

3437.5
-45 -45
45 -45

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

5399.61

#657

Путь коня

Темы: [Обход в ширину]

Дана шахматная доска, состоящая из \(N\)x\(N\) клеток, несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую.

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

В первой строке задано число \(N\). В следующих \(N\) строках содержится по \(N\) символов. Символом # обозначена вырезанная клетка, точкой - невырезанная клетка, \(@\) - заданные клетки (таких символов два). 2 <= \(N\) <= 50.

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

Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом \(@\).

Примеры

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

2
@.
.@

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

Impossible

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

3
@..
...
..@

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

@@.
..@
@.@

#658

Грядки

Темы: [Обход в глубину]

Прямоугольный садовый участок шириной \(N\) и длиной \(M\) метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

* из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
* никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

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

В первой строке находятся числа \(N\) и \(M\) через пробел, далее идут \(N\) строк по \(M\) символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. 1 ≤ \(N\), \(M\) ≤ 200.

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

Вывести одно число - количество грядок на садовом участке.

Примеры

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

5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####

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