Задачи из книги "Олимпиадные задачи по программированию"
Ф. Меньшиков

Восьмая тренировка

содержание задачника

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

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

Задача 8B. SMS

Сообщения SMS сотового телефона MOBILA (смотрите рисунок) составлены из прописных
латинских букв. Если буква первая на кнопке, нужно нажать эту кнопку один раз, чтобы добавить букву в сообщение. Если буква вторая — нужно нажать кнопку дважды и т. д. Так, чтобы набрать слово «SMS», нужно нажать (PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS) Чтобы ввести две буквы, находящиеся на одной кнопке, нужно между нажатиями клавиши сделать паузу. Например, чтобы ввести сообщение «АА», нужно нажать (АВС)(пауза)(АВС)
Если на кнопке три буквы, то, как только такая кнопка нажата три раза, последняя буква добавляется в сообщение немедленно, а следующие нажатия той же кнопки относятся к следующей букве сообщения. Аналогично, если на кнопке четыре буквы, то после четырех нажатий в сообщение будет добавлена последняя буква. То есть последовательность нажатий (АВС)(АВС)(АВС)(АВС)(пауза)(АВС) соответствует сообщению «САА». К сожалению, сотовые телефоны этой модели давно не производятся, и остался только один такой телефон. Он может произвольно вставлять и игнорировать паузы во время ввода сообщения, что может привести к некоторым изменениям в сообщениях. Например, введя MOSCOWQUARTERFINAL, можно получить вместо этого OMSCMNWQTTARTERPDEINAL. Вы получили SMS-сообщение и знаете, что оригинальное сообщение содержало N букв. Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое вы получили. Ограничения: 1 $\le$ N$\le$ 80, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения — от 1 до 80 букв, время 2 с.
Ввод из файла sms.in. В первой строке задана длина оригинального сообщения N. Вторая строка содержит полученное SMS-сообщение.
Вывод в файл sms.out. Вывести число сообщений из N букв, которые, будучи набранными на этом телефоне, могут превратиться в данное сообщение.
Примеры
Ввод
4
MAMA
Вывод
1

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

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

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

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

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

Дана шахматная доска, состоящая из NхN клеток; несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую. Ограничения: 2 $\le$ N$\le$ 50, время 1 с.
Ввод из файла knightw.in. В первой строке задано число N. В следующих N строках содержится по N символов. Символом # обозначена вырезанная клетка, точкой — невырезанная клетка, @ — заданные клетки (таких символов два). Вывод в файл knightw.out. Если путь построить невозможно, вывести «Impossible», в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом @.
Пример
Ввод
5
.....
.@@..
.....
.....
.....
Вывод
...@.
.@@..
....@
.....
.....

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

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

Ввод из файла beds.in. В первой строке находятся числа N и М через пробел, далее идут N строк по М символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. Вывод в файл beds.out. Вывести одно число — количество грядок на садовом участке.
Пример
Ввод
5 10
##......#.
.#..#...#.
.###....#.
..##....#.
........#.
Вывод
3

содержание задачника