Формат выходных данных
В выходной файл выведите единственное число без лидирующих нулей: A+B.
Пример
input.txt
|
output.txt
|
2
3
|
5
|
Числа до 10100 не умещаются ни в один стандартный тип данных, так что необходимо реализовать сложение длинных чисел.
Задача 10-2. A-B
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
Даны два целых неотрицательных числа A и B. Требуется найти их разность.
Формат входных данных
Во входном файле записаны целые неотрицательные числа A и B по одному в строке (B <= A < 10100).
Формат выходных данных
В выходной файл выведите единственное число без лидирующих нулей: A-B.
Пример
input.txt
|
output.txt
|
7
5
|
2
|
Числа до 10100 не умещаются ни в один стандартный тип данных, так что необходимо реализовать сложение длинных чисел.
Задача 10-3. A*B
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
Даны два целых неотрицательных числа A и B. Требуется найти их произведение.
Формат входных данных
Во входном файле записаны целые неотрицательные числа A и B по одному в строке (A < 10100, B <= 10000).
Формат выходных данных
В выходной файл выведите единственное число без лидирующих нулей: A*B.
Пример
input.txt
|
output.txt
|
2
3
|
6
|
Числа до 10100 не умещаются ни в один стандартный тип данных, так что необходимо реализовать умножение "длинного" числа на "короткое". Благодаря тому, что число B относительно небольшое, операции с ним можно производить как с однозначными.
Задача 10-4. A/B
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
Даны два натуральных числа A и B. Требуется найти их целую часть от их частного. (A div B)
Формат входных данных
Во входном файле записаны натуральные числа A и B по одному в строке (A < 10100, B <= 10000).
Формат выходных данных
В выходной файл выведите единственное число без лидирующих нулей: A div B.
Пример
input.txt
|
output.txt
|
7
3
|
2
|
Числа до 10100 не умещаются ни в один стандартный тип данных, так что необходимо реализовать деление "длинного" числа на "короткое". Благодаря тому, что число B относительно небольшое, операции с ним можно производить как с однозначными.
Занятие 11. Длинный корень.
На этом занятии мы рассмотрим задачу проведение более сложных операций с длинными числами. Для этого нам понадобятся четыре основных арифметических операции, которые мы научились реализовывать на прошлом занятии.
Задача 11-1. Длинный корень
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
2 секунды
|
Формат входных данных
Во входном файле записано натуральное число A (A <= 10100).
Формат выходных данных
В выходной файл выведите максимальное натуральное число B, квадрат которого не превосходит A. Число B следует выводить без лидирующих нулей.
Пример
input.txt
|
output.txt
|
17
|
4
|
Задача 11-1. Длинный корень
(Разбор)
Для начала найдем количество цифр в ответе. Покажем, что квадрат K-значного числа имеет либо 2*K-1, либо 2*K цифр. Действительно, квадрат наименьшего K-значного числа, т.е. числа 10K-1, равен 102K-2, т.е. имеет 2*K-1 цифру; квадрат наибольшего K-значного числа, т.е. числа 10K-1, равен 102K-2*10K+1, т.е. имеет 2*K цифр. Поскольку функция y=x2 монотонно возрастает для всех x>0(т.е. для любых x1,x2>0, таких что x12 выполнено x1222), квадрат любого K-значного числа будет иметь либо 2*K-1, либо 2*K цифр. Следовательно, если число A из входного файла имеет N цифр, то корень из него будет иметь ровно (N+1) div 2 цифр.
Теперь, когда мы знаем количество цифр в числе, будем последовательно подбирать его цифры, начиная со старших. Пусть K старших цифр уже подобраны. Поставим на K+1 место самую большую цифру - 9, и будем уменьшать ее до тех пор, пока квадрат полученного таким образом числа (считая, что все цифры ответа, начиная с K+2 и до самой младшей равны 0) не станет меньше либо равен числу A из входного файла. Таким образом, мы подобрали K+1 цифру нашего числа. Продолжая этот процесс, получим ответ на поставленную задачу
В изложенном решении используется операция умножения "длинных" чисел. Благодаря алгоритму умножения "в столбик" эта задача сводится к многократному умножению "длинных" чисел на "короткие" и сложению "длинных" чисел. Заметим, что эта операция легко выполняется в том случае, если одно из чисел является степенью 10, умноженной на "короткое" число. Тогда достаточно умножить "длинное" число на это короткое, а затем сдвинуть результат на нужное число позиций, что равносильно умножению числа на степень 10.
Пусть aK - число, полученное на K-м шаге нашего приближения, b - очередная цифра, умноженная на 10 в соответствующей степени. Тогда aK+12=(aK+b)2=aK2+2aKb+b2. В стоящей справа сумме все слагаемые, кроме первого, представляют собой частный случай перемножения "длинных" чисел, изложенный выше. А первое слагаемое уже было вычисленно на предыдущем шаге алгоритма.
Занятие 12. Рекурсия - 1.
Рекурсивный вызов - это вызов процедуры (функции) из нее самой.
Рекурсивная процедура (функция) - это процедура (функция), которая совершает рекурсивные вызовы.
Рекурсия - это способ реализации вычислительного процесса, при котором решение задачи описывается с помощью рекурсивной процедуры (функции).
Рассмотрим в качестве примера рекурсивную функцию вычисления факториала:
Function Fact(n : LongInt) : LongInt;
begin
if n=0 then Fact:=1
else Fact:=Fact(n-1)*n;
end;
В данной реализации мы каждый раз сводим нашу задачу к аналогичной задаче меньшей размерности с помощью простой формулы n! = (n-1)! * n до тех пор, пока решение не станет очевидным: 0! = 1.
При написании рекурсивной функции особое внимание следует обратить на два вопроса:
(a) Почему она всегда будет заканчивать работу?
(b) Почему она будет работать правильно, если закончит работу?
Чтобы проверить (a), обычно находят параметр, который
-
уменьшается (увеличивается) с каждым рекурсивным вызовом
-
не может уменьшаться (увеличиваться) до бесконечности
-
уменьшение (увеличение) параметра всегда приводит к одному из крайних значений
-
значение нашей функции при крайних значениях параметра известно либо легко вычисляется
Чтобы проверить (b), убедимся в корректности работы процедуры (функции), считая, что рекурсивные вызовы возвращают правильное значение. После этого корректность работы всей процедуры в целом будет доказана с помощью метода математической индукции(база индукции - правильное значение функции на крайних значениях параметра, переход нами только что обоснован).
Рекурсивная форма организации алгоритма зачастую оказывается изящнее нерекурсивной и дает более компактный текст программы, но работает, как правило, медленнее.
Примечание. В большинстве задач, предложенных в рамках этого занятия, введен искусственный запрет на использование циклов. Этот запрет предназначен для того, чтобы на простых задачах научить Вас применять рекурсию, без которой многие более сложные задачи вызовут большие трудности.
Задача 12-1. N-ое число Фибоначчи
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
Последовательностью Фибоначчи называется последовательность чисел a0, a1, ..., an, ..., где a0 = 0, a1 = 1, ak = ak-1 + ak-2 (k > 1).
Требуется найти N-е число Фибоначчи.
Примечание. В программе запрещается использовать циклы.
Формат входных данных
Во входном файле записано целое неотрицательное число N (N ≤ 30).
Формат выходных данных
В выходной файл выведите N-е число Фибоначчи.
Пример
input.txt
|
output.txt
|
7
|
13
|
Задача решается с помощью рекурсивной функции, которая для n = 0 и n = 1 непосредственно возвращает ответ, а при n > 1 производит рекурсивные вызовы для n - 1 и n - 2, в качестве ответа возвращая сумму результатов.
Задача 12-2. НОД
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
Даны два натуральных числа A и B. Требуется найти их наибольший общий делитель.
Примечание. В программе запрещается использовать циклы.
Формат входных данных
Во входном файле записаны натуральные числа A и B (A, B ≤ 109).
Формат выходных данных
В выходной файл выведите НОД A и B.
Пример
input.txt
|
output.txt
|
12 42
|
6
|
Задача решается с помощью алгоритма Евклида. Этот алгоритм основывается на рекурентном соотношении НОД(a,b) = НОД(b,a mod b) при b > 0, НОД(a,b) = a при b = 0.
Задача 12-3. Генератор
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
Даны два натуральных числа N и K. Требуется вывести в файл все цепочки x1,x2,...,xN такие, что xi - натуральное и 1 ≤ xi ≤ K.
Формат входных данных
Во входном файле записаны натуральные числа N и K (N, K ≤ 6).
Формат выходных данных
В выходной файл выведите все требуемые цепочки в произвольном порядке - по одной на строке. Никакая цепочка не должна встречаться более одного раза.
Пример
input.txt
|
output.txt
|
2 3
|
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
|
Пытаемся на текущее место поставить все числа от 1 до K. Для каждого варианта делаем рекурсивный вызов для следующей позиции. Текущий вариант запоминается в глобальном массиве. При вызове рекурсиной процедуры для (N+1)-го места просто выводим очередную цепочку, записанную в массиве.
Задача 12-4. Без массивов
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
Дано натуральное число N и последовательность из N элементов. Требуется вывести эту последовательность в обратном порядке.
Примечание. В программе запрещается объявлять массивы и использовать циклы (даже для ввода).
Формат входных данных
В первой строке входного файла записано натуральное число N (N ≤ 103). Во второй строке через пробел идут N целых чисел, по модулю не превосходящих 1000, - элементы последовательности.
Формат выходных данных
В выходной файл выведите заданную последовательность в обратном порядке.
Пример
input.txt
|
output.txt
|
3
1 2 3
|
3 2 1
|
Задача решается с помощью рекурсивной процедуры; в качестве параметра ей передаётся M - количество чисел в последовательности, которую надо вывести в обратном порядке. Эта поцедура считывает один элемент, делает рекурсивный вызов от (M-1), после чего выводит считанный элемент.
Занятие 13. Графы. Обход в глубину.
На этом занятии мы рассмотрим применение рекурсии на примере алгоритма обхода графа в глубину.
Обход графа в глубину состоит в следующем: если мы попали в какую-то вершину, то мы помечаем ее как "пройденную" и вызываем себя рекусивно от всех непомеченных вершин, соседних с данной. Таким образом, этот алгоритм обходит все вершины, достижимые из начальной, и каждую вершину обрабатывает не более одного раза.
Приведем текст процедуры обхода в глубину. Как видно, он очень короткий и простой:
procedure dfs(v:integer);
var
i:integer;
begin
used[v]:=true;
for i:=1 to n do
if (a[v,i]=1)and(not used[i]) then
dfs(i);
end;
Топологическая сортировка
Топологической сортировкой называют порядок нумерации вершин ориентированного графа, при котором любое ребро идет из вершины с меньшим номером в вершину с большим.
Очевидно, что не любой граф можно отсортировать топологически. Можно доказать, что топологическая сортировка существует для ацеклических графов и не существует для цикличестких.
Итак, займемся построением топологической сортировки.
Заведем счетчик времени - переменную, которая в начале работы программы равна 0 и увеличивается на 1 при прохождении программы через некоторую контрольную точку. В качестве контрольной точки выберем точку выхода из процедуры обхода в глубину. Для каждой вершины запомним значение счетчика времени, которое она получила в процессе обхода в глубину, в глобальном массиве. Эти числа позволяют определить, обработку какой вершины поиск в глубину закончил раньше, а какой позже. Их можно назвать "временем выхода" поиска из данной вершины.
Теперь будем запускать модифицированный таким образом поиск в глубину из всех непомеченных вершин, пока таковых не останется. После этого отсортируем вершины в порядке уменьшения времени выхода.
Легко проверить, что для ациклического графа полученный порядок является его топологической сортировкой. А для циклических графов топологической сортировки не существует.
Задача 13-1. Обход в глубину
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
Дан неориентированный невзвешенный граф. Для него вам необходимо найти количество вершин, лежащих в одной компоненте связности с данной вершиной.
Формат входных данных
В первой строке входного файла заданы два числа: N и S (1 <= N <= 100; 1 <= S <= N), где N - количество вершин графа, а S - заданная вершина. В следующих N строках записано по N чисел - матрица смежности графа, в которой 0 означает отсутствие ребра между вершинами, а 1 - его наличие. Гарантируется, то на главной диагонали матрицы всегда стоят всегда нули.
Формат выходных данных
Вывести одно целое число - искомое количество.
Пример
input.txt
|
output.txt
|
3 1
0 1 0
1 0 0
0 0 0
|
2
|
Найдем с помощью обхода в глубину компоненту связности, в которой лежит данная вершина, и выведем количество вершин в ней.
Задача 13-2. Банкет
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.
Формат входных данных
В первой строке входного файла дано два числа: N и M (1 <= N,M <= 100), где N - количество ОВП, а M - количество пар ОВП, которые не могут сидеть за одним столом. В следующих M строках записано по 2 числа - пары ОВП, которые не могут сидеть за одним столом.
Формат выходных данных
Если способ рассадить ОВП существует, то в выходной файл выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.
Пример
input.txt
|
output.txt
|
3 2
1 2
1 3
|
YES
2 3
|
Построим граф, в котором вершинами будут ОВП. Ребрами соединим те пары ОВП, которые не могут сидеть за одним столом. Обойдем получившийся граф в глубину, раскрашивая вершины в два цвета. Цвет в терминах нашей задачи будет обозначать номер стола для соответствующей ОВП. Переходя на следующий уровень рекурсии, будем менять цвет, в который мы красим вершину. Если в результате такой раскраски никакое ребро не соединяет две вершины одного цвета, то мы получили искомый способ рассадить ОВП по двум столам, иначе такого способа не существует. Это следует из того факта, что способ их рассадить существует тогда и только тогда, когда в полученном графе нет циклов нечетной длины.
Задача 13-3. Построение
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
Группа солдат-новобранцев прибыла в армейскую часть N666. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо.
Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине.
После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен.
Формат входных данных
Во входном файле cначала идут числа N и M (1 <= N <= 100, 1 <= M <= 5000) - количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B.
|