Задачи для самостоятельного решения

10.1. Последовательность (6)

В последовательности чисел a₁, a₂, a₃, ... задан первый член, а остальные вычисляются по формуле a_i = (a_i - 1)² mod 10 000. Найти N-й член последовательности.

Ограничения: 0 ≤ a₁ < 10 000, 1 ≤ N ≤ 2 000 000 000, время 1 с.

Ввод из файла INPUT.TXT. В первой строке находятся числа a₁ и N, разделённые пробелом.

Вывод в файл OUTPUT.TXT. Вывести одно число - a_N.

Примеры

Ввод 1 Ввод 2

4 3 0 2000000000

Вывод 1 Вывод 2

256 0

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

10.2. Последовательность 2 (5)

Каждый член последовательности десятичных цифр d₁, d₂, d₃..., начиная с четвёртого, равен последней цифре суммы трёх предыдущих. По заданным d₁, d₂, d₃ найти N-й член последовательности.

Ввод из файла INPUT.TXT. В первой строке находятся цифры d₁, d₂, d₃, разделённые пробелами, во второй - число N.

Вывод в файл OUTPUT.TXT. Вывести одну цифру - d_N.

Ограничения: 1 ≤ N ≤ 10³⁰, время 1 с.

Примеры

Ввод 1 Ввод 2

1 4 8 5 5 5

4 1000000000000000

Вывод 1 Вывод 2

3 5

10.3. Провода (6)

Дано N отрезков провода длиной L₁, L₂, ..., L_N сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.

Ограничения: 1 ≤ N ≤ 10 000, 1 ≤ K ≤ 10 000, 100 ≤ L_i ≤ 10 000 000, все числа целые, время 1 с.

Ввод из файла INPUT.TXT. В первой строке находятся через пробел числа N и К. В следующих N строках - L₁, L₂, ..., L_N, по одному числу в строке.

Вывод в файл INPUT.TXT. Вывести одно число - полученную длину отрезков.

Пример

Ввод

4 11

802

743

457

539

Вывод

200

Подсказка. Использовать метод дихотомии (деления пополам).

10.4. Таблица (8)

Рассмотрим прямоугольную таблицу размером n  m. Занумеруем строки таблицы числами от 1 до n, а столбцы – числами от 1 до m. Будем такую таблицу последовательно заполнять числами следующим образом.

Обозначим через a_ij число, стоящее на пересечении i-ой строки и j-ого столбца. Первая строка таблицы заполняется заданными числами – a₁₁, a₁₂, …, a_1m. Затем заполняются строки с номерами от 2 до n. Число a_ij вычисляется как сумма всех чисел таблицы, находящихся в «треугольнике» над элементом a_ij. Все вычисления при этом выполняются по модулю r.

Например, если таблица состоит из трех строк и четырех столбцов, и первая строка состоит из чисел 2,3,4,5, а r = 40 то для этих исходных данных таблица будет выглядеть следующим образом (взятие по модулю показано только там, где оно приводит к изменению числа):

Требуется написать программу, которая по заданной первой строке таблицы (a₁₁, a₁₂, …, a_1m), вычисляет последнюю строку, как описано выше.

Ввод из файла INPUT.TXT. В первой строке содержатся числа n, m и r (2 ≤ n, m ≤ 2000, 2 ≤ r ≤ 10⁹) – число строк и столбцов таблицы соответственно, а также число, по модулю которого надо посчитать ответ. Следующая строка содержит m целых чисел – первую строку таблицы: a₁₁, a₁₂, …, a_1m. Все a_1i неотрицательны и не превосходят 10⁹.

Вывод в файл OUTPUT.TXT. В единственной строке необходимо вывести m чисел – последнюю строку таблицы: a_n1, a_n2, …, a_nm.

Ограничения: оперативная память до 64 МГБ, время 2 с.

Пример

Ввод

2 3 10

1 2 3

Вывод

3 6 5

10.5. Последовательность 3 (6)

Задана неубывающая последовательность целых чисел. Найти количество пар чисел с заданной разностью D.

Ввод из файла INPUT.TXT. В первой строке задаются через пробел два целых числа: количество членов последовательности N и разность D (2 ≤ N ≤ 10⁶, 1 ≤ D ≤ 10⁶). Во второй строке вводятся через пробел N натуральных чисел последовательности A₁ ≤ A₂ ≤ ...≤ A_N (A_i ≤ 10⁹).

Вывод в файл OUTPUT.TXT. Вывести число пар (A_i, A_j) таких, что A_i – A _j = D.

Ограничения. Время работы на одном тесте до 2 с. Объем используемой памяти до 1 Мгб.

Пример

Ввод

10 7

3 5 12 18 25 40 47 47 48 49

Вывод

4

10.6. Дипломы (4)

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причем, как оказалось, все они имели одинаковые размеры: w – в ширину и h – в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней – дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером w на h. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

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

Ввод из файла INPUT.TXT. Первая строка содержит три целых числа: w, h, n (1 ≤ w, h, n ≤ 10⁹).

Вывод в файл OUTPUT.TXT. Единственная строка должна содержать размер доски.

Пример

Ввод

2 3 10
Вывод

9

Иллюстрация к примеру

10.7. Симпсон Гомер (7)

Гомер Симпсон пожертвовал N долларов на распространение дисков с фильмами о себе. Имеется 3 вида дисков, которые продаются по ценам C₁, C₂ и C₃ долларов. Требуется купить как можно больше дисков так, чтобы осталась неизрасходованной как можно меньшая сумма денег.

Ввод из файла INPUT.TXT. В первой строке задается значение N (1 ≤ N ≤ 2×10⁹). Во второй строке C₁, C₂ и C₃ через пробел (1 ≤ C₁, C₂ , C₃ ≤ 2×10⁹). Все числа целые.

Вывод в файл OUTPUT.TXT. В первой строке вывести общее количество покупаемых дисков. Во второй строке выводится остаток средств. В третьей строке через пробел выводится число покупаемых дисков каждого вида соответственно.

Пример

Ввод

14

5 3 7

Вывод

4

0

1 3 0

Указание. Рассмотреть случаи Min(C₁, C₂, C₃) ≤ 10⁶ и Min(C₁, C₂, C₃) > 10⁶.

11. Вычислительная геометрия

Вычислительная геометрия – один из разделов информатики. Существует большое количество научных и прикладных задач, связанных с вычислительной геометрией.

Рассмотрим сначала типы данных, применяемых для вычислений. Точка на плоскости описывается парой вещественных чисел. При использовании вещественного типа операции сравнения лучше всего оформить специальными функциями, то есть сравнения вида A=B, где A и B вещественные числа, использовать не стоит. Приведем пример [4].

Пусть для хранения вещественного типа используются два десятичных разряда для порядка и шесть разрядов для хранения мантиссы. Есть два числа: A=0.3456710⁴ и B=0.9876510^-4. При сложении и вычитании происходит выравнивание порядков, сложение (вычитание) мантисс и нормализация результата. После выравнивания порядков получим B=0.000000009876510⁴, а после сложения мантисс и будет результат:

A+B = 0. 3456700098765

При шести десятичных разрядах мантиссы после округления окажется, что A+B=A при B>0! В реальных системах тоже есть подобные ограничения на разрядность представления вещественного типа данных. Например, для типа Real в ПАСКАЛе мантиссе отводится 11-12 цифр.

Операцию проверки равенства вещественных чисел можно реализовать следующей функцией:

Function IsEqual(A,B: real): boolean;

Begin

IsEqual:=Abs(A-B)<Eps

{ Eps – константа, определяющая точность, например Eps=1e-10 }

End;