14. День рождения Иванова

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

Считайте, что число гостей не превосходит 100 человек.

Формат входных данных

В первой строке входного файла задано одно число - количество гостей

Формат выходных данных

В единственной строке напечатать число способов рассадки гостей.

Пример

input.txt	output.txt
4	9

15. Железнодорожный состав из N вагонов был собран последовательно в разных городах. Поэтому имеет случайное расположение номеров вагонов.

Сколькими способами можно получить новый состав с упорядоченным по возрастанию номерами вагонов от 1 до N, оцепляя по одному вагоны только с начала или с конца состава и соединяя вагоны только в начало или в конец нового состава.

Формат входных данных

Входной файл в первой строке содержит число N (1≤N≤70) – количество вагонов. В следующей строке заданы N целых чисел – начальное расположение номеров вагонов.

Формат выходных данных

Выходной файл содержит одно число – ответ.

Пример

input.txt	output.txt
3 1 3 2	3

16. Копилка

Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность P_i и вес W_i одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Ограничения: 1 <= E <= F <= 10 000, 1 <= N <= 500, 1 <= P_i <= 50 000, 1 <= W_i <= 10 000, все числа целые, время 2 с.

Формат выходного файла

Ввод из файла input.txt. В первой строке находятся числа E и F, во второй - число N, в следующих N строках - по два числа, P_i и W_i.

Формат выходного файла

Вывод в файл output.txt. Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.". Примеры

input.txt	output.txt
1000 1100 2 1 1 5 2	100 250
1000 1010 2 6 3 2 2	10 16
1000 2000 1 10 3	This is impossible.

17. Возрастающая последовательность

Даны N целых чисел. В заданной последовательности чисел найти возрастающую последовательность максимальной длины.

Формат входных данных

Во входном файле в первой строке записано число N — количество чисел (1≤N≤10000). Во второй строке заданы N целых чисел.

Формат выходных данных

В первой строке выходного файла выведите одно число — количество элементов в полученной возрастающей последовательности, во второй элементы полученной возрастающей последовательности. Если их несколько, напечатать любую из них

Пример

input.txt	output.txt
9 12 1 2 4 3 0 5 1 7	5 1 2 4 5 7