Задача Подняться на лестницу При прохождении компьютерной игры Вася дошел до финального испытания. Ему необходимо взобраться на вершину пирамиды. Вокруг пирамиды идет лестница, однако за долгие годы некоторые из ступенек этой лестницы стали слишком опасными для того, чтобы можно было на них наступать.
Вася очень аккуратно проходил все предыдущие испытания, и поэтому у него есть все подсказки о том, на какие ступеньки наступать нельзя.
Лестница состоит из N ступенек, пронумерованных от 1 до N от основания пирамиды до её вершины, и в ней K опасных ступенек. Кроме того, персонаж Васи за одну секунду может сделать один шаг и подняться на 1, 2, …S ступенек.
До прохождения испытания персонаж стоит перед первой ступенькой, а для успешного его прохождения требуется оказаться на N-ой ступеньке.
Определите минимальное и максимальное время, за которое Вася может пройти финальное испытание.
Формат входных данных
В первой строке входного файла записаны три целых числа N, K и S (1 ≤ N ≤ 200 000, 1 ≤ S 0, то во второй строке записаны K различных целых чисел ai (1 ≤ ai < N) — номера опасных ступенек. Гарантируется, что можно подняться на вершину пирамиды, не наступая на опасные ступеньки. В 80 % тестов N ≤ 1 000.
Формат выходных данных
В единственной строке выходного файла выведите два целых числа: минимальное и максимальное время, за которое Вася может пройти финальное испытание.
a) 5 * 2 - 4
Решение:
Умножение имеет более высокий приоритет, чем вычитание. Поэтому, сначала выполним вычисление умножения: 5 * 2 = 10.
Затем, выполним вычитание: 10 - 4 = 6.
Ответ: 6.
б) 7 * х + 2
Решение:
Умножение имеет более высокий приоритет, чем сложение. Поэтому, сначала выполним вычисление умножения: 7 * х = 7х.
Затем, выполним сложение: 7х + 2.
Ответ: 7х + 2.
в) 8 * х - 3 * (х + у)
Решение:
Выполним умножение: 8 * х = 8х и 3 * (х + у) = 3х + 3у.
Затем, выполним вычитание: 8х - (3х + 3у).
Для выполнения операции в скобках, умножение 3 на каждый из элементов внутри скобок:
8х - 3х - 3у = 5х - 3у.
Ответ: 5х - 3у.
г) v^2 * х * у^2 * х * у
Решение:
По правилам алгебры, умножение можно проводить в любом порядке.
Выполним умножение: v^2 * х = v^2х, у^2 * х = у^2х, v^2х * у^2х = (vх * у)^2х.
Ответ: (vх * у)^2х.
2. Переведем запись с языка Pascal в нормальную форму:
f = (3 * x + 4 * y)/(2 * sqr(к) - 4 * t / y)
Решение:
Нормализация выражения подразумевает разделение на более простые составляющие.
Заменим sqr(к) на к^2, чтобы выразить возведение в квадрат в общепринятой форме:
f = (3 * x + 4 * y)/(2 * к^2 - 4 * t / y)
Затем, выполним умножение и деление в числителе и знаменателе:
f = (3 * x + 4 * y)/(2к^2 - (4 * t) / y)
Ответ: f = (3 * x + 4 * y)/(2к^2 - 4t/y).
Таким образом, мы записали выражения по правилам языка Pascal и перевели запись с языка Pascal в нормальную форму.