Тренировка S08

Время тестирования приведено для Intel Celeron 400.
Решения должны быть представлены на Turbo Pascal 7.0. Объём памяти, предоставляемый программе, составляет 500 кб.

        Задача A. Несоставляемое число

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

        Задача B. 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 букв. Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое Вы получили.
Ограничения: 1 <= N <= 80, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения - от 1 до 80 букв, время 2 с.
Ввод из файла sms.in. В первой строке задана длина оригинального сообщения N. Вторая строка содержит полученное SMS-сообщение.
Вывод в файл sms.out. Вывести число сообщений из N букв, которые, будучи набранными на на этом телефоне, могут превратиться в данное сообщение.
Примеры 
Ввод 1    Ввод 2    Ввод 3
4         2         80
MAMA      WWW       QUARTERFINAL
Вывод 1   Вывод 2   Вывод 3
1         2         0

        Задача C. Дерево игры

Игра для двух игроков определяется её деревом. Соперники делают ходы по очереди. Первый игрок начинает игру. Игра кончается или вничью, или победой одного из игроков. Листья дерева этой игры могут иметь значения, равные одному из трёх чисел: +1 - победа первого игрока, -1 - победа второго игрока, 0 - ничья. Ваша задача - определить, кто выиграет, если оба противника следуют правильной стратегии.
Ввод из файла gametree.in. Узлы дерева пронумерованы последовательными целыми числами. Корень дерева всегда имеет номер 1. Первая строка входного файла содержит целое N - число узлов в дереве игры. Следующая N - 1 строка описывает узлы - одна строка для каждого узла (за исключением первого). Вторая строка содержит описание второго узла дерева, третья - третьего узла и т.д. Если узел является листом, первый символ строки - L, затем идёт пробел, затем номер родительского узла, ещё пробел и результат игры (+1 - победа первого игрока, -1 - победа второго, 0 - ничья). Если узел внутренний, то строка содержит N - первый символ, затем пробел и номер родительского узла.
Вывод в файл gametree.out. Выводится +1, если выигрывает первый игрок, -1, если второй, и 0 - в случае ничейного исхода.
Ограничения: 2 <= N <= 1000, время 1 с.
Примеры 
Ввод 1    Ввод 2
7         7
N 1       N 1
N 1       N 1
L 2 -1    L 2 -1
L 2 +1    L 2 +1
L 3 +1    L 3 +1
L 3 +1    L 3 0
Вывод 1   Вывод 2
+1        0

Ввод 3 (см. рисунок)
18
N 1
N 1
N 2
L 2 +1
N 3
L 3 +1
L 3 +1
L 4 -1
L 4 +1
N 4
N 6
L 6 -1
L 6 -1
L 11 -1
L 11 +1
L 12 +1
L 12 -1
Вывод 3
+1

        Задача D. Дуга на сфере

На поверхности планеты, являющейся шаром радиусом R, заданы две точки своими широтой и долготой. Найти минимальную длину пути по поверхности этой планеты из одной точки в другую.
Ограничения: широта в градусах от -90 до 90, долгота в градусах от -180 до 180, 100 <= R <= 10 000, все числа вещественные, время 1 с.
Ввод из файла spherarc.in. В первой строке находится число R, во второй строке заданы широта и долгота первой точки, в третьей строке - широта и долгота второй точки.
Вывод в файл spherarc.out. Вывести длину пути с двумя знаками после запятой.
Примеры 
Ввод 1
4000
45 120
0 120
Вывод 1
3141.59

        Задача E. Путь коня

Дана шахматная доска, состоящая из NxN клеток, несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую.
Ограничения: 2 <= N <= 50, время 1 с.
Ввод из файла knightw.in. В первой строке задано число N. В следующих N строках содержится по N символов. Символом # обозначена вырезанная клетка, точкой - невырезанная клетка, @ - заданные клетки (таких символов два).
Вывод в файл knightw.out. Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом @.
Примеры 
Ввод 1    Ввод 2    Ввод 3
5         5         5
.....     @..@.     @....
.@@..     ..##.     ..#..
.....     .....     .#...
.....     .....     .....
.....     .....     ....@
Вывод 1   Вывод 2   Вывод 3
...@.     @..@.     Impossible
.@@..     ..##.
....@     .@..@
.....     ..@..
.....     @....

        Задача F. Грядки

Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям: Подсчитайте количество грядок на садовом участке.
Ограничения: 1 <= N, M <= 200, время 1 с.
Ввод из файла beds.in. В первой строке находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет.
Вывод в файл beds.out. Вывести одно число - количество грядок на садовом участке.
Примеры 
Ввод 1
5 10
##......#.
.#..#...#.
.###....#.
..##....#.
........#.
Вывод 1
3
Hosted by uCoz