Разбор Proggy-Buggy Contest

16/12/2015 by Вустянюк Ігор Дмитрович

5 декабря компанией DataArt проводилась международная юмористическая олимпиада по программированию Proggy-Buggy Contest.

Задачи на ней не были сложными, но решать их нужно было очень быстро: на 13 задач отводилось 42 минуты времени.

В Одесском офисе DataArt было рекордное количество команд-участинков среди всех городов, принимавших мероприятие. Среди участников была команда ONU_Rabid_Pandas (Марченко, Илларионова, Вустянюк), которая подготовила разбор задач соревнования:

Условия

Разбор

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

Related Images:

Возведение в целую степень

01/09/2015 by Вустянюк Ігор Дмитрович

В заметке описаны четыре простейших алгоритма возведения в целую степень: наивный алгоритм, быстрый рекурсивный алгоритм и две схемы бинарного итеративного алгоритма. На этих примерах проиллюстрированы основные методы доказательства корректности алгоритма: по индукции и методом инварианта.

Приведена реализация модулярного возведения в степень на С++ с предотвращением переполнения.

Дан краткий обзор материалов по множественному возведению в степень, описаны некоторые приложения темы в олимпиадных задачах.

Описан тест простоты Ферма и основанный на нём эффективный тест простоты для чисел, не превосходящих [latex] {10}^{21} [/latex].

Прелюдия

Понятие степени с целым положительным показателем может быть определено на любой алгебраической структуре с ассоциативной бинарной операцией. Можно возводить в степень числа, перестановки, матрицы, многочлены… Любой из приведённых ниже алгоритмов пригоден для всех указанных случаев, если соответствующим образом реализовать оператор умножения.
Если в структуре есть нейтральный элемент [latex] e [/latex], то можно определить возведение в нулевую степень как [latex] a^{0} = e [/latex]. На практике мы обычно имеем дело именно с этим случаем
Для каждого обратимого элемента структуры [latex] \left( M, * \right) [/latex] можно определить степени с отрицательным показателем, положив [latex] a^{n} = a^{-(-n)} [/latex] для всех [latex] n < 0 [/latex]. Для обработки этого случая достаточно в начале каждого из приведённых ниже алгоритмов реализовать следующий псевдокод:

Python

if (n < 0): if (is_invertible(a)): return (inverse(a), -n) else: error("Элемент необратим")

1
2
3
4
5

if (n < 0):
if (is_invertible(a)):
return (inverse(a), -n)
else:
error("Элемент необратим")

где функция is_invertible проверяет является ли элемент обратимым, а функция inverse возвращает для обратимого элемента его обратный.

Итак, пусть есть непустое множество [latex] M [/latex], на котором задана ассоциативная бинарная операция [latex] * [/latex], относительно которой в [latex] M [/latex] есть нейтральный элемент [latex] e [/latex]. Будем считать, что у нас перегружен оператор умножения [latex] * [/latex], а также что есть алгоритм [latex] e() [/latex], возвращающий нейтральный элемент структуры [latex] \left(M,*\right) [/latex]. Кроме того, деление у нас целочисленное (как в С/С++ и Java), т.е. результатом вычисления выражения [latex] 5 / 2 [/latex] является число [latex] 2 [/latex].

Самой «дорогой» по времени выполнения операцией, встречающейся в этих алгоритмах является умножение, поэтому под сложностью алгоритма возведения в степень будем понимать функцию [latex] T(n) [/latex], сопоставляющую показателю степени [latex] n [/latex] количество умножений, необходимое рассматриваемому алгоритму для возведения в степень [latex] n [/latex] произвольного элемента из [latex] M [/latex].

NB! Алгоритмы приведены на языке Python. Я видел, что этот подход используется во многих онлайн-курсах по Computer Science и многих вводных курсах в программирование. На выбор Python в качестве языка-иллюстратора есть, по крайней мере, три причины:

синтаксис минималистичный и, как говорят в английском, self-explanatory, поэтому код Python похож на псевдокод, легко воспринимается и очень легко переводится на любой другой язык программирования
код получается очень компактным: вложенность конструкций регулируется отступами, поэтому нет большого количество скобок; отсутствие необходимости указывать тип переменных и возвращаемый тип функций существенно сокращает используемое количество ключевых слов
наличие множественного возврата из функций и параллельного присваивания делает код в большей мере соответствующим интуитивному восприятию алгоритмов

Наивный алгоритм

Наивный алгоритм основан на том, что [latex] a^{n} = [/latex] [latex]\begin{cases}e & \text{} n=0 \\a * a^{n-1} & \text{} n>0\end{cases} [/latex].

Рекурсивно PythonC++Итеративно PythonC++

# Рекурсивная реализация
def pow(a,n):
	if (n == 0):
		return e()
	return a * pow(a, n-1)

# Рекурсивная реализация

def pow(a,n):

if (n == 0):

return e()

return a * pow(a, n-1)

// Рекурсивная реализация
int pow(double a, int n) {
	return n == 0? 1: a * pow(a, n-1);
}

// Рекурсивная реализация

int pow(double a, int n) {

return n == 0? 1: a * pow(a, n-1);

}

# Итеративная реализация
def pow(a,n):
	r = e()
	for k in range(0,n):
	    r *= a
	return r

# Итеративная реализация

def pow(a,n):

r = e()

for k in range(0,n):

r *= a

return r

// Итеративная реализация
int pow(double a, int n) {
	double r = 1.0;
	for (int i = 0; i < n; i++) r *= a;
	return r;
}

// Итеративная реализация

int pow(double a, int n) {

double r = 1.0;

for (int i = 0; i < n; i++) r *= a;

return r;

}

Доказательство корректности обеих версий алгоритма легко проводится индукцией с учётом отмеченного выше рекуррентного соотношения. В итеративной реализации очевидно, что для завершения алгоритма при [latex] n > 0 [/latex] необходимо [latex] n [/latex] умножений.

Для рекурсивной реализации это также нетрудно доказать. Отметим, что [latex] T(0) = 0 [/latex] и что при [latex] n > 0 [/latex]

[latex] T(n) = 1 + T(n-1) [/latex]

(нам нужно столько умножений, сколько нужно для вычисления [latex] a ^ {n-1} [/latex] , и ещё одно умножение для вычисления [latex] a * pow(a, n-1) [/latex]). А поэтому

[latex] T(1) = 1 + T(n-1) = 1 + 0 = 1 [/latex]

если [latex] T(n) = n [/latex], то [latex] T(n+1) = 1 + T(n) = 1 + n [/latex]

и, по принципу математической индукции, [latex] T(n) = n [/latex].

Время линейно зависит от [latex] n [/latex], поэтому для возведения в степень с показателем, например, [latex] 10^{18} [/latex] понадобится… ну очень много времени. А ведь в криптографии приходится иметь дело с числами длиной в сотни и иногда даже тысячи битов, поэтому данный алгоритм для возведения в столь большие степени абсолютно неприменим. В олимпиадных задачах тысячебитная степень вряд ли встретится, но вот степень с восемнадцатью нулями вполне возможна. Поэтому у нас есть все причины перейти к следующему алгоритму.

Быстрый рекурсивный алгоритм

Этот алгоритм основан на том, что [latex] a^{n} = [/latex][latex]\begin{cases}\left(a^{2}\right)^{\frac{n}{2}} & \text{} n\equiv_{2} 0 \\a * \left(a^{2}\right)^{\frac{n}{2}} & \text{} n \not \equiv_{2} 0 \end{cases} [/latex].

PythonC++

def pow(a,n):
    if (n == 0):
        return e()
    if (n == 1):
        return a
    if (n % 2 == 0):
        return pow(a*a, n // 2)
    return a * pow(a*a, n // 2)

def pow(a,n):

if (n == 0):

return e()

if (n == 1):

return a

if (n % 2 == 0):

return pow(a*a, n // 2)

return a * pow(a*a, n // 2)

int pow(double a, int n) {
	return n == 0? 1 : n % 2? a * pow(a, n - 1): pow(a * a, n / 2);
}

int pow(double a, int n) {

return n == 0? 1 : n % 2? a * pow(a, n - 1): pow(a * a, n / 2);

}

Доказательство корректности

Докажем следующую теорему: для любых [latex] a \in M [/latex] и [latex] n \in \mathbb{N}_{0}[/latex], поданных на вход алгоритма pow, этот алгоритм завершается и возвращает [latex] a ^ {n} [/latex]. Доказательство будем проводить индукцией по [latex] n [/latex]. При [latex] n = 0 [/latex] или [latex] n = 1 [/latex] алгоритм корректно завершается при любом [latex] a \in M [/latex]. Пусть [latex] n > 1 [/latex] и для всех [latex] 0 \leq k < n [/latex] алгоритм корректно завершается при любом [latex] a \in M [/latex].

Подадим на вход алгоритма произвольное [latex] a \in M [/latex] и рассмотрим два случая, в зависимости от чётности/нечётности числа [latex] n [/latex]. В обоих случаях алгоритм делает рекурсивный вызов [latex] pow \left( a \cdot a, n/2 \right) [/latex]. По предположению индукции, на входной паре [latex] \left(a \cdot a, n/2 \right) [/latex] алгоритм завершается. Значит, на входной паре [latex] \left( a, n \right) [/latex] алгоритм также завершится. Осталось показать, что он возвратит правильный результат.

Если [latex] n [/latex] чётное, то алгоритм возвращает

[latex] pow \left( a \cdot a, n/2 \right) = {\left( a \cdot a \right)} ^{\frac{n}{2}} = a^{n} [/latex]

Если [latex] n [/latex] нечётное, то алгоритм возвращает

[latex] a \cdot pow \left( a \cdot a, n/2 \right) = a \cdot {\left( a \cdot a \right)} ^{\frac{n-1}{2}} = a^{n} [/latex]

Первая оценка времени

Проанализируем время работы. [latex] T(0) = T(1) = 0 [/latex], а при [latex] n > 1 [/latex]

[latex] T\left( n \right) = [/latex] [latex]\begin{cases}1 + T(n/2) & \text{} n \equiv_{2} 0 \\2 + T(n/2) & \text{} n \not \equiv_{2} 0\end{cases} [/latex]

Из приведённого соотношения следует, что для любого [latex] n > 1 [/latex]

[latex] T(n) \leq 2 + T(n/2) [/latex]

Проведём неформальный анализ функции [latex] T [/latex]:

[latex] T(n) \leq 2 + T(n/2) \leq 4 + T(n/4) \leq 6 + T(n/8) \leq \dots[/latex]

Делить число [latex] n [/latex] на [latex] 2 [/latex] до получения нуля мы можем примерно столько раз, сколько цифр в двоичной записи числа, а их примерно [latex] \log_2 n [/latex]. При каждом делении мы увеличиваем верхнюю границу на [latex] 2 [/latex], поэтому естественно предположить следующую оценку: [latex] T(n) \leq 2 \log_2 n [/latex].

Проведём формальное доказательство этой оценки индукцией по [latex] n > 1 [/latex]. При [latex] n = 2 [/latex] оценка справедлива, поскольку

[latex] T(2) = 1 + T(1) = 1 + 0 = 1 \leq 2 = 2 \cdot 1 = 2 \cdot log_2 2 [/latex]

Пусть [latex] n > 2 [/latex] и для всех [latex] 1 < k < n [/latex] доказываемая оценка справедлива. Тогда

[latex] T(n) \leq 2 + T(n/2) \leq 2 + 2 log_2 (n/2) = 2 + 2 log_2 n — 2 log_2 2 = 2 + 2 log_2 n — 2 = 2 log_2 n[/latex]

где второе неравенство обосновано индукционным предположением, применённым к числу [latex] 1 < n/2 < n [/latex].

Таким образом, для всех [latex] n > 1 [/latex] справедливо неравенство [latex] T(n) \leq 2 \log_2 n [/latex]. А это, по определению нотации «О-большое» означает, что [latex] T(n) = O(\log n) [/latex]. Мы не указываем основание логарифма, поскольку значения логарифма одного и того же числа по двум разным основаниям отличаются на константный множитель, а константы О-большое «съедает».

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

У нас есть асимптотическая оценка сложности алгоритма, но мы также можем посчитать точное количество умножений. Сначала, как и выше, проведём неформальный анализ. При каждом рекурсивном вызове показатель степени делится нацело на [latex] 2 [/latex]. Значит, можем ожидать, что будет примерно [latex] \log_2 n [/latex] рекурсивных вызовов. При каждом вызове будет обязательно произведено умножение при вычислении выражения [latex] a*a [/latex]. Деление нацело на [latex] 2 [/latex] равносильно отсечению крайней правой цифры в двоичной записи числа. Если при текущем вызове значение [latex] n [/latex] являлось нечётным (т.е. если при текущем отсечении последняя цифры была единицей), то будет произведено дополнительное умножение.

Таким образом, можем ожидать, что [latex] T(n) \approx \log_2 n + s(n) [/latex], где [latex] s(n) [/latex] — количество единиц в двоичной записи числа [latex] n [/latex]. Обозначим дополнительно [latex] l(n) = 1 + \left\lfloor \log_2 n \right\rfloor [/latex] — количество цифр в двоичной записи числа [latex] n [/latex]. Поиграв немного со значениями функции [latex] T [/latex] можно прийти к следующему выводу: при любом [latex] n > 1 [/latex] [latex] T(n) = l(n) + s(n) — 2 [/latex].

Докажем это равенство индукцией по [latex] n > 1 [/latex]. При [latex] n = 1 [/latex] имеем [latex] T(1) = 0 = 1 + 1 — 2 = l(n) + s(n) — 2 [/latex]. Пусть [latex] n \geq 2 [/latex] и для всех [latex] 1 \leq k < n [/latex] доказываемая оценка справедлива. Двоичная запись числа [latex] n [/latex] получается из двоичной записи числа [latex] n/2 [/latex] приписыванием нуля (если [latex] n [/latex] чётное) или единицы (если [latex] n [/latex] нечётное). С учётом этого замечания получаем:

если [latex] n [/latex] чётное, то [latex] l(n) = l(n/2) + 1 [/latex], [latex] s(n) = s(n/2) [/latex] и [latex] T(n) = 1 + T(n/2) = 1 + l(n/2) + s(n/2) — 2 = l(n) + s(n) — 2 [/latex]
если [latex] n [/latex] нечётное, то [latex] l(n) = l(n/2) + 1 [/latex], [latex] s(n) = s(n/2) + 1 [/latex] и [latex] T(n) = 2 + T(n/2) = 2 + l(n/2) + s(n/2) — 2 = l(n/2) + s(n/2) = l(n) — 1 + s(n) — 1 = l(n) + s(n) — 2 [/latex]

Бинарный алгоритм

Быстрый рекурсивный алгоритм можно превратить в быстрый итеративный, просматривая двоичные цифры числа [latex] n [/latex]. Просматривать их можно слева направо, а можно справа налево. Соответственно получаем две версии алгоритма. Иногда их называют бинарным алгоритмом возведения в степень слева направо (или справа налево). Кормен и соавторы используют название «метод многократного возведения в квадрат».

В англоязычных источниках описанные методы встречаются под названиями «exponentiation by squaring», «exponentiation by repeated squaring», «square-and-multiply exponentiation», «binary exponentiation». Обычно рассматривается один из методов, а второй предлагается в качестве упражнения. Но мы рассмотрим оба.

Схема «слева направо»

Пусть количество цифр в числе [latex] n [/latex] есть [latex] l(n) = t [/latex]: [latex] \left( n_{t-1} \dots n_{0} \right)_{2} [/latex]. Для каждого [latex] k \in \left[ 0 \dots t-1 \right] [/latex] обозначим [latex] m_{k} = \left( n_{t-1} \dots n_{k} \right)_{2} [/latex].

Если [latex] k = 0 [/latex], то [latex] m_k = n[/latex] и поэтому [latex] a ^{m_k} = a^{n} [/latex].

Если [latex] 0 < k \leq t-1 [/latex], то

[latex] m_{k-1} = \left( n_{t-1} \dots n_{k} n_{k-1} \right)_{2} = [/latex] [latex] 2\left( n_{t-1} \dots n_{k} \right)_{2} + n_{k-1}= 2 m_{k} + n_{k-1}[/latex]

и поэтому

[latex] a^{m_{k-1}} = \left( a^{m_{k}} \right) ^ {2} a^{n_{k-1}} = [/latex][latex]\begin{cases}\left(a^{m_{k}}\right)^{2} & \text{} n_{k-1} = 0 \\a * \left(a^{m_{k}}\right)^{2} & \text{} n_{k-1} = 1 \end{cases} [/latex]

Получаем следующий алгоритм:

def pow(a,n):
    # Обработка тривиального случая
    if (n == 0):
        return e()
    # Стадия препроцессинга
    D = []
    while (n > 0):
        D.append(n % 2)
        n = n // 2
    t = len(D)
    # Стадия вычислений
    r = a
    for k in range(t-2,-1,-1):
        r *= r
        if (D[k] == 1):
            r *= a
    return r

def pow(a,n):

# Обработка тривиального случая

if (n == 0):

return e()

# Стадия препроцессинга

D = []

while (n > 0):

D.append(n % 2)

n = n // 2

t = len(D)

# Стадия вычислений

r = a

for k in range(t-2,-1,-1):

r *= r

if (D[k] == 1):

r *= a

return r

Отмечу, что процесс «накопления» показателя степени в данном алгоритме по сути идентичен процессу вычисления значения многочлена [latex]\sum_{k=0}^{t}n_{k}x^{k} [/latex] в точке [latex] x = 2 [/latex] по схеме Горнера.

Главным преимуществом данного алгоритм перед алгоритмом по схеме «справа налево» является тот факт, что на стадии домножения (если текущая цифра — единица), умножение всегда происходит на один и тот же элемент. Иногда это позволяет существенно сэкономить время, затрачиваемое на умножение. Например, в тестах простоты встречается ситуация степени с малым основанием и большим показателем. В этом случае умножение на основание является операцией существенно более быстрой, чем умножение на произвольное число, которое может возникнуть в схеме «справа налево».
Оценка времени. Деление на [latex] 2 [/latex] можно считать быстрой операцией. Поэтому, игнорируя детали работы со списками, время на препроцессинг можно оценить как линейно зависящее от [latex] l(n) [/latex]. Оценим количество возведений в квадрат / умножений. В случаях [latex] n = 0 [/latex] и [latex] n = 1 [/latex] не производится ни возведений в квадрат, ни умножений. Если же [latex] n > 1 [/latex], то цикл for в стадии вычислений отработает [latex] l(n)-1 [/latex] шаг и на каждом из них будет произведено возведение в квадрат. При этом «на каждой единице», кроме старшей, будет произведено умножение на [latex] a [/latex]. В итоге получаем, что при [latex] n > 1 [/latex] алгоритму требуется [latex] l(n) — 1 [/latex] возведений в квадрат и [latex] s(n) — 1 [/latex] обычных умножений, где [latex] l(n) [/latex] — количество цифр в двоичной записи числа [latex] n [/latex], [latex] s(n) [/latex] — количество единиц в двоичной записи [latex] n [/latex].

Схема «справа налево»

Если [latex] k = t-1 [/latex], то [latex] m_k = n[/latex] и поэтому [latex] a ^{m_k} = a^{n} [/latex].

Если [latex] 0 \leq k < t-1 [/latex], то

[latex] m_{k+1} = \left( n_{k+1} n_{k} \dots n_{0} \right)_{2} = [/latex] [latex] 2^{k+1} n_{k+1} + \left( n_{k} \dots n_{0} \right)_{2}= 2^{k+1} n_{k+1} + m_{k}[/latex]

и поэтому

[latex] a^{m_{k+1}} = \left( a^{ 2^{k+1} } \right)^{n_{k+1}} a^{m_{k}} =[/latex] [latex]\begin{cases}a^{m_{k}} & \text{} n_{k+1} = 0 \\ a^{2^{k+1}} a^{m_{k}} & \text{} n_{k+1} = 1 \end{cases} [/latex]

Мы могли бы получить алгоритм, похожий на тот, что приведён в схеме «слева направо», но цифры числа можно просматривать «динамически», без предвычисления.

def pow(a,n):
    r = e()
    while (n != 0):
        if (n % 2 == 1):
            r = r * a
        n = n // 2
        if (n != 0)
            a = a * a
    return r

def pow(a,n):

r = e()

while (n != 0):

if (n % 2 == 1):

r = r * a

n = n // 2

if (n != 0)

a = a * a

return r

На примере этого алгоритма рассмотрим, как проводятся доказательства корректности методом инварианта.

Доказательство будем проводить методом инварианта: покажем, что перед циклом и после каждого шага цикла справедлив следующий инвариант: [latex] r a^{n} = A^{N} [/latex], где [latex] A [/latex] и [latex] N [/latex] — первоначальные значения переменных [latex] a [/latex] и [latex] n [/latex].

Предусловие. Перед началом цикла [latex] r a^{n} = e A^{N} = A ^ {N} [/latex].

Сохранение. Предположим, что инвариант справедлив перед некоторым шагом цикла и пусть [latex] \rho, \nu, \alpha [/latex] — текущие значения переменных [latex] r, n, a[/latex]. Если [latex] \nu [/latex] чётное, то после завершения текущего шага будем иметь: [latex] r = \rho [/latex], [latex] a = \alpha ^ {2} [/latex], [latex] n = \frac{\nu}{2} [/latex], а если нечётное, то [latex] r = \rho a [/latex], [latex] a = \alpha ^ {2} [/latex], [latex] n = \frac{\nu — 1}{2} [/latex]. Непосредственно проверяется, что в обоих случаях справедливо равенство [latex] r a ^ {n} = \rho \alpha ^ {\nu}[/latex]. По предположению об инварианте, правая часть равна [latex] A ^ {N} [/latex]. Значит, инвариант после завершения текущего шага сохраняется.

Завершение доказательства.

Если [latex] N = 0 [/latex], то цикл ни разу не запустится и алгоритм завершится, возвратив [latex] e = A^{0} [/latex], т.е. завершится корректно.

Если [latex] N = 1 [/latex], то цикл отработает единственный шаг и алгоритм завершится, возвратив [latex] A = A^{1} [/latex], т.е. завершится корректно.

Если [latex] N > 0 [/latex], то, поскольку на каждому шаге мы целочисленно делим положительное число [latex] N [/latex] на [latex] 2 [/latex], за конечное число шагов цикл завершится. С помощью индукции нетрудно показать, что точное число шагов в этом случае составит [latex] l(N) [/latex] — количество цифр в двоичной записи числа [latex] N [/latex]. После завершения цикла переменная [latex] n [/latex] содержит значение [latex] 0 [/latex] и после последнего шага, по выше доказанному, инвариант сохранялся. Значит, [latex] A ^ { N} = r \cdot a ^ {n} = r \cdot a ^ {0} = r \cdot e = r [/latex], т.е. алгоритм к.

Оценка времени. При [latex] n > 1 [/latex] цикл while, как было сказано выше отработает [latex] l(n) [/latex] шагов, на каждом из которых, кроме последнего, производится возведение в квадрат. При этом на каждом шаге с единицей мы производим умножение. Однако первое умножение — это фактически умножение на [latex] e [/latex], а такие умножения принято исключать из подсчёта. В итоге получаем, что при [latex] n > 1 [/latex] алгоритму требуется [latex] l(n) — 1 [/latex] возведений в квадрат и [latex] s(n) — 1 [/latex] обычных умножений, где [latex] l(n) [/latex] — количество цифр в двоичной записи числа [latex] n [/latex], [latex] s(n) [/latex] — количество единиц в двоичной записи [latex] n [/latex].

Множественное возведение в степень

Напомню, что в записи [latex] a ^ {b} [/latex] элемент [latex] a [/latex] называют основанием степени, а число [latex] b [/latex] — показателем степени. Кроме случая, когда основание и показатель фиксированы, встречаются задачи, когда оснований/показателей много. Эти задачи встречаются в литературе под общим названием множественного возведения в степень (multiexponentiation). Основные приложения — криптография и тестирование простоты.

Три основные задачи множественного возведения в степень:

основание фиксировано, показатели меняются: [latex] a^{b_1}, \dots , a^{b_s} [/latex]
основания меняются, показатель фиксированный: [latex] {a_1}^{b}, \dots , {a_s}^{b} [/latex]

вычисление произведения степеней [latex] {a_1}^{b_1} \cdot \dots {a_s}^{b_s} [/latex]

В каждом из трёх случаев умения эффективно вычислять одну степень недостаточно.

Некоторые из алгоритмов, разработанных для решения этих задач, являются модификациями [latex] 2^k [/latex]-арного алгоритма, описанного выше. Для всех трёх задач активно используют алгоритмы с предвычислением некоторых промежуточных степеней и последующим кобминированием их.

Когда показатель степени фиксированный, один из методов — применение аддитивных цепей. Аддитивная цепь длины [latex] l [/latex] — это последовательность [latex] c_0, \dots, c_{l} [/latex] целых чисел, начинающаяся с единицы и такая, что каждый следующий член равен сумме двух более ранних:

[latex] c_0 = 1 [/latex]

[latex] \forall k \in \left[ 1 \dots l \right] [/latex] [latex] \exists i,j \in \left[ 0 \dots k-1 \right] [/latex] [latex] c_k = c_i + c_j [/latex]

Если задана аддитивная цепь, завершающаяся числом [latex] n [/latex], то по ней легко построить процесс возведения в степень [latex] n [/latex]. Соответственно имеет смысл искать кратчайшую аддитивную цепь, потому что она минимизирует количество умножений. Доказано, что задача нахождения оптимальной аддитивной цепи является NP-полной. Однако иногда поиск такой цепи окупается за счёт последующей экономии на умножениях. Кроме того, существуют эвристические алгоритмы поиска цепей. Обзор аддитивных цепей имеется у Дональда Кнута во втором томе той самой книги.

К сожалению, я не нашёл материалов по этой теме на русском языке. Если вдруг эту заметку кто-то прочитает и его заинтересует обсуждение описанных задач, читатель может обратиться к следующим часто цитируемым источникам:

Handbook of Applied Cryptography (Menezes, van Oorschot, Vanstone, глава 14, раздел 6)

A Survey of Fast Exponentiation Methods (Daniel M. Gordon)

Algorithms for multi-exponentiation (Bodo Moller)

Improved Techniques for Fast Exponentiation (Bodo Moller)

Pippenger’s exponentiation algorithm (Daniel J. Bernstein)

Handbook of Elliptic and Hyperelliptic Curve Cryptography (Cohen et al., глава 9)

Модулярное возведение в степень

В языке Python реализована длинная арифметика: мы можем работать с числами произвольной длины, не опасаясь проблем с переполнением. Однако С/С++ и Java этой особенностью похвастаться не могут. Ниже приведена реализация на С++ алгоритма модулярного возведения в степень. Поскольку в основном алгоритме power используется умножение по модулю, а модуль предполагается большим, то возникает угроза переполнения.

Чтобы предотвратить переполнение при умножении, заметим, что умножение по модулю — это то же возведение в степень, только в аддитивной терминологии,. Значит, мы можем наравне с алгоритмом power возведения в степень реализовать алгоритм mul вычисления кратных. Различий будет ровно два: «умножением» будет сложение, «единицей» будет ноль. Теперь проблема переполнения перенеслась на сложение, дав нам больше пространства для манёвра. Поскольку все фигурирующие в алгоритме mul числа не превосходят модуль, заключаем: если модуль хотя бы в два раза меньше максимального значения типа (в данном случае — значения типа long long), то переполнение нигде не возникнет.

Приведённый ниже алгоритм также демонстрирует один из возможных способов обработки случая отрицательных показателей степени. Как известно, критерием обратимости элемента в кольцах вычетов является его взаимная простота с модулем. Для проверки этого условия и нахождения обратного элемента я использовал расширенный алгоритм Эвклида (функция ext_gcd), реализованный на основе алгоритма 2.107 на стр.67 в Handbook of Applied Cryptography (Menezes et al.).

#include <iostream>
#include <cassert>
using namespace std;
#define L long long

L ext_gcd(L a, L b, L &x, L &y) {
    L x2 = 1, x1 = 0, y2 = 0, y1 = 1, q, r;
    while (b > 0) {
        q = a / b, r = a - q*b, x = x2 - q*x1, y = y2 - q*y1;
        a = b, b = r, x2 = x1, x1 = x, y2 = y1, y1 = y;
    }
    x = x2, y = y2;
    return a;
}

L inv(L a, L m) {
    L x, y, d = ext_gcd(a, m, x, y);
    assert (d == 1);
    return (x > 0 ? x : m + x);
}

L mul(L a, L n, L m) {
	int r = 0;
	while (n != 0) {				
		if (n % 2 == 1)				
			r = (r + a) % m;
		 a = (a + a) % m;
		 n /= 2;			
	}
	return r;
}

L power(L a, L n, L m) {
    if (n < 0) {
        a = inv(a,m);
        n = -n;
    }
	int r = 1;
	while (n != 0) {			
		if (n % 2 == 1)			
			r = mul(r, a, m);
		 a = mul(a, a, m);
		 n /= 2;			
	}
	return r;
}

int main(void) {
	L a, n, m;
	cin >> a >> n >> m;
        cout << power(a, n, m) << endl;
	return 0;
}

#include <iostream>

#include <cassert>

using namespace std;

#define L long long

L ext_gcd(L a, L b, L &x, L &y) {

L x2 = 1, x1 = 0, y2 = 0, y1 = 1, q, r;

while (b > 0) {

q = a / b, r = a - q*b, x = x2 - q*x1, y = y2 - q*y1;

a = b, b = r, x2 = x1, x1 = x, y2 = y1, y1 = y;

}

x = x2, y = y2;

return a;

}

L inv(L a, L m) {

L x, y, d = ext_gcd(a, m, x, y);

assert (d == 1);

return (x > 0 ? x : m + x);

}

L mul(L a, L n, L m) {

int r = 0;

while (n != 0) {

if (n % 2 == 1)

r = (r + a) % m;

a = (a + a) % m;

n /= 2;

}

return r;

}

L power(L a, L n, L m) {

if (n < 0) {

a = inv(a,m);

n = -n;

}

int r = 1;

while (n != 0) {

if (n % 2 == 1)

r = mul(r, a, m);

a = mul(a, a, m);

n /= 2;

}

return r;

}

int main(void) {

L a, n, m;

cin >> a >> n >> m;

cout << power(a, n, m) << endl;

return 0;

}

Алгоритм (точнее, его неотрицательная часть) протестирован на следующих задачах e-olymp:

273. Возведение в степень

480. Возведение в степень — 2 (требуется обработка переполнения)

Отмечу, что приведённая реализация хотя и является достаточно эффективной для олимпиадных задач, всё же допускает много оптимизаций. Одна из них — ускорение модулярного умножения, например, с помощью алгоритма Монтгомери.

Применение в олимпиадных задачах

Линейные рекуррентные соотношения

Возведение в степень матриц может использоваться для быстрого решения линейных рекуррентных соотношений. Рассмотрим частный случай соотношения глубины [latex] 2 [/latex]: [latex] x_{n} = A x_{n-1} + B x_{n-2} [/latex] при [latex] n \geq 2 [/latex], значения [latex] x_{0} [/latex] и [latex] x_{1} [/latex] - произвольные.

Обозначим [latex] X_{n} = \begin{bmatrix}x_{n+1} \\ x_{n}\end{bmatrix} [/latex], [latex] M = [/latex][latex] \begin{bmatrix} A & B \\ 1 & 0 \end{bmatrix} [/latex]. Тогда

[latex] X_{n+1} = \begin{bmatrix}x_{n+2} \\ x_{n+1}\end{bmatrix} = [/latex][latex] \begin{bmatrix}A x_{n+1} + B x_{n} \\ 1 x_{n+1} + 0 x_{n}\end{bmatrix} [/latex][latex] = M X_{n} [/latex]

[latex] X_{n} = M [/latex][latex] X_{n-1} = M^{2} X_{n-2} = \dots = M^{n} X_{0}[/latex]

Предположим, что нам нужно вычислить [latex] x_n [/latex]. По выше сказанному,

[latex] \begin{bmatrix}x_{n+1} \\ x_{n}\end{bmatrix} [/latex] [latex] = X_{n} = M^{n} X_{0} = [/latex] [latex] \begin{bmatrix} p & q \\ r & s \end{bmatrix} [/latex] [latex] \begin{bmatrix}x_{1} \\ x_{0}\end{bmatrix} [/latex] [latex] = \begin{bmatrix}p x_{1} + q x_{0} \\ r x_{1} + s x_{0}\end{bmatrix} [/latex]

т.е. нам достаточно возвести матрицу [latex] M [/latex] в [latex] n [/latex]-ую степень и тогда [latex] x_{n} = r x_{1} + s x_{0} [/latex]

Эта идея легко обобщается на случай рекуррентных соотношений произвольной глубины. Сложность перемножения двух квадратных матриц размера [latex] k \times k [/latex] обычным алгоритмом составляет [latex] k^3 [/latex] умножений, поэтому получаем оценку [latex] k^{3} \log N [/latex] умножений для нахождения [latex] N [/latex]-го члена линейной рекуррентной последовательности глубины [latex] k [/latex].

Метод проверен на задаче e-olymp 5197. Числа Фибоначчи

С кодом моего решения на С++ можно ознакомиться здесь.

С++

#include <iostream>
using namespace std;
#define ull unsigned long long

struct matrix {
	int x11, x12, x21, x22;
	
	matrix() {
		x11 = 1, x12 = 0, x21 = 0, x22 = 1;
	}
	
	matrix(int a, int b, int c, int d) {
		x11 = a, x12 = b, x21 = c, x22 = d;
	}
	
	matrix mul(matrix M) {
		int a, b, c, d;
		a = (x11*M.x11 + x12*M.x21) % 1000;
		b = (x11*M.x12 + x12*M.x22) % 1000;
		c = (x21*M.x11 + x22*M.x21) % 1000;
		d = (x21*M.x12 + x22*M.x22) % 1000;
		return matrix(a,b,c,d);
	}
	
	void print() {
		cout << x11 << " " << x12 << endl << x21 << " " << x22 << endl;
	}
};

matrix power(matrix A, ull n) {
	if (n == 0)
		return matrix();
	if (n == 1)
		return A;
	if (n % 2 == 0)
		return power(A.mul(A), n/2);
	if (n % 2 == 1)
		return A.mul(power(A.mul(A), n/2));
}

int main() {
	ull n;
	int tmp, x, y;
	matrix A(1,1,1,0), B;
	while (cin >> n) {
		B = power(A,n-1);
		cout << (B.x21 + B.x22) % 1000 << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

#define ull unsigned long long

struct matrix {

int x11, x12, x21, x22;

matrix() {

x11 = 1, x12 = 0, x21 = 0, x22 = 1;

}

matrix(int a, int b, int c, int d) {

x11 = a, x12 = b, x21 = c, x22 = d;

}

matrix mul(matrix M) {

int a, b, c, d;

a = (x11*M.x11 + x12*M.x21) % 1000;

b = (x11*M.x12 + x12*M.x22) % 1000;

c = (x21*M.x11 + x22*M.x21) % 1000;

d = (x21*M.x12 + x22*M.x22) % 1000;

return matrix(a,b,c,d);

}

void print() {

cout << x11 << " " << x12 << endl << x21 << " " << x22 << endl;

}

};

matrix power(matrix A, ull n) {

if (n == 0)

return matrix();

if (n == 1)

return A;

if (n % 2 == 0)

return power(A.mul(A), n/2);

if (n % 2 == 1)

return A.mul(power(A.mul(A), n/2));

}

int main() {

ull n;

int tmp, x, y;

matrix A(1,1,1,0), B;

while (cin >> n) {

B = power(A,n-1);

cout << (B.x21 + B.x22) % 1000 << endl;

}

return 0;

}

Разрешимость квадратного уравнения по простому модулю

Пусть [latex] p > 2 [/latex] - простое число и [latex] a, b, c \in \mathbb{Z}_{p} [/latex]. Можно показать, что разрешимость в [latex] \mathbb{Z}_{p} [/latex] квадратного уравнения [latex] a x^{2} + bx + c = 0 [/latex] равносильна тому, что в [latex] \mathbb{Z}_{p} [/latex] существует квадратный корень из [latex] D = b^{2} - 4ac [/latex] . По критерию Эйлера, это имеет место, если и только если [latex] D^{p-1} \equiv_p 1 [/latex] .

Получаем следующий алгоритм проверки квадратного уравнения на разрешимость: нужно возвести в степень "модуль минус один" дискриминант уравнения и сравнить результат с единицей.

e-olymp 3234. Квадратное уравнение 1

С кодом решения на С++ можно ознакомиться здесь.

С++

#include <stdio.h>
#include <iostream>
using namespace std;
#define ull unsigned long long

int quick_pow(int a, int n, int m) {
	ull r = 1, p = a % m;
	for (; n > 0; n /= 2) {
		if (n % 2 == 1)
			r = (r * p) % m;
		p = (p * p) % m;
	}
	return r;
}

int main() {
	int t;
	scanf("%d", &t);
	ull a, b, c, p, D, tmp;
	for (int k = 0; k < t; k++) {
		scanf("%llu %llu %llu %llu", &a, &b, &c, &p);
		D = ((b*b % p) - (4*(a*c % p) % p) + p) % p;
		if (D == 0)
			printf("YES\n");
		else {
			tmp = quick_pow(D,(p-1)/2, p);
			if (tmp == 1)
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
	return 0;
}

#include <stdio.h>

#include <iostream>

using namespace std;

#define ull unsigned long long

int quick_pow(int a, int n, int m) {

ull r = 1, p = a % m;

for (; n > 0; n /= 2) {

if (n % 2 == 1)

r = (r * p) % m;

p = (p * p) % m;

}

return r;

}

int main() {

int t;

scanf("%d", &t);

ull a, b, c, p, D, tmp;

for (int k = 0; k < t; k++) {

scanf("%llu %llu %llu %llu", &a, &b, &c, &p);

D = ((b*b % p) - (4*(a*c % p) % p) + p) % p;

if (D == 0)

printf("YES\n");

else {

tmp = quick_pow(D,(p-1)/2, p);

if (tmp == 1)

printf("YES\n");

else

printf("NO\n");

}

return 0;

}

Интересно, что при всей простоте проверки на разрешимость, для нахождения решения модулярного квадратного уравнения требуются намного более сложные алгоритмы. Более того, эффективного детерминированного алгоритма для этой задачи пока не известно.

Упрощённое возведение в степень по простому модулю

Если модуль [latex] p [/latex] - простое число, то все ненулевые элементы [latex] \mathbb{Z}_p [/latex] обратимы. Согласно малой теореме Ферма, для любого ненулевого [latex] a \in \mathbb{Z}_p [/latex] справедливо сравнение [latex] a^{p-1} \equiv_p 1[/latex]. Но тогда [latex] a ^ {p-2} [/latex] - элемент, обратный к [latex] a [/latex], поскольку [latex] a \cdot a^{p-2} \equiv_p a^{p-1} \equiv_p 1 [/latex].

Тест простоты Ферма

Малая теорема Ферма утверждает, что для любого простого числа [latex] p [/latex] и любого целого [latex] a [/latex], не делящегося на [latex] p [/latex], справедливо сравнение [latex] a^{p-1} \equiv_p 1[/latex]. Верно и обратное утверждение: если целое [latex] n [/latex] таково, что для любого [latex] a [/latex], взаимно простого с [latex] n [/latex], справедливо сравнение [latex] a^{n-1} \equiv_n 1 [/latex], то число [latex] n [/latex] простое.

На этом наблюдении основан вероятностный тест простоты, называемый тестом Ферма. Для проверки на простоту числа [latex] n [/latex] предлагается выбрать случайное [latex] a \in \left[ 1 \cdots n-1 \right] [/latex], возвести [latex] a [/latex] в степень [latex] n-1 [/latex] и сравнить результат с единицей: если результат равен единице, возвратить "простое", иначе - возвратить "составное".

Теорема Ферма гарантирует следующие характеристики алгоритма:

если на вход подано простое число, то алгоритм верно распознает его как простое
если алгоритм возвратил "составное", то число действительно является составным

Если же алгоритм возвратил "простое", то входное число может как быть, так и не быть простым. Поэтому основной вопрос состоит в следующем: какова вероятность того, что алгоритм, получив на вход составное число, назовёт его простым?

Пусть [latex] n [/latex] - составное число. Рассмотрим множество

[latex] G = \left\{x \in \left[ 1 \cdots n-1 \right] : x^{n-1}\equiv_n 1 \right\} [/latex]

Элементы [latex] G [/latex] - это "лжесвидетели простоты", приводящие к неверному ответу. Алгоритм назовёт составное [latex] n [/latex] простым, если и только если случайно выбранное им [latex] a \in \left[ 1 \cdots n-1 \right] [/latex] окажется элементом множества [latex] G [/latex]. Вероятность этого события есть [latex] p = \frac{\left| G \right|}{n-1} [/latex].

Оценим количество элементов во множестве [latex] G [/latex]. Каждый элемент [latex] G [/latex] обратим по модулю [latex] n [/latex], поскольку [latex] x x^{n-1} \equiv_n x^{n} \equiv_n 1 [/latex]. Значит, [latex] G [/latex] является подмножеством [latex] U(\mathbb{Z}_n) [/latex] - группы обратимых по модулю [latex] n [/latex] вычетов. При этом если [latex] x, y \in G [/latex], то

[latex] \left( x \cdot y \right) ^ {n-1} \equiv_n \cdot x^{n-1} y ^{n-1} \equiv 1 \cdot 1 \equiv_n 1[/latex]

т.е. [latex] xy \in G [/latex]. Как известно, замкнутое подмножество конечной группы является подгруппой, поэтому [latex] G [/latex] - подгруппа [latex] U(\mathbb{Z}_n) [/latex].

По теореме Лагранжа, порядок подгруппы [latex] G [/latex] является делителем порядка группы [latex] U(\mathbb{Z}_n) [/latex]. Поэтому если [latex] G \neq U(\mathbb{Z}_n) [/latex], то [latex] \left| G \right| \leq \frac{\left| U(\mathbb{Z}_n) \right|}{2} [/latex] и в этом случае [latex] p \leq \frac{1}{2} [/latex]. Если при сделанном относительно множества [latex] G [/latex] предположении, применить к числу [latex] n [/latex] [latex] k [/latex] независимых тестов Ферма, то вероятность ошибки составит [latex] \frac{1}{2^k} [/latex].
Без предположения [latex] G \neq U(\mathbb{Z}_n) [/latex] приведённые рассуждения неверны и, к несчастью для теста Ферма, существуют числа (их называют числами Кармайкла), для которых [latex] G = U(\mathbb{Z}_n) [/latex] и поэтому описанная оценка вероятности для таких чисел не работает. Известно, что чисел Кармайкла бесконечно много, но встречаются они очень редко: статья в Википедии утверждает, что имеется [latex] 20 138 200 [/latex] чисел Кармайкла между [latex] 1 [/latex] и [latex] {10}^{21} [/latex].

Кроме того, известно, что каждое число Кармайкла имеет не менее трёх различных простых делителей. Это наблюдение доставляет достаточно эффективный алгоритм проверки на простоту чисел, вмещающихся в стандартные целочисленные типы языков C/C++ и Java. Пусть [latex] n \leq {10}^{21} [/latex]. Если [latex] n [/latex] является числом Кармайкла, то у него есть простой делитель, не превосходящий [latex] {10} ^ {7} [/latex]. Все простые числа до десяти миллионов легко получить, например, решетом Эратосфена. Если число [latex] n [/latex] не делится ни на одно из них, то оно не может быть числом Кармайкла. Значит, справедлива полученная выше оценка вероятности и применив к числу [latex] n [/latex] три раза тест Ферма, мы

либо обнаружим, что [latex] n [/latex] составное
либо можем предполагать, что оно простое; вероятность ошибки при этом составит не более [latex] \frac{1}{2^3} = 0.125 [/latex]

Описанный метод проверен на задаче e-olymp 4316. Простые сложности (нужно проверить на простоту 5000 чисел, не превосходящих [latex] {10}^{18} [/latex])

С кодом решения на С++ можно ознакомиться здесь.

C++

#include <stdio.h>
#include <vector>
#include <cstdlib>
using namespace std;

const int M = 1e5;
int L;
vector<long long> primes;

long long Mul(long long a, long long n, long long m) {
	long long r = 0;
	while (n) {
		if (n % 2 == 1)
			r = (r + a) % m;
		a = (a + a) % m;
		n /= 2;
	}
	return r;
}

long long Pow(long long a, long long n, long long m) {
	long long r = 1;
	while (n) {
		if (n % 2 == 1)
			r = Mul(r, a, m);
		a = Mul(a, a, m);
		n /= 2;
	}
	return r;
}

bool fermat(long long n, int iter) {
	if (n == 1)
		return false;
	if (n <= 1e10) {
		for (int k = 0; k < L; k++) {
			if (n == primes[k])
				return true;
			if (n % primes[k] == 0)
				return false;
		}
	}
	for (int k = 0 ; k < iter; k++) {
		long long a = 1 + rand() % (n-1);	// 1 <= a <= n-1
		if (Pow(a, n-1, n) != 1)
			return false;
	}
	return true;
}

int main() {
	bool* A = (bool*) calloc(M+1, sizeof(bool));
	for (int k = 2; k <= M; k++)
		if (!A[k]) {
			primes.push_back(k);
			if (k * 1ll * k <= M)
				for (int j = k*k; j <= M; j += k)
					A[j] = true;
		}
	L = primes.size();
	long long n;
	int t;
	scanf("%d", &t);
	for (int k = 0; k < t; k++) {
		scanf("%lld", &n);
		if (fermat(n,3))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

#include <stdio.h>

#include <vector>

#include <cstdlib>

using namespace std;

const int M = 1e5;

int L;

vector<long long> primes;

long long Mul(long long a, long long n, long long m) {

long long r = 0;

while (n) {

if (n % 2 == 1)

r = (r + a) % m;

a = (a + a) % m;

n /= 2;

}

return r;

}

long long Pow(long long a, long long n, long long m) {

long long r = 1;

while (n) {

if (n % 2 == 1)

r = Mul(r, a, m);

a = Mul(a, a, m);

n /= 2;

}

return r;

}

bool fermat(long long n, int iter) {

if (n == 1)

return false;

if (n <= 1e10) {

for (int k = 0; k < L; k++) {

if (n == primes[k])

return true;

if (n % primes[k] == 0)

return false;

}

for (int k = 0 ; k < iter; k++) {

long long a = 1 + rand() % (n-1); // 1 <= a <= n-1

if (Pow(a, n-1, n) != 1)

return false;

}

return true;

}

int main() {

bool* A = (bool*) calloc(M+1, sizeof(bool));

for (int k = 2; k <= M; k++)

if (!A[k]) {

primes.push_back(k);

if (k * 1ll * k <= M)

for (int j = k*k; j <= M; j += k)

A[j] = true;

}

L = primes.size();

long long n;

int t;

scanf("%d", &t);

for (int k = 0; k < t; k++) {

scanf("%lld", &n);

if (fermat(n,3))

printf("YES\n");

else

printf("NO\n");

}

return 0;

}

На самом деле, для проверки на простоту используют тест Миллера-Рабина, либо ещё более изощрённые алгоритмы. Однако прародителем и идейным вдохновителем многих из этих алгоритмов был именно тест Ферма, поэтому полезно с ним познакомиться и немного поиграться.

Протокол Диффи-Хеллмана

Одним из известнейших приложений алгоритмов возведения в степень является протокол Диффи-Хеллмана. Предположим, что Алиса и Боб хотят иметь общий секрет. Допустим, им нужен общий параметр для некоторого алгоритма шифрования, причём этот параметр должен быть одинаковым для обоих и обменяться им они планируют по открытому каналу связи. Алису и Боба устроит, если параметр мы будем называть «ключом» и он будет элементом некоторой конечной циклической группы. Например, группы обратимых вычетов [latex] U(\mathbb{Z}_p) [/latex] или группы точек на некоторой эллиптической кривой, или любой другой.

Итак, пусть [latex] G [/latex] — конечная циклическая группа порядка [latex] n [/latex] и [latex] g \in G [/latex] — какой-либо её порождающий элемент. Алиса и Боб всем рассказали про [latex] g [/latex]. О нём знают они двое и знают злоумышленники, прослушивающие канал связи. Алиса также выбрала случайное число [latex] a \in \left[1 \dots n \right] [/latex], а Боб выбрал число [latex] b \in \left[ 1 \dots n \right] [/latex]. Алиса вычислила и отправила Бобу элемент [latex] g^{a} [/latex], а он ей — элемент [latex] g^{b} [/latex].

Вот тут и начинается магия. В качестве общего секретного параметра Алиса и Боб могут взять элемент [latex] g^{ab} [/latex]. Хотя Алиса не знает число [latex] b [/latex], но ей известен элемент [latex] g^b [/latex] и она знает, что [latex] \left(g^{b} \right) ^ {a} = g^{ab} [/latex]. Аналогично Боб может вычислить [latex] \left(g^{a} \right) ^ {b} = g^{ab} [/latex].

Однако возникает вопрос: что помешает узнать секретный(!) параметр [latex] g^{ab} [/latex] злоумышленникам, которые прослушивали канал связи? Оказывается, что в некоторых группах задача нахождения элемента [latex] g^{ab} [/latex] по известным [latex] g^{a} [/latex] и [latex] g^{b} [/latex] при неизвестных [latex] a [/latex] и [latex] b [/latex] является вычислительно очень сложной и на сегодняшний день не может быть решена за адекватное время. В частности, в качестве [latex] G [/latex] можно использовать уже упомянутую группу [latex] U(\mathbb{Z}_p) [/latex]

Related Images:

А717б

24/05/2015 by Вустянюк Ігор Дмитрович

Условие

Две правые треугольные матрицы [latex] A [/latex] и [latex] B [/latex] порядка [latex] n [/latex] заданы в виде последовательности [latex] \frac{\left( n + 1 \right) n}{2}[/latex] чисел: сначала идёт [latex] n [/latex] элементов первой строки, затем [latex] n-1 [/latex] элемент второй строки, и т.д. (из последней, [latex] n [/latex] -ой строки берётся только [latex] n [/latex] -ый элемент). Нужно получить в аналогичном виде матрицу

б) [latex] A \left( I + B^{2} \right) [/latex], где [latex] I [/latex] — единичная матрица порядка [latex] n [/latex]

Тест

[latex] \begin{bmatrix} 2 & 2 & 2 \\ 0 & 0 & 3 \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix} = \begin{bmatrix} 4 & 54 & 236 \\
0 & 0 & 111 \\
0 & 0 & 37 \end{bmatrix} [/latex]

Решение

Создадим класс для работы с треугольными матрицами указанного вида и снабдим его основными методами, необходимыми для решения задачи.

У нас будут конструктор матрицы из стандартного потока ввода, конструктор скалярной матрицы, а также будут перегружены операторы сложения, умножения и присваивания.

Код на С++

#include <iostream>
#include <assert.h> 
#include <stdlib.h> 
using namespace std;

class TriMat {
    private:
        int Size;   
        int** M;
    public:
        TriMat(int n) {
            Size = n;
            M = (int**) malloc(Size * sizeof(int));
            for (int k = 0; k < Size; k++) {
                M[k] = (int*) malloc((Size - k) * sizeof(int));
                for (int j = 0; j <= Size - 1 - k; j++)
                    cin >> M[k][j];
            }
        }
        
        // Конструктор скалярной матрицы с заданным элементом на главной диагонали
        TriMat(int n, int a) {
            Size = n;
            M = (int**) malloc(Size * sizeof(int));
            for (int k = 0; k < Size; k++) {
                M[k] = (int*) malloc((Size - k) * sizeof(int));
                M[k][0] = a;
            }
        }
        
        void print() {
            for (int k = 0; k < Size; k++) {
                for (int j = 0; j < k; j++)
                    cout << "\t";
                for (int j = 0; j <= Size - 1 - k; j++)
                    cout << M[k][j] << "\t";
                cout << endl;
            }
        }
        
        int* operator[](size_t k) {
            assert(0 <= k && k < Size);
            return M[k];
        }
        
        void assign(int i, int j, int a) {
            assert(0 <= i && i < Size && 0 <= j && j < Size);
            M[i][j] = a;
        }
        
        int el(int i, int j) {
            assert(0 <= i && i < Size && 0 <= j && j < Size);
            return M[i][j];
        }

   
        TriMat operator+ (TriMat B) {
            TriMat C(Size);
            for (int k = 0; k < Size; k++)
                for (int j = 0; j <= Size - 1 - k; j++)
                    C[k][j] = M[k][j] + B[k][j];
            return C;
        }
        
        TriMat operator= (TriMat B) {
            for (int k = 0; k < Size; k++)
                for (int j = 0; j <= Size - 1 - k; j++)
                M[k][j] = B[k][j];
            return *this;
        }

        TriMat operator* (TriMat B) {
            TriMat C(Size);
            for (int k = 0; k < Size; k++)
                for (int j = k; j < Size; j++) {
                    for (int r = k; r <= j; r++)
                        C[k][j-k] += M[k][r-k] * B[r][j-r];
                }
            return C;
        }
};


int main() {
    int n;
    cin >> n;
    TriMat A(n), B(n), I(n,1), C = A * (I + B*B);
    A.print();
    B.print();
    C.print();
    return 0;
}

#include <iostream>

#include <assert.h>

#include <stdlib.h>

using namespace std;

class TriMat {

private:

int Size;

int** M;

public:

TriMat(int n) {

Size = n;

M = (int**) malloc(Size * sizeof(int));

for (int k = 0; k < Size; k++) {

M[k] = (int*) malloc((Size - k) * sizeof(int));

for (int j = 0; j <= Size - 1 - k; j++)

cin >> M[k][j];

}

// Конструктор скалярной матрицы с заданным элементом на главной диагонали

TriMat(int n, int a) {

Size = n;

M = (int**) malloc(Size * sizeof(int));

for (int k = 0; k < Size; k++) {

M[k] = (int*) malloc((Size - k) * sizeof(int));

M[k][0] = a;

}

void print() {

for (int k = 0; k < Size; k++) {

for (int j = 0; j < k; j++)

cout << "\t";

for (int j = 0; j <= Size - 1 - k; j++)

cout << M[k][j] << "\t";

cout << endl;

}

int* operator[](size_t k) {

assert(0 <= k && k < Size);

return M[k];

}

void assign(int i, int j, int a) {

assert(0 <= i && i < Size && 0 <= j && j < Size);

M[i][j] = a;

}

int el(int i, int j) {

assert(0 <= i && i < Size && 0 <= j && j < Size);

return M[i][j];

}

TriMat operator+ (TriMat B) {

TriMat C(Size);

for (int k = 0; k < Size; k++)

for (int j = 0; j <= Size - 1 - k; j++)

C[k][j] = M[k][j] + B[k][j];

return C;

}

TriMat operator= (TriMat B) {

for (int k = 0; k < Size; k++)

for (int j = 0; j <= Size - 1 - k; j++)

M[k][j] = B[k][j];

return *this;

}

TriMat operator* (TriMat B) {

TriMat C(Size);

for (int k = 0; k < Size; k++)

for (int j = k; j < Size; j++) {

for (int r = k; r <= j; r++)

C[k][j-k] += M[k][r-k] * B[r][j-r];

}

return C;

}

};

int main() {

int n;

cin >> n;

TriMat A(n), B(n), I(n,1), C = A * (I + B*B);

A.print();

B.print();

C.print();

return 0;

}

Ideone (C++)

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Trimat {
    int Size;
    int[][] M;
    
    public Trimat(int n, Scanner in) {
        Size = n;
        M = new int[Size][];
        for (int k = 0; k < Size; k++) {
            M[k] = new int[Size - k];
            for (int j = 0; j < Size - k; j++)
                M[k][j] = in.nextInt();
        }
    }
    
    public Trimat(int n, int a) {
        Size = n;
        M = new int[Size][];
        for (int k = 0; k < Size; k++) {
            M[k] = new int[Size - k];
            M[k][0] = a;
        }
    }
    
    public void print() {
        for (int k = 0; k < Size; k++) {
            for (int j = 0; j < k; j++)
                System.out.print("\t");
            for (int j = 0; j < Size - k; j++)
                System.out.format("%d\t", M[k][j]);
            System.out.println();
        }
    }
    
    public Trimat add(Trimat B) {
        Trimat C = new Trimat(Size, 0);
        for (int k = 0; k < Size; k++)
            for (int j = 0; j < Size - k; j++)
                C.M[k][j] = M[k][j] + B.M[k][j];
        return C;
    }
    
    public Trimat mul(Trimat B) {
        Trimat C = new Trimat(Size, 0);
        for (int k = 0; k < Size; k++) 
            for (int j = k; j < Size; j++)
                for (int r = k; r <= j; r++)
                    C.M[k][j-k] += M[k][r-k] * B.M[r][j-r];
        return C;
    }
}

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        Trimat A = new Trimat(n, in), B = new Trimat(n, in);
        Trimat I = new Trimat(n,1);
        Trimat C = A.mul(I.add(B.mul(B)));
        A.print();
        B.print();
        C.print();
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Trimat {

int Size;

int[][] M;

public Trimat(int n, Scanner in) {

Size = n;

M = new int[Size][];

for (int k = 0; k < Size; k++) {

M[k] = new int[Size - k];

for (int j = 0; j < Size - k; j++)

M[k][j] = in.nextInt();

}

public Trimat(int n, int a) {

Size = n;

M = new int[Size][];

for (int k = 0; k < Size; k++) {

M[k] = new int[Size - k];

M[k][0] = a;

}

public void print() {

for (int k = 0; k < Size; k++) {

for (int j = 0; j < k; j++)

System.out.print("\t");

for (int j = 0; j < Size - k; j++)

System.out.format("%d\t", M[k][j]);

System.out.println();

}

public Trimat add(Trimat B) {

Trimat C = new Trimat(Size, 0);

for (int k = 0; k < Size; k++)

for (int j = 0; j < Size - k; j++)

C.M[k][j] = M[k][j] + B.M[k][j];

return C;

}

public Trimat mul(Trimat B) {

Trimat C = new Trimat(Size, 0);

for (int k = 0; k < Size; k++)

for (int j = k; j < Size; j++)

for (int r = k; r <= j; r++)

C.M[k][j-k] += M[k][r-k] * B.M[r][j-r];

return C;

}

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

Trimat A = new Trimat(n, in), B = new Trimat(n, in);

Trimat I = new Trimat(n,1);

Trimat C = A.mul(I.add(B.mul(B)));

A.print();

B.print();

C.print();

}

Ideone (Java)

Related Images:

e-olimp 3837. Выражения

05/04/2015 by Вустянюк Ігор Дмитрович

Задача

Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (x + y) * (z — w) — арифметическое выражение в инфиксной нотации. Однако легче написать программу, вычисляющую значение выражения, когда оно находится в постфиксной нотации (известная как обратная польская нотация). В постфиксной нотации оператор записывается за своими двумя операндами, которые и сами в могут быть выражениями. Например, x y + z w — * является постфиксной нотацией приведенного выше выражения. Заметим, что для такой записи скобки не нужны.

Для вычисления выражения, заданного в постфиксной нотации, используется алгоритм, работающий со стеком. Стек — это структура данных, поддерживающая две операции:

push: число кладется на верх стека.
pop: число снимается с вершины стека.

Во время вычисления выражение обрабатывается слева направо. Если приходит число, то кладем его на стек. Если приходит оператор, то извлекаем два числа из стека, применяем к ним оператор и результат кладем обратно в стек. Следующий псевдокод обрабатывает оператор O:

a := pop();

b := pop();

push(b O a);

Результатом выражения будет единственное число, оставшееся в стеке.

Предположим, что мы используем вместо стека очередь. Очередь также имеет операции push иpop, но их смысл немного другой:

push: число вставляется в конец очереди.
pop: из начала очереди извлекается число.

Можете ли Вы переписать заданное выражение так, чтобы алгоритм, использующий очередь при его вычислении, давал тот же результат, что и алгоритм вычисления со стеком?

Пояснения к решению

Если задана правильная строка в постфиксной нотации, то алгоритм её вычисления на основе стека выглядит следующим образом:

Просматриваем строку слева направо
Если встречаем переменную, помещаем её в конец стека/очереди
Если встречаем символ оператора * , то выполняем следующие действия: снимаем со стека a, снимаем со стека b и кладём на стек b * a.

По условию задачи, мы должны обрабатывать строки, используя вместо стека очередь, поэтому описанные выше действия примут следующий вид: снимаем с очереди a, снимаем с очереди b и кладём в конец очереди b * a.

Постфиксную запись, рассчитанную на обработку посредством стека, будем называть s-постфиксной, а рассчитанную на обработку очередью — q-постфиксной.

Две записи «вычислятся одинаково» в том и только в том случае, когда соответствующие им деревья синтаксического разбора (англ.: parse tree, далее — ДСР) одинаковы. Идея приведённого ниже алгоритма состоит примерно в следующем: на основе s-постфиксной записи строим ДСР, обходя которое специальным образом, получаем q-постфиксную запись. Нужно обходить дерево по уровням справа налево (под уровнем дерева подразумевается множество всех вершин дерева, равноудалённых от корня; уровни дерева естественным образом нумеруются: корень расположен на уровне 0 и так далее). В приведённом ниже коде функция get_levels генерирует уровни ДСР на основе s-постфиксной нотации в виде вектора строк, k-ая компонента которого соответствует k-му уровню ДСР заданной строки, вершины которого (если таковые имеются) перечислены справа налево. Поскольку у ДСР может быть не больше уровней, чем символов в строке, то создаём вектор как раз с таким числом компонент и инициализируем его компоненты пустыми строками.

Корректность функции get_levels можно доказать индукцией по длине строки, отметим, что если строка содержит более одного элемента, то она имеет вид ФGО, где Ф и G — правильные строки, О — символ оператора. Запустить рекурсивно функцию с предпоследней позиции — всё равно, что применить её к строке G. ДСР этой строки является левым поддеревом для ДСР исходной строки и k-ый уровень этого дерева является (k+1)-ым уровнем ДСР исходной строки (именно поэтому вызываем функцию с параметром depth на 1 больше). По индукционному предположению, дойдя до начала строки G, функция корректно «расставит» уровни ДСР этой строки (с учётом + 1) и завершит свою работу. Аналогично будут правильно расставлены уровни ДСР строки Ф, которое является правым поддеревом исходной строки. Таким образом, все вершины ДСР исходной строки будут правильно расставлены, а поскольку рекурсия вызывается сначала для левого, а потом для правого её поддерева, то и перечислены вершины на каждом уровне будут справа налево.

Код на С++

Ссылка на программу в ideone.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

/* Expr - строка-формула, которую мы обрабатываем
 index - текущий символ в строке Expr
 depth - текущий уровень дерева разбора
 Answer - вектор уровней */

void get_levels(string& Expr, int& index, int depth, vector<string>& Answer) {
	Answer[depth] += Expr[index];
	index--;
	if (isupper(Expr[index+1])) {
		get_levels(Expr, index, depth + 1, Answer);
		get_levels(Expr, index, depth + 1, Answer);
	}
}


int main() {
	int n, index;
	cin >> n;
	string Expr;
	for (int k = 0; k < n; k++) {
		cin >> Expr;						
		vector<string> Answer(Expr.size(), "");
		index = Expr.size() - 1;
		get_levels(Expr, index, 0, Answer);
		for (int k = Expr.size() - 1; k >= 0; k--)
			cout << Answer[k];
		cout << endl;
	}
	return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

/* Expr - строка-формула, которую мы обрабатываем

index - текущий символ в строке Expr

depth - текущий уровень дерева разбора

Answer - вектор уровней */

void get_levels(string& Expr, int& index, int depth, vector<string>& Answer) {

Answer[depth] += Expr[index];

index--;

if (isupper(Expr[index+1])) {

get_levels(Expr, index, depth + 1, Answer);

}

int main() {

int n, index;

cin >> n;

string Expr;

for (int k = 0; k < n; k++) {

cin >> Expr;

vector<string> Answer(Expr.size(), "");

index = Expr.size() - 1;

get_levels(Expr, index, 0, Answer);

for (int k = Expr.size() - 1; k >= 0; k--)

cout << Answer[k];

cout << endl;

}

return 0;

}

Код на Java

Ссылка на программу в ideone.

import java.util.*;
import java.lang.*;
import java.io.*;

class Index {
	int in;
	public Index(int a) {
		in = a;
	}
}

class Main
{
	public static void get_levels(char[] Expr, Index index, int depth, String[] Answer) {
		Answer[depth] += Expr[index.in];
		index.in--;
		if (Character.isUpperCase(Expr[index.in + 1])) {
			get_levels(Expr, index, depth + 1, Answer);
			get_levels(Expr, index, depth + 1, Answer);
		}
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String str = in.nextLine();

		for (int k = 0; k < n; k++) {
			str = in.nextLine();
			char[] Expr = str.toCharArray();
			String[] Answer = new String[Expr.length];
			Arrays.fill(Answer, "");
			Index index = new Index(Expr.length - 1);
			get_levels(Expr, index, 0, Answer);
			for (int j = Expr.length - 1; j >= 0; j--)
				System.out.print(Answer[j]);
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Index {

int in;

public Index(int a) {

in = a;

}

class Main

{

public static void get_levels(char[] Expr, Index index, int depth, String[] Answer) {

Answer[depth] += Expr[index.in];

index.in--;

if (Character.isUpperCase(Expr[index.in + 1])) {

get_levels(Expr, index, depth + 1, Answer);

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

String str = in.nextLine();

for (int k = 0; k < n; k++) {

str = in.nextLine();

char[] Expr = str.toCharArray();

String[] Answer = new String[Expr.length];

Arrays.fill(Answer, "");

Index index = new Index(Expr.length - 1);

get_levels(Expr, index, 0, Answer);

for (int j = Expr.length - 1; j >= 0; j--)

System.out.print(Answer[j]);

System.out.println();

}

Related Images:

e-olimp 122. Горные маршруты

02/04/2015 by Вустянюк Ігор Дмитрович

Задача. Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует разных таких маршрутов (без циклов) между a и b?
Ссылка на задачу

Пояснение к решению

Поиск путей представляет из себя модифицированный обход в глубину. Вместо массива «глобально посещённых» вершин, в которые уже нельзя возвращаться при обходе, я использую массив «локально посещённых» вершин. Это позволяет использовать одну и ту же вершину в разных, в том числе очень длинных и извращённых путях (в стандартном варианте ищется кратчайший путь, а нам нужны все: в том числе длинные и извращённые).

Кроме того, добавлен параметр depth — длина рассматриваемого в данный момент пути (или глубина текущего рекуррентного вызова, если угодно). Этот параметр изначально имеет значение 0 и при каждом вызове сравнивается с максимально допустимым значением. Перед рекуррентным вызовом мы увеличиваем значение depth, ведь длина нового пути будет на 1 больше. После вызова, т.е. возвращаясь на предыдущий уровень рекурсии, мы уменьшаем длину пути (ведь мы «отбросили» последнюю вершину, т.е. длина пути уменьшилась на 1).

Алгоритм работает примерно так: сначала посещаем начальную вершину и помечаем её как локально посещённую. Если она — искомая, увеличиваем количество найденных путей на 1 и алгоритм завершает свою работу (путей без циклов, содержащих более одной вершины, в этом случае быть не может). Если же начальная вершина не совпадает с целевой, то для всех вершин, в которые можно попасть из неё, применяем рекуррентно тот же алгоритм. Если таких вершин нет, алгоритм завершается, возвращая 0 (нет ни одного пути из начальной вершины в конечную). Если же такие вершины имеются, то увеличиваем параметр «глубина» и вызываем для них рекуррентно наш алгоритм. После выхода из рекурсии, возвращаем параметр «глубина» к последнему его значению (тем, что было перед вызовом) и, чтобы мы могли использовать данную вершину в других путях помечаем её как «локально свободную».

Стоит отметить, что в общем случае задача поиска всех простых путей (пусть даже удовлетворяющих определённым условиям, как в данной задаче) является NP-полной, т.е. решается исключительно переборными алгоритами, работающими за неполиномиальное время (более эффективных алгоритмов для решения таких задач на сегодняшний день неизвестно; кто их найдёт, получит миллион долларов; я не нашёл). Также отметим, что простая модификация приведённого алгоритма позволяет не только вычислять количество простых путей указанной длины, но и перечислять их.

Решение на С++

#include <stdio.h>
#include <vector>
#include <stdlib.h>
using namespace std;

struct Graph {
	vector< vector<int> > AdjList;
	int Size;
	
	Graph(int n) {
		vector<int> List;
		for (int k = 0; k < n; k++)
			AdjList.push_back(List);
		Size = n;
	}

	void add_vertex() {					// вершина == целое число == номер этой вершины в списке вершин
		Size++;
		vector<int> List;
		AdjList.push_back(List);
	}
	
	void add_edge(int u, int v) {		// u и v уже должны быть в списке вершин
		AdjList[u].push_back(v);
	}

	int simple_paths(int start, int end, int max_depth) {
		bool* on_path = (bool*) calloc(Size, sizeof(bool));
		int cur_depth = 0;
		int count = 0;
		simple_paths(start, end, on_path, cur_depth, max_depth, count);
		return count;
	}
	
	void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) {
		if (cur_depth <= max_depth) {
			on_path[start] = true;
			if (start == end)
				count++;
			else
				for (int k = 0; k < AdjList[start].size(); k++) {
					int v = AdjList[start][k];
					if (!on_path[v]) {
						cur_depth++;
						simple_paths(v, end, on_path, cur_depth, max_depth, count);
						on_path[v] = false;
						cur_depth--;
					}
				}
		}
	}
	
};


int main() {
	int n, k, a, b, d, tmp1, tmp2;
	scanf("%d %d %d %d %d", &n, &k, &a, &b, &d);
	Graph G(n);
	for (int i = 0; i < k; i++) {
		scanf("%d %d", &tmp1, &tmp2);
		G.add_edge(tmp1 - 1, tmp2 - 1);
	}
	printf("%d\n", G.simple_paths(a-1, b-1, d));
	return 0;
}

#include <stdio.h>

#include <vector>

#include <stdlib.h>

using namespace std;

struct Graph {

vector< vector<int> > AdjList;

int Size;

Graph(int n) {

vector<int> List;

for (int k = 0; k < n; k++)

AdjList.push_back(List);

Size = n;

}

void add_vertex() { // вершина == целое число == номер этой вершины в списке вершин

Size++;

vector<int> List;

AdjList.push_back(List);

}

void add_edge(int u, int v) { // u и v уже должны быть в списке вершин

AdjList[u].push_back(v);

}

int simple_paths(int start, int end, int max_depth) {

bool* on_path = (bool*) calloc(Size, sizeof(bool));

int cur_depth = 0;

int count = 0;

simple_paths(start, end, on_path, cur_depth, max_depth, count);

return count;

}

void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) {

if (cur_depth <= max_depth) {

on_path[start] = true;

if (start == end)

count++;

else

for (int k = 0; k < AdjList[start].size(); k++) {

int v = AdjList[start][k];

if (!on_path[v]) {

cur_depth++;

simple_paths(v, end, on_path, cur_depth, max_depth, count);

on_path[v] = false;

cur_depth--;

}

};

int main() {

int n, k, a, b, d, tmp1, tmp2;

scanf("%d %d %d %d %d", &n, &k, &a, &b, &d);

Graph G(n);

for (int i = 0; i < k; i++) {

scanf("%d %d", &tmp1, &tmp2);

G.add_edge(tmp1 - 1, tmp2 - 1);

}

printf("%d\n", G.simple_paths(a-1, b-1, d));

return 0;

}

Решение на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class myInt {
	int v;
	public myInt(int a) {
		this.v = a;
	}
}

class Graph {
	Vector<Vector<Integer>> AdjList;

	public Graph(int n) {
		AdjList = new Vector<Vector<Integer>>(n);
		for (int k = 0; k < n; k++)
			AdjList.add(new Vector<Integer>());
	}
	
	public void add_vertex() {
		AdjList.add(new Vector<Integer>());
	}
	
	public void add_edge(int u, int v) {
		AdjList.elementAt(u).add(v);
	}
	
	public int simple_paths(int start, int end, int max_depth) {
		boolean[] on_path = new boolean[AdjList.size()];
		myInt cur_depth = new myInt(0);
		myInt count = new myInt(0);
		simple_paths(start, end, on_path, cur_depth, max_depth, count);
		return count.v;
	}
	
	public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) {
		if (cur_depth.v <= max_depth) {
			on_path[start] = true;
			if (start == end)
				count.v++;
			else
				for (int k = 0; k < AdjList.elementAt(start).size(); k++) {
					int v = AdjList.elementAt(start).elementAt(k);
					if (!on_path[v]) {
						cur_depth.v++;
						simple_paths(v, end, on_path, cur_depth, max_depth, count);
						on_path[v] = false;
						cur_depth.v--;
					}
				}
		}
	}
}

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), k = in.nextInt();
		int a = in.nextInt(), b = in.nextInt(), d = in.nextInt();
		int tmp1, tmp2;
		Graph G = new Graph(n);
		for (int i = 0; i < k; i++) {
			tmp1 = in.nextInt();
			tmp2 = in.nextInt();
			G.add_edge(tmp1 - 1, tmp2 - 1);
		}
		System.out.println(G.simple_paths(a-1, b-1, d));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class myInt {

int v;

public myInt(int a) {

this.v = a;

}

class Graph {

Vector<Vector<Integer>> AdjList;

public Graph(int n) {

AdjList = new Vector<Vector<Integer>>(n);

for (int k = 0; k < n; k++)

AdjList.add(new Vector<Integer>());

}

public void add_vertex() {

AdjList.add(new Vector<Integer>());

}

public void add_edge(int u, int v) {

AdjList.elementAt(u).add(v);

}

public int simple_paths(int start, int end, int max_depth) {

boolean[] on_path = new boolean[AdjList.size()];

myInt cur_depth = new myInt(0);

myInt count = new myInt(0);

simple_paths(start, end, on_path, cur_depth, max_depth, count);

return count.v;

}

public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) {

if (cur_depth.v <= max_depth) {

on_path[start] = true;

if (start == end)

count.v++;

else

for (int k = 0; k < AdjList.elementAt(start).size(); k++) {

int v = AdjList.elementAt(start).elementAt(k);

if (!on_path[v]) {

cur_depth.v++;

simple_paths(v, end, on_path, cur_depth, max_depth, count);

on_path[v] = false;

cur_depth.v--;

}

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), k = in.nextInt();

int a = in.nextInt(), b = in.nextInt(), d = in.nextInt();

int tmp1, tmp2;

Graph G = new Graph(n);

for (int i = 0; i < k; i++) {

tmp1 = in.nextInt();

tmp2 = in.nextInt();

G.add_edge(tmp1 - 1, tmp2 - 1);

}

System.out.println(G.simple_paths(a-1, b-1, d));

}

Related Images:

АА18

02/04/2015 by Вустянюк Ігор Дмитрович

Задача

В строке найти первое слово, которое встречается два раза подряд. Слова разделяются одним или несколькими пробелами. Напечатать его.

Пояснение к решению

Идея простая:

последовательно разбиваем строку на отдельные слова с помощью функций стандартной библиотеки
смотрим, не встретилось ли некоторое слово два раза подряд

Решение

Основной вариант:

#include <iostream>
#include <sstream>
using namespace std;

int main() {
   	string str, a, b, tmp;
    getline(cin, str);
	stringstream ss(str);
	ss >> a;
    while (ss >> tmp) {
    	if (a == tmp) {
    		cout << a << endl;
    		return 0;
    	}
    	a = tmp;
    }
	cout << "Нет повторов" << endl;
	return 0;
}

#include <iostream>

#include <sstream>

using namespace std;

int main() {

string str, a, b, tmp;

getline(cin, str);

stringstream ss(str);

ss >> a;

while (ss >> tmp) {

if (a == tmp) {

cout << a << endl;

return 0;

}

a = tmp;

}

cout << "Нет повторов" << endl;

return 0;

}

Перевод на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		String s, t;
		boolean check = true;
		s = in.next();
		while (in.hasNext()) {
            t = in.next();
            if (s.equals(t)) {
            	System.out.println(s);
            	check = false;
            }
            s = t;
        }
        if (check)
	        System.out.println("Нет повторов");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

String s, t;

boolean check = true;

s = in.next();

while (in.hasNext()) {

t = in.next();

if (s.equals(t)) {

System.out.println(s);

check = false;

}

s = t;

}

if (check)

System.out.println("Нет повторов");

}

Старый неаккуратный и медленный вариант:

#include <vector>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

int main()
{
    string str, buf;
    getline(cin, str);
	vector<string> words;
	
    stringstream ss(str); 
    while (ss >> buf)
        words.push_back(buf);

    if (words.size() > 1)
    	for (auto it = words.begin(); it != words.end() - 1; it++)
    		if (*it == *(it + 1))
    			cout << *it;
}

#include <vector>

#include <string>

#include <iostream>

#include <sstream>

using namespace std;

int main()

{

string str, buf;

getline(cin, str);

vector<string> words;

stringstream ss(str);

while (ss >> buf)

words.push_back(buf);

if (words.size() > 1)

for (auto it = words.begin(); it != words.end() - 1; it++)

if (*it == *(it + 1))

cout << *it;

}

Related Images:

e-olimp 6130. Дек неограниченного размера (как список деков)

26/03/2015 by Вустянюк Ігор Дмитрович

Как пишет Википедия в статье Double-Ended Queue, есть три основных способа реализации двухсторонней очереди (она же — дек, дека и т.д.):

— хранить дек в циклическом буфере и расширять при переполнении (при таком подходе реже нужны расширения);

— хранить содержимое дека в массиве, начиная от его центра, и при переполнении расширять массив (например, создавать новый массив и копировать туда содержимое старого);

— хранить дек в виде многих малых массивов, добавляя новые массивы с того или другого конца при необходимости.

Здесь приведу свою реализацию третьим способом: малые деки хранятся в виде двусвязного списка и добавляются/удаляются в соответствующих ситуациях.; конструктор основного дека создаёт единственный малый дек, который заполняется от центра к краям.

Соответствующая задача на e-olimp: 6130 и зачтённое решение.

В этом блоге можно увидеть картинку, иллюстрирующую рассматриваемый метод, и краткое описание того, как можно снабдить дек индексированием, чтобы быстро получать доступ к элементу дека по его индексу (как в массиве).

О плюсах и минусах

Расширения нужно (в теории) производить чаще, чем при первом подходе, но зато не нужно полностью копировать содержимое дека при расширении.

Отмечу, что если хранить в узлах двусвязного списка не малые деки, а отдельные элементы, то тратится в три раза больше памяти, что должно быть чувствительно при необходимости хранить большое количество элементов в деке.

Основным преимуществом рассматриваемого подхода, по сравнению с двумя другими, я считаю как раз более эффективный расход памяти. Основной же недостаток, на мой взгляд, состоит в том, что при цепочке удалений-вставок, приводящей к постоянному переполнению/очищению одного из крайних малых деков, будут очень часто создаваться/удаляться малые деки, что может привести к бОльшим временным затратам, чем при реализации дека другими методами.

#include <iostream>
#include <string>
using namespace std;

const int Max = 1000;		// максимально допустимое число элементов в малом деке

struct node {
	node* prev;
	node* next;
	int* dequeue;
	
	node(node* Pr, node* Ne) {
		prev = Pr;
		next = Ne;
		dequeue = new int[Max]();
	}
	
	void print() {
		for(int k = 0; k < Max; k++)
			cout << dequeue[k] << " ";
		cout << endl;
	}
};

struct Dequeue {
	node* first;
	node* last;
	int f;		// индекс первого свободного элемента в первой деке
	int l;		// индекс последнего свободного элемента в последней деке
	int Size;

	Dequeue() {
		node* N = new node(nullptr, nullptr);
		first = N;
		last = N;
		f = Max/2 - 1;
		l = Max/2;
		Size = 0;
	}

// Управление двусвязным списком
	void add_first () {			// добавляет новый узел в начало списка
		node* N = new node(nullptr, first);
		first -> prev = N;
		first = N;
		f = Max - 1;
	}
	
	void add_last () {		// добавляет новый узел в конец списка
		node* N = new node(last, nullptr);
		last -> next = N;
		last = N;
		l = 0;
	}
	
	void delete_first () {		// удаляет первый узел списка
		node* N = first -> next;
		delete first;
		first = N;
		first -> prev = nullptr;
		f = 0;
	}
	
	void delete_last () {		// удаляет последний узел списка
		node* N = last -> prev;
		delete last;
		last = N;
		last -> next = nullptr;
		l = Max - 1;
	}

// Управление деком
	void push_front (int n) {
		(first -> dequeue)[f] = n;
		f--;
		Size++;
		if (f == -1)		// если первый дек переполнен
			add_first();	// добавляем в начало списка новый дек
	}
	
	void push_back (int n) {
		(last -> dequeue)[l] = n;
		l++;
		Size++;
		if (l == Max)		// если последний дек переполнен
			add_last();		// добавляем в конец списка новый дек
	}
	
	int pop_front () {
		Size--;
		if (f == Max - 1)
			delete_first();
		else
			f++;
		return (first -> dequeue)[f];
	}
	
	int pop_back () {
		Size--;
		if (l == 0)
			delete_last();
		else
			l--;
		return (last -> dequeue)[l];
	}
	
	int front () {
		if (f == Max - 1)
			return ((first -> next) -> dequeue)[0];
		else
			return (first -> dequeue)[f+1];
	}
	
	int back () {
		if (l == 0)
			return ((last -> prev) -> dequeue)[Max - 1];
		else
			return (last -> dequeue)[l-1];
	}
	
	int size() {
		return Size;
	}
	
	bool empty() {return (Size == 0);}
	
	void clear() {
		node* N = first;
		while (N) {
			node* M = N -> next;
			delete N->prev;
			delete N;
			N = M;
		}
		
		N = new node(nullptr, nullptr);
		
		first = N;
		last = N;
		Size = 0;
		f = Max/2 - 1;
		l = Max/2;
	}
	
	void print() {
		node* N = first;
		while (N) {
			N -> print();
			N = N->next;
		}
	}
};


int main() {
	Dequeue D;
	string comand;
	int x;
	while(cin >> comand) {
		if (comand == "push_front") {
			cin >> x;
			D.push_front(x);
			cout << "ok\n";
		}
		if (comand == "push_back") {
			cin >> x;
			D.push_back(x);
			cout << "ok\n";
		}
		
		if (comand == "pop_front") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.pop_front() << "\n";
		}
		if (comand == "pop_back") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.pop_back() << "\n";
		}

		if (comand == "front") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.front() << "\n";
		}
		if (comand == "back") {
			if (D.empty())
				cout << "error\n";
			else
				cout << D.back() << "\n";
		}
		
		if (comand == "size") {
			cout << D.size() << "\n";
		}
		if (comand == "clear") {
			D.clear();
			cout << "ok\n";
		}
		if (comand == "exit") {
			cout << "bye\n";
			return 0;
		}
		if (comand == "print") {
			D.print();
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

#include <iostream>

#include <string>

using namespace std;

const int Max = 1000; // максимально допустимое число элементов в малом деке

struct node {

node* prev;

node* next;

int* dequeue;

node(node* Pr, node* Ne) {

prev = Pr;

next = Ne;

dequeue = new int[Max]();

}

void print() {

for(int k = 0; k < Max; k++)

cout << dequeue[k] << " ";

cout << endl;

}

};

struct Dequeue {

node* first;

node* last;

int f; // индекс первого свободного элемента в первой деке

int l; // индекс последнего свободного элемента в последней деке

int Size;

Dequeue() {

node* N = new node(nullptr, nullptr);

first = N;

last = N;

f = Max/2 - 1;

l = Max/2;

Size = 0;

}

// Управление двусвязным списком

void add_first () { // добавляет новый узел в начало списка

node* N = new node(nullptr, first);

first -> prev = N;

first = N;

f = Max - 1;

}

void add_last () { // добавляет новый узел в конец списка

node* N = new node(last, nullptr);

last -> next = N;

last = N;

l = 0;

}

void delete_first () { // удаляет первый узел списка

node* N = first -> next;

delete first;

first = N;

first -> prev = nullptr;

f = 0;

}

void delete_last () { // удаляет последний узел списка

node* N = last -> prev;

delete last;

last = N;

last -> next = nullptr;

l = Max - 1;

}

// Управление деком

void push_front (int n) {

(first -> dequeue)[f] = n;

f--;

Size++;

if (f == -1) // если первый дек переполнен

add_first(); // добавляем в начало списка новый дек

}

void push_back (int n) {

(last -> dequeue)[l] = n;

l++;

Size++;

if (l == Max) // если последний дек переполнен

add_last(); // добавляем в конец списка новый дек

}

int pop_front () {

Size--;

if (f == Max - 1)

delete_first();

else

f++;

return (first -> dequeue)[f];

}

int pop_back () {

Size--;

if (l == 0)

delete_last();

else

l--;

return (last -> dequeue)[l];

}

int front () {

if (f == Max - 1)

return ((first -> next) -> dequeue)[0];

else

return (first -> dequeue)[f+1];

}

int back () {

if (l == 0)

return ((last -> prev) -> dequeue)[Max - 1];

else

return (last -> dequeue)[l-1];

}

int size() {

return Size;

}

bool empty() {return (Size == 0);}

void clear() {

node* N = first;

while (N) {

node* M = N -> next;

delete N->prev;

delete N;

N = M;

}

N = new node(nullptr, nullptr);

first = N;

last = N;

Size = 0;

f = Max/2 - 1;

l = Max/2;

}

void print() {

node* N = first;

while (N) {

N -> print();

N = N->next;

}

};

int main() {

Dequeue D;

string comand;

int x;

while(cin >> comand) {

if (comand == "push_front") {

cin >> x;

D.push_front(x);

cout << "ok\n";

}

if (comand == "push_back") {

cin >> x;

D.push_back(x);

cout << "ok\n";

}

if (comand == "pop_front") {

if (D.empty())

cout << "error\n";

else

cout << D.pop_front() << "\n";

}

if (comand == "pop_back") {

if (D.empty())

cout << "error\n";

else

cout << D.pop_back() << "\n";

}

if (comand == "front") {

if (D.empty())

cout << "error\n";

else

cout << D.front() << "\n";

}

if (comand == "back") {

if (D.empty())

cout << "error\n";

else

cout << D.back() << "\n";

}

if (comand == "size") {

cout << D.size() << "\n";

}

if (comand == "clear") {

D.clear();

cout << "ok\n";

}

if (comand == "exit") {

cout << "bye\n";

return 0;

}

if (comand == "print") {

D.print();

}

return 0;

}

Related Images:

M2. Brainfuck

27/11/2014 by Вустянюк Ігор Дмитрович

Задача

Написать интерпретатор языка Brainfuck для памяти на n ячеек. Ячейки хранят значения типа char.

Тесты

Название программы

Ввод (программа на Brainfuck)

Вывод

Hello World!

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

1	++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

Hello World!

1	Hello World!

Числа Фибоначчи

>++++++++++>+>+[
    [+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[
        [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-
            [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>
    ]<<<
]

>++++++++++>+>+[

[+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[

[-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-

[>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>

]<<<

]

Факториалы

>++++++++++>>>+>+[>>>+[-[<<<<<[+<<<<<]>>[[-]>[<<+>+>-]<[>+<-]<[>+<-[>+<-[>
+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>>>>+>+<<<<<<-[>+<-]]]]]]]]]]]>[<+>-
]+>>>>>]<<<<<[<<<<<]>>>>>>>[>>>>>]++[-<<<<<]>>>>>>-]+>>>>>]<[>++<-]<<<<[<[
>+<-]<<<<]>>[->[-]++++++[<++++++++>-]>>>>]<<<<<[<[>+>+<<-]>.<<<<<]>.>>>>]

>++++++++++>>>+>+[>>>+[-[<<<<<[+<<<<<]>>[[-]>[<<+>+>-]<[>+<-]<[>+<-[>+<-[>

+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>>>>+>+<<<<<<-[>+<-]]]]]]]]]]]>[<+>-

]+>>>>>]<<<<<[<<<<<]>>>>>>>[>>>>>]++[-<<<<<]>>>>>>-]+>>>>>]<[>++<-]<<<<[<[

>+<-]<<<<]>>[->[-]++++++[<++++++++>-]>>>>]<<<<<[<[>+>+<<-]>.<<<<<]>.>>>>]

Код на С++

#include <iostream>
using namespace std;

int main() {
	int n; // Количество ячеек
        cin >> n;
	string tape(n,0);
	int pointer = 0;
	string program;
	cin >> program;
	for (unsigned int i = 0; i < program.length(); i++) {
		if (program[i] == '>')
			pointer++;
		
		if (program[i] == '<')
			pointer--;
		
		if (program[i] == '+')
			tape[pointer]++;
		
		if (program[i] == '-')
			tape[pointer]--;
		
		if (program[i] == '.')
			cout << tape[pointer];
		
		if (program[i] == ',')
			cin >> tape[pointer];
		
		if (program[i] == '[') {
			if (tape[pointer] == 0) {
				int counter = 1;
				while (counter > 0) {
					i++;
					if (program[i] == '[')
						counter++;
					if (program[i] == ']')
						counter--;
				}
			}
        }
        else if (program[i] == ']') {
			if (tape[pointer] != 0) {
				int counter = 1;
				while (counter > 0) {
					i--;
					if (program[i] == '[')
						counter--;
					if (program[i] == ']')
						counter++;
				}
			}
        }
    }

	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n; // Количество ячеек

cin >> n;

string tape(n,0);

int pointer = 0;

string program;

cin >> program;

for (unsigned int i = 0; i < program.length(); i++) {

if (program[i] == '>')

pointer++;

if (program[i] == '<')

pointer--;

if (program[i] == '+')

tape[pointer]++;

if (program[i] == '-')

tape[pointer]--;

if (program[i] == '.')

cout << tape[pointer];

if (program[i] == ',')

cin >> tape[pointer];

if (program[i] == '[') {

if (tape[pointer] == 0) {

int counter = 1;

while (counter > 0) {

i++;

if (program[i] == '[')

counter++;

if (program[i] == ']')

counter--;

}

else if (program[i] == ']') {

if (tape[pointer] != 0) {

int counter = 1;

while (counter > 0) {

i--;

if (program[i] == '[')

counter--;

if (program[i] == ']')

counter++;

}

return 0;

}

Код на Ideone. Код программы нужно вводить сплошным блоком текста — без переносов строки. Зато можно осуществлять «ввод данных для программы на Brainfuck» — то, для чего нужен оператор «,». Для этого нужно символы, которые «хотим ввести в программу на Brainfuck», нужно ввести в окно ввода Ideone на новой строке после кода программы.

Ещё один вариант кода. В нём можно вводить код программы на разных строках. Различие минимальное:

	string program = "", tmp;
	while (cin >> tmp)
		program += tmp;

string program = "", tmp;

while (cin >> tmp)

program += tmp;

Пройдя по второй ссылке можно посмотреть на один из вариантов вычисления чисел Фибоначчи на Brainfuck. Вычисляются числа, не превосходящие 100. Программа работает 🙂

Код на С

#include <stdio.h>
#include <stdlib.h>

char* read_string(size_t *size){
    char *str;
    int c;
    size_t length = 0;
    str = realloc(NULL, sizeof(char)*(*size));
    if(!str)return str;
    while((c=getchar()) != EOF  &&  c != '\n'){
        str[length++] = c;
        if(length == *size) {
        	str = realloc(str, sizeof(char)*(*size += 10));
            if(!str)
            	return str;
        }
    }
    str[length++] = '\0';
    size = length;
    return str;
}

int main() {
	int n;
        scanf("%d", &n);
        getchar();
	char tape[10000];
	for (int k = 0; k < n; k++)
		tape[k] = 0;
	int pointer = 0;
	size_t length = 100;
	char *program = read_string(&length);
	printf("%s\n", program);
	for (unsigned int i = 0; i < length; i++) {
		if (program[i] == '>')
			pointer++;
		
		if (program[i] == '<')
			pointer--;
		
		if (program[i] == '+')
			tape[pointer]++;
		
		if (program[i] == '-')
			tape[pointer]--;
		
		if (program[i] == '.')
			printf("%c", tape[pointer]);
		
		if (program[i] == ',')
			scanf("%c", &tape[pointer]);

		if (program[i] == '[') {
			if (tape[pointer] == 0) {
				int counter = 1;
				while (counter > 0) {
					i++;
					if (program[i] == '[')
						counter++;
					if (program[i] == ']')
						counter--;
				}
			}
        }
        else if (program[i] == ']') {
			if (tape[pointer] != 0) {
				int counter = 1;
				while (counter > 0) {
					i--;
					if (program[i] == '[')
						counter--;
					if (program[i] == ']')
						counter++;
				}
			}
        }
    }

	return 0;
}

#include <stdio.h>

#include <stdlib.h>

char* read_string(size_t *size){

char *str;

int c;

size_t length = 0;

str = realloc(NULL, sizeof(char)*(*size));

if(!str)return str;

while((c=getchar()) != EOF && c != '\n'){

str[length++] = c;

if(length == *size) {

str = realloc(str, sizeof(char)*(*size += 10));

if(!str)

return str;

}

str[length++] = '\0';

size = length;

return str;

}

int main() {

int n;

scanf("%d", &n);

getchar();

char tape[10000];

for (int k = 0; k < n; k++)

tape[k] = 0;

int pointer = 0;

size_t length = 100;

char *program = read_string(&length);

printf("%s\n", program);

for (unsigned int i = 0; i < length; i++) {

if (program[i] == '>')

pointer++;

if (program[i] == '<')

pointer--;

if (program[i] == '+')

tape[pointer]++;

if (program[i] == '-')

tape[pointer]--;

if (program[i] == '.')

printf("%c", tape[pointer]);

if (program[i] == ',')

scanf("%c", &tape[pointer]);

if (program[i] == '[') {

if (tape[pointer] == 0) {

int counter = 1;

while (counter > 0) {

i++;

if (program[i] == '[')

counter++;

if (program[i] == ']')

counter--;

}

else if (program[i] == ']') {

if (tape[pointer] != 0) {

int counter = 1;

while (counter > 0) {

i--;

if (program[i] == '[')

counter--;

if (program[i] == ']')

counter++;

}

return 0;

}

Ideone (C)

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = Integer.parseInt(in.next());
		char[] tape = new char[n];
		for (int i = 0; i < n; i++)
			tape[i] = 0;
		int pointer = 0;
		String program = in.next();
		for (int i = 0; i < program.length(); i++) {
			if (program.charAt(i) == '>')
				pointer++;
			if (program.charAt(i) == '<')
				pointer--;
			if (program.charAt(i) == '+')
				tape[pointer]++;
			if (program.charAt(i) == '-')
				tape[pointer]--;
			if (program.charAt(i) == '.')
				System.out.print(tape[pointer]);
			if (program.charAt(i) == ',')
				tape[pointer] = (char) System.in.read();
			
			if (program.charAt(i) == '[') {
				if (tape[pointer] == 0) {
					int counter = 1;
					while (counter > 0) {
						i++;
						if (program.charAt(i) == '[')
							counter++;
						if (program.charAt(i) == ']')
							counter--;
					}
				}
	        }
	        else if (program.charAt(i) == ']') {
				if (tape[pointer] != 0) {
					int counter = 1;
					while (counter > 0) {
						i--;
						if (program.charAt(i) == '[')
							counter--;
						if (program.charAt(i) == ']')
							counter++;
					}
				}
	        }
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = Integer.parseInt(in.next());

char[] tape = new char[n];

for (int i = 0; i < n; i++)

tape[i] = 0;

int pointer = 0;

String program = in.next();

for (int i = 0; i < program.length(); i++) {

if (program.charAt(i) == '>')

pointer++;

if (program.charAt(i) == '<')

pointer--;

if (program.charAt(i) == '+')

tape[pointer]++;

if (program.charAt(i) == '-')

tape[pointer]--;

if (program.charAt(i) == '.')

System.out.print(tape[pointer]);

if (program.charAt(i) == ',')

tape[pointer] = (char) System.in.read();

if (program.charAt(i) == '[') {

if (tape[pointer] == 0) {

int counter = 1;

while (counter > 0) {

i++;

if (program.charAt(i) == '[')

counter++;

if (program.charAt(i) == ']')

counter--;

}

else if (program.charAt(i) == ']') {

if (tape[pointer] != 0) {

int counter = 1;

while (counter > 0) {

i--;

if (program.charAt(i) == '[')

counter--;

if (program.charAt(i) == ']')

counter++;

}

Ideone (Java)

Related Images:

А402б

26/11/2014 by Вустянюк Ігор Дмитрович

Задача

Даны натуральное число [latex] n \geq 2 [/latex], действительная квадратная матрица порядка [latex] n [/latex]. Построить последовательность [latex] b_{1}, \ldots, b_{n} [/latex] из нулей и единиц, в которой [latex] b_{i} = 1 [/latex] тогда и только тогда, когда элементы [latex] i [/latex] строки образуют возрастающую или убывающую последовательность.

Тесты

Ввод	Вывод
[latex] \begin{pmatrix} 1 & 2.5 & 3 & -5 & 2 \\ -7 & -4.5 & -2.8 & 0 & 1 \\ 8 & 3 & 0 & -2.9 & -4.62 \\ 8 & 3 & 3 & -2.9 & -4.62 \\ 1 & 2 & 3 & 3 & 4 \end{pmatrix} [/latex]	[latex] \begin{matrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \end{matrix}[/latex]

Код на С++

#include <iostream>
using namespace std;

int main() {
	int m, n;
	cin >> m >> n;
	double M[m][n];
	bool monotone[m];
	
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> M[i][j];
			
	for (int i = 0; i < m; i++) {
		bool check = true, diff;
		if (M[i][0] != M[i][1]) {
			diff = (M[i][1] > M[i][0]);
			for (int j = 2; j < n; j++)
				if ((M[i][j] == M[i][j-1]) || ((M[i][j] > M[i][j-1]) != diff)) {
					check = false;
					break;
				}
		}
		else
			check = false;
		monotone[i] = check;
	}
	
	for (int i = 0; i < m; i++)
		cout << monotone[i] << endl;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int m, n;

cin >> m >> n;

double M[m][n];

bool monotone[m];

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

cin >> M[i][j];

for (int i = 0; i < m; i++) {

bool check = true, diff;

if (M[i][0] != M[i][1]) {

diff = (M[i][1] > M[i][0]);

for (int j = 2; j < n; j++)

if ((M[i][j] == M[i][j-1]) || ((M[i][j] > M[i][j-1]) != diff)) {

check = false;

break;

}

else

check = false;

monotone[i] = check;

}

for (int i = 0; i < m; i++)

cout << monotone[i] << endl;

return 0;

}

Ideone (C++)

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int m = in.nextInt(), n = in.nextInt();
		double[][] M = new double[m][n];
		boolean[] monotone = new boolean[m];
		
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				M[i][j] = in.nextDouble();
		
		for (int i = 0; i < m; i++) {
			boolean check = true, diff;
			if (M[i][0] != M[i][1]) {
				diff = (M[i][1] > M[i][0]);
				for (int j = 2; j < n; j++)
					if ((M[i][j] == M[i][j-1]) || ((M[i][j] > M[i][j-1]) != diff)) {
						check = false;
						break;
					}
			}
			else
				check = false;
			monotone[i] = check;
		}
		
		for (int i = 0; i < m; i++)
			System.out.println(monotone[i]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int m = in.nextInt(), n = in.nextInt();

double[][] M = new double[m][n];

boolean[] monotone = new boolean[m];

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

M[i][j] = in.nextDouble();

for (int i = 0; i < m; i++) {

boolean check = true, diff;

if (M[i][0] != M[i][1]) {

diff = (M[i][1] > M[i][0]);

for (int j = 2; j < n; j++)

if ((M[i][j] == M[i][j-1]) || ((M[i][j] > M[i][j-1]) != diff)) {

check = false;

break;

}

else

check = false;

monotone[i] = check;

}

for (int i = 0; i < m; i++)

System.out.println(monotone[i]);

}

Ideone (Java)

Решение

1) Считываем матрицу

2) Просматриваем по очереди строки матрицы. Фиксируем знак разности первых двух элементов строки и пробегаем строку, сравнивая знак соседних элементов со знаком первых двух. Если последовательность убывает/возрастает, знаки всех пар должны совпадать со знаком первой и никакие два подряд идущих элемента не должны совпадать.

Related Images:

Ю4.33

03/11/2014 by Вустянюк Ігор Дмитрович

Задача

Для заданной матрицы [latex] A(m,n) [/latex] найти её норму: [latex] \left \| A \right \| = \max_{i=1,m} \sum_{k=1}^{n} \left | a_{ik} \right |[/latex].

Тесты

Мне кажется, что достаточно одного теста с матрицей, среди элементов которой будут нули, отрицательные и дробные числа:

Ввод	Построчные суммы	Вывод
[latex] \begin{pmatrix} 1 & -3 & 2 & 4 & 0 \\ -3 & -7.5 & 2.3 & -3.1 & 2.8 \\ 3.4 & -4.5 & 0 & 0 & 2 \\ 3.2 & 4.7 & 2.8 & -3.1 & -4.3 \end{pmatrix} [/latex]	[latex] \begin{matrix} 10 \\ 18.7 \\ 14.4 \\ 18.1 \end{matrix}[/latex]	18.7

Решение

Нам понадобятся два цикла: во внешнем будем искать максимум, пробегая по всем строкам матрицы; во внутреннем будем для фиксированной строки вычислять сумму абсолютных величин её элементов. Если эта сумма превосходит текущую максимальную, обновляем последнюю. Поскольку все наши суммы будут неотрицательными числами, изначально присвоим переменной max значение [latex] 0 [/latex].

Хотя тема называется «Массивы», фактически массив нам здесь не нужен. От нас не требуют производить какие-либо действия над элементами матрицы, поэтому для экономии памяти и времени мы будем «обрабатывать её» , не сохраняя в отдельный массив.

Если бы в задаче требовалось по каким-либо причинам сохранить матрицу, алгоритм бы не поменялся. Только пришлось бы добавить следующий (или эквивалентный ему) фрагмент кода:

	double A[m][n];
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> A[i][j];

double A[m][n];

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

cin >> A[i][j];

Код на С++

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int m, n; // размеры матрицы
	double x; 	// эта переменная будет хранить текущий элемент матрицы
	double max; // здесь в конце будет храниться норма матрицы
	cin >> m >> n;
	max = 0;
	for (int i = 0; i < m; i++) {
		double s = 0.0;
		for (int j = 0; j < n; j++) {
			cin >> x;
			s += abs(x);
		}
		if (s > max)
			max = s;
	}
	cout << max;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int m, n; // размеры матрицы

double x; // эта переменная будет хранить текущий элемент матрицы

double max; // здесь в конце будет храниться норма матрицы

cin >> m >> n;

max = 0;

for (int i = 0; i < m; i++) {

double s = 0.0;

for (int j = 0; j < n; j++) {

cin >> x;

s += abs(x);

}

if (s > max)

max = s;

}

cout << max;

return 0;

}

Ideone (C++)

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double x, max = 0.0;
		int m = in.nextInt(), n = in.nextInt();
		for (int i = 0; i < m; i++) {
			double s = 0.0;
			for (int j = 0; j < n; j++) {
				x = in.nextDouble();
				s += Math.abs(x);
			}
			if (s > max)
				max = s;
		}
		System.out.println(max);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double x, max = 0.0;

int m = in.nextInt(), n = in.nextInt();

for (int i = 0; i < m; i++) {

double s = 0.0;

for (int j = 0; j < n; j++) {

x = in.nextDouble();

s += Math.abs(x);

}

if (s > max)

max = s;

}

System.out.println(max);

}

Ideone (Java)

Related Images:

А165в

03/11/2014 by Вустянюк Ігор Дмитрович

Задача

Даны действительные числа [latex] a_1 , a_2 \ldots[/latex]. Известно, что [latex] a_1 > 0[/latex] и что среди [latex] a_1, a_2, \ldots [/latex] есть хотя бы одно отрицательное число. Пусть [latex] a_1 , \ldots, a_n[/latex] -– члены данной последовательности, предшествующие первому отрицательному члену ([latex] n [/latex] заранее неизвестно). Получить:

в) среднее арифметическое [latex] a_1 , \ldots, a_n[/latex]

Тесты

Ввод	Вывод
3 -2 -7 2 5	3
3.4 0.5 0 -7 -8 2	1.3
1 0 0 -2	0.333
1.5 2.4 3 3.8 -7.5 11 0	2.675

Код на С++

#include <iostream>
using namespace std;

int main() {
	double sum = 0.0, number = 0.0, x;
	while ((cin >> x) && (x >= 0)) {
		sum += x;
		number++;
	}
	cout << sum/number;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double sum = 0.0, number = 0.0, x;

while ((cin >> x) && (x >= 0)) {

sum += x;

number++;

}

cout << sum/number;

return 0;

}

Ideone (C++)

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double sum = 0.0, number = 0.0, x = 1;
		while (in.hasNext() && x >= 0) {
			x = in.nextDouble();
			sum += x;
			number++;
		}
		System.out.println(sum / number);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double sum = 0.0, number = 0.0, x = 1;

while (in.hasNext() && x >= 0) {

x = in.nextDouble();

sum += x;

number++;

}

System.out.println(sum / number);

}

Ideone (Java)

Решение

Считываем в цикле числа из стандартного ввода, пока это возможно и пока не встретится отрицательное число. В том же цикле вычисляем сумму введённых чисел и их количество. Возвращаем сумму, делённую на количество, — среднее арифметическое.

Related Images:

Horse-racing Duals

16/10/2014 by Вустянюк Ігор Дмитрович

Horses2

Задача

Рассмотрим последнюю задачу уровня Easy с сайта codingame.com. Некоторое количество лошадей участвует в скачках и у каждой есть некая характеристика, выраженная целым числом. Формат скачек — парные заезды — и организаторы хотят, чтобы в заезде участвовали две лошади, различие между которыми (т.е. разность их характеристик) минимальна.

Входные данные

Первая строка: число n — количество лошадей.

Следующие n строк — в каждой указано одно целое число — характеристика соответствующей лошади.

Выходные данные

Наименьшая положительная разность характеристик.

Решение

Пусть задана конечная последовательность целых чисел a. В исходной формулировке задачи, без каких-либо оптимизаций, от нас требуют найти [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right|[/latex]. Если решать задачу в лоб, нам понадобятся два цикла: один пробегает все значения по i, а другой — все значения по [latex] j > i [/latex]. На каждом шаге внешнего цикла будет проделано [latex] n — i [/latex] шагов внутреннего. Итого получаем приблизительную оценку сложности такого алгоритма: [latex] n\left( n — i \right)[/latex], что асимптотически эквивалентно [latex] n^2 [/latex].

Оказывается, можно решить задачу «проще». Как утверждают авторитетные источники, сложность встроенного в стандартную библиотеку алгоритма сортировки составляет [latex] O(n \cdot \log \left( n \right) [/latex], что при больших значениях n лучше, чем [latex] n^2 [/latex]. Пусть b — конечная последовательность, в которой элементы последовательности a расположены по возрастанию. Поскольку множество значений у этих последовательностей одинаково, имеем: [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right| [/latex]. Однако нам уже не нужен двойной цикл. Благодаря монотонному возрастанию последовательности b, при любом [latex] i [/latex] имеем [latex] b_{i+1} — b_{i} > 0 [/latex] и при любых [latex] i,j [/latex] если [latex]i < j[/latex], то [latex] b_{j} — b_{i} \geq b_{i+1} — b_{i}[/latex].

Значит, [latex] D = min_{1 \leq i \leq n} \left( b_{i+1} — b_{i} \right) [/latex], а эту проверку можно провести за n действий. Таким образом, новая сложность составит примерно [latex] n \cdot log(n) + n [/latex], что асимптотически эквивалентно [latex] n \cdot log(n) [/latex] и, значит, для больших значений лучше «безоптимизационного» подхода.

Код на С++

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
	int n;	// Количество лошадей
	cin >> n;
	int horses[n];	
	for (int i = 0; i < n; i++) {	// Помещаем характеристики лошадей
		cin >> horses[i];			// в массив
	}	
	std::sort(horses, horses + n);	// Сортируем массив horses по возрастанию
	int min_dif = horses[1] - horses[0];
	for (int i = 1; i < n - 1; i++) {	// Поиск минимальной разницы характеристик
	    int cur_dif = horses[i+1] - horses[i];
	    if (cur_dif < min_dif)
	        min_dif = cur_dif;
	}
	cout << min_dif;
	return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

int main()

{

int n; // Количество лошадей

cin >> n;

int horses[n];

for (int i = 0; i < n; i++) { // Помещаем характеристики лошадей

cin >> horses[i]; // в массив

}

std::sort(horses, horses + n); // Сортируем массив horses по возрастанию

int min_dif = horses[1] - horses[0];

for (int i = 1; i < n - 1; i++) { // Поиск минимальной разницы характеристик

int cur_dif = horses[i+1] - horses[i];

if (cur_dif < min_dif)

min_dif = cur_dif;

}

cout << min_dif;

return 0;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] horses = new int[n];
		for (int i = 0; i < n; i++)
			horses[i] = in.nextInt();
		Arrays.sort(horses);
		int min_dif = horses[1] - horses[0];
		for (int i = 1; i < n-1; i++) {
			int cur_dif = horses[i+1] - horses[i];
			if (cur_dif < min_dif)
				min_dif = cur_dif;
		}
		System.out.println(min_dif);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[] horses = new int[n];

for (int i = 0; i < n; i++)

horses[i] = in.nextInt();

Arrays.sort(horses);

int min_dif = horses[1] - horses[0];

for (int i = 1; i < n-1; i++) {

int cur_dif = horses[i+1] - horses[i];

if (cur_dif < min_dif)

min_dif = cur_dif;

}

System.out.println(min_dif);

}

Подтверждение

Related Images:

Heat Detector

16/10/2014 by Вустянюк Ігор Дмитрович

Задача

Речь пойдёт о первой задаче уровня Medium на сайте codingame.com. По сюжету Бэтмен должен отыскать бомбу в многоэтажном доме. Ему известно количество этажей и количество окон на каждом этаже. Ему также известно направление, в котором находится бомба. Бэтмену нужно как можно быстрее её найти. Процесс поиска выглядит следующим образом: Бэтмен заглядывает в какое-то окно и затем на каждом игровом шаге он перепрыгивает в какое-то другое окно — так до тех пор, пока не отыщет бомбу.

Инциализация

В первой строке заданы числа W и H — соответственно количество окон на каждом этаже (оно для всех этажей одно и то же) и количество этажей в здании.

Во второй строке задано количество переходов, которые Бэтмен может сделать до взрыва. Это число нам не понадобится.

В третьей строке заданы два целых числа — x и y — координаты окна, с которого Бэтмен начинает свой поиск. Первая координата задаёт номер окна на этаже (начиная с нуля), вторая — номер этажа (также начиная с нуля). Нулевой этаж — верхний, нулевое окно на каждом этаже — левое.

Входные данные для одного игрового хода

Одна строка DIR, задающая направление, в котором следует искать бобму:

Выходные данные для одного игрового хода

Одна строка, в которой заданы два целых числа, разделённых одним пробелом, — координаты окна, которое должен проверить Бэтмен.

Решение

Игровой цикл продолжается до тех пор, пока либо бобма взорвётся, либо Бэтмен её обезвредит. Т.е. либо нам не хватит шагов, либо мы угадаем обе координаты. На каждом шаге игрового цикла будем перемещать Бэтмена с учётом направления, в котором находится бомба, и при этом «сжимать» область игрового поля, в которой он может прыгать. Однажды этот промежуток ужмётся в ондну точку — ту самую, абсцисса которой соответствует координате бомбы.

Обозначим координаты бобмы через BX и BY и введём четыре вспомогательных параметра: l, r, u, b — «динамические границы», левая, правая, верхняя и нижняя соответственно. Идея состоит в том, чтобы на каждом шаге выполнялись неравенства [latex] l \leq BX \leq r [/latex] и [latex] d \leq By \leq u [/latex].

Зададим начальные значения [latex] l = 0 [/latex], [latex] r = W — 1 [/latex], [latex] u = 0 [/latex] и [latex] d = H — 1 [/latex]. Тогда после инициализации игры указанные выше неравенства справедливы тривиальным образом (это просто заданные по условию ограничения на возможные значения Bx и By). Переходим к первому ходу, он же первый шаг игрового цикла. Мы считали строку DIR, указавшую нам направление, в котором следует искать бомбу.

Для оси абсцисс имеет место один из трёх случаев:

[latex] BX < x [/latex] (если DIR — одна из строк «L», «DL», «UL»). В этом случае справедливо неравенство [latex] l \leq BX \leq x — 1 [/latex]. Положим [latex] r = x — 1 [/latex]. Тогда будет справедливо неравенство [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток [latex] l \ldots r [/latex] в этом случае будет на единицу короче предыдущего.
[latex] BX = x [/latex] (если DIR — одна из строк «U» и «B»). В этом случае всё хорошо.
[latex] BX > x [/latex] (если DIR — одна из строк «R», «DR», «UR»). В этом случае справедливо неравенство [latex] x + 1 \leq BX \leq r [/latex]. Положим [latex] l = x + 1 [/latex]. Тогда будет справедливо неравенство [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток [latex] l \ldots r [/latex] в этом случае будет на единицу короче предыдущего.

Если [latex] BX = x [/latex], то всё хорошо — мы уже знаем абсциссу бомбы. А что делать в остальных двух случаях? Как эффективнее искать бомбу? Можно просматривать все значения из промежутка [latex] l \ldots r [/latex] поочерёдно слева направо, но что если бомба расположена у правого края? Можно просматривать все значения поочерёдно справа налево, но что если координата бомбы равна l, а промежуток большой? Остаётся один естественный вариант — «прыгнуть» в середину промежутка, т.е. в точку с абсциссой [latex] \left \lfloor \frac{l + r}{2} \right \rfloor[/latex]. На следующем шаге цикла надо повторить приведённые выше рассуждения, изменения границ и «прыжок». Таким образом, либо мы случайно наткнётся на абсциссу бомбы, либо промежуток [latex] l .. r [/latex], уменьшаясь каждый раз на одно число, ужмётся в точку, т.е. мы тоже найдём абсциссу бомбы! Осталось применить те же рассуждения к ординате бомбы. Надеюсь, код ответит на оставшиеся вопросы.

Код

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int W, H;   // Количество окон по горизонтали и вертикали соответственно
    cin >> W >> H; cin.ignore();
    int l = 0, r = W - 1, u = 0, d = H - 1; // Начальные значения границ
    int N;
    cin >> N; cin.ignore();
    int x, y;
    cin >> x >> y; cin.ignore();

    // Игровой цикл
    while (1) {
        string DIR; // Направление, в котором находится бомба
        cin >> DIR;
        if ((DIR[0] == 'L')  ||  (DIR[1] == 'L'))
            r = x - 1;
        if ((DIR[0] == 'R')  ||  (DIR[1] == 'R'))
            l = x + 1;
        if (DIR[0] == 'U')
            d = y - 1;
        if (DIR[0] == 'D')
            u = y + 1;
        
        x = (l + r)/2;  // Абсцисса нового окна
        y = (u + d)/2;  // Ордината нового окна
        
        cout << x << " " << y << endl;
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int W, H; // Количество окон по горизонтали и вертикали соответственно

cin >> W >> H; cin.ignore();

int l = 0, r = W - 1, u = 0, d = H - 1; // Начальные значения границ

int N;

cin >> N; cin.ignore();

int x, y;

cin >> x >> y; cin.ignore();

// Игровой цикл

while (1) {

string DIR; // Направление, в котором находится бомба

cin >> DIR;

if ((DIR[0] == 'L') || (DIR[1] == 'L'))

r = x - 1;

if ((DIR[0] == 'R') || (DIR[1] == 'R'))

l = x + 1;

if (DIR[0] == 'U')

d = y - 1;

if (DIR[0] == 'D')

u = y + 1;

x = (l + r)/2; // Абсцисса нового окна

y = (u + d)/2; // Ордината нового окна

cout << x << " " << y << endl;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int w = in.nextInt(), h = in.nextInt();
        int l = 0, r = w-1, u = 0, d = h-1;
        int n = in.nextInt(), x = in.nextInt(), y = in.nextInt();
        
        while (true) {
            char dir = in.next().charAt(0);
            if ((dir == 'L') || (dir == 'L'))
                r = x-1;
            if ((dir == 'R') || (dir == 'R'))
                l = x+1;
            if (dir == 'U')
                d = y-1;
            if (dir == 'D')
                u = y+1;
            x = (l + r) / 2;
            y = (u + d) / 2;
            System.out.println(x + " " + y);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int w = in.nextInt(), h = in.nextInt();

int l = 0, r = w-1, u = 0, d = h-1;

int n = in.nextInt(), x = in.nextInt(), y = in.nextInt();

while (true) {

char dir = in.next().charAt(0);

if ((dir == 'L') || (dir == 'L'))

r = x-1;

if ((dir == 'R') || (dir == 'R'))

l = x+1;

if (dir == 'U')

d = y-1;

if (dir == 'D')

u = y+1;

x = (l + r) / 2;

y = (u + d) / 2;

System.out.println(x + " " + y);

}

Подтверждение

Heat Detector

Related Images:

Temperatures

14/10/2014 by Вустянюк Ігор Дмитрович

Задача взята с сайта codingame.com

Задача.

Задан набор целых чисел (значения температуры за различные моменты времени). Нужно вывести из них ближайшее к нулю.

Входные данные.

Выходные данные.

Вывести нуль, если [latex] N = 0[/latex]. В противном случае вывести число, ближайшее к нулю, причём если два числа разных знаков одинаково близки к нулю, нужно вывести положительное.

Решение.

Сначала отфильтруем случай, когда [latex] N = 0[/latex]. В этом случае, как от нас и требуют, напечатаем нуль.

Если же [latex] N > 0 [/latex], прибегнем к уже знакомому нам приёму. Введём новую переменную — min — и присвоим ей первое число. Затем в цикле for будем эту переменную менять, если наткнёмся число, более близкое к нулю, чем хранящееся в min. Вот основной вопрос: когда нам нужно менять min? «Число [latex] a [/latex] ближе к нулю, чем число [latex] b [/latex]» означает, что [latex] a [/latex] по модулю меньше, чем [latex] b [/latex]. Значит, если число, прочитанное на текущем шаге цикла, по модулю строго меньше, чем число, хранящееся в min, переменную min нужно обновить. Но есть ещё один случай, когда переменную min следует обновить — это тот случай, когда текущее число положительно и столь же близко к нулю, как и число, хранящееся в min. Это действие даёт нам гарантию того, что если два числа разных знаков одинаково близки к нулю, будет выведено положительное.

Код на С++

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main()
{
	int N;
	cin >> N;
	if (N == 0)
        cout << 0 << endl;
    else {
        int min, temp;
        cin >> min;
        for (int i = 1; i < N; i++) {
            cin >> temp;
            if ((abs(temp) < abs(min)) || (temp == abs(min)))
                min = temp;
	    }
	    cout << min;
    }
	return 0;
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main()

{

int N;

cin >> N;

if (N == 0)

cout << 0 << endl;

else {

int min, temp;

cin >> min;

for (int i = 1; i < N; i++) {

cin >> temp;

if ((abs(temp) < abs(min)) || (temp == abs(min)))

min = temp;

}

cout << min;

}

return 0;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		if (N == 0)
			System.out.println(0);
		else {
			int min = in.nextInt(), temp;
			for (int i = 1; i < N; i++) {
				temp = in.nextInt();
				if ((Math.abs(temp) < Math.abs(min)) || (temp == Math.abs(min)))
					min = temp;
			}
			System.out.println(min);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int N = in.nextInt();

if (N == 0)

System.out.println(0);

else {

int min = in.nextInt(), temp;

for (int i = 1; i < N; i++) {

temp = in.nextInt();

if ((Math.abs(temp) < Math.abs(min)) || (temp == Math.abs(min)))

min = temp;

}

System.out.println(min);

}

P.S.. Возможно, усложнив оператор ветвления можно сделать алгоритм более эффективным за счёт уменьшения числа сравнений или присваиваний.

Related Images:

Ragnarök — Power of Thor

14/10/2014 by Вустянюк Ігор Дмитрович

Задача

Есть Тор. А у Тора был источник силы. Больше нет. Тор движется по прямоугольному полю и ему известны его координаты и координаты источника. Наша задача: за наименьшее количество ходов привести Тора к источнику. Допустимые варианты движения приведены на картинке ниже:

Инициализация

Одна строка, в которой даны четыре целых числа: LX, LY, TX, TY — соответственно абсцисса и ордината источника, абсцисса и ордината начального положения Тора.

Инициализация

Входные данные для одного игрового хода

Уровень энергии Тора. Нам он не понадобится.

Выходные данные для одного игрового хода

Одна из следующих строк: «N», «NE», «E», «SE», «S», «SW», «W», «NW», указывающая в каком направлении Тору нужно переместиться.

Решение

Поскольку Тор движется по прямоугольному полю, на котором нет преград, кратчайший путь получится, если на каждом шаге сравнивать положение Тора с положением источника по каждой из осей и направлять Тора в соответствующую сторону (так, чтобы скомпенсировать различие в координатах). Подробно этот процесс ниже описан в комменатариях к коду. Здесь сделаем только две ремарки.

Во-первых, нужно учесть, что ордината растёт в южном, а не в северном направлении, как обычно:

Во-вторых, если бы поле не было прямоугольным (или на нём были бы преграды, не позволяющие двигаться в том или ином направлении), то наш метод пришлось бы серьёзно модифицировать.

Код на С++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int LX; // абсцисса источника энергии
    int LY; // ордината источника энергии
    int TX; // абсцисса Тора
    int TY; // ордината Тора
    cin >> LX >> LY >> TX >> TY;

    while (1) {
        int E;
        cin >> E;
        string hor;     // Куда нужно двигаться Тору по оси абсцисс
        string ver;     // Куда нужно двигаться Тору по оси ординат
        // Определяем, куда нужно двигаться Тору по оси Х
        if (TX == LX)           // Если абсцисса Тора совпадает с абсциссой источника,
            hor = "";		// её менять не нужно
        else {				
            if (TX < LX) {	// Если абсцисса Тора МЕНЬШЕ абсциссы источника,
                hor = "E";	// УВЕЛИЧИМ её, т.е. двинемся на ВОСТОК
                TX++;		// Фиксируем изменение положения Тора
            }
            else {		// Если абсцисса Тора БОЛЬШЕ абсциссы источника, 
                hor = "W";	// УМЕНЬШИМ её, т.е. двинемся на ЗАПАД
                TX--;		// Фиксируем изменение положения Тора
            }
        }
        // Определяем, куда нужно двигаться Тору по оси Y
        if (TY == LY)		// Если ордината Тора совпадает с ординатой источника,
            ver = "";           // её менять не нужно
        else {
            if (TY < LY) {	// Если ордината Тора меньше ординаты источника,
                ver = "S";	// УВЕЛИЧИМ её, т.е. двинемся на ЮГ
                TY++;		// Фиксируем изменение положения Тора 
            }
            else {		// Если ордината Тора больше ординаты источника,
                ver = "N";	// УМЕНЬШИМ её, т.е. двинемся на СЕВЕР
                TY--;		// Фиксируем изменение положения Тора
            }
        }     
        cout << ver + hor << endl; // Склеиваем наши строки-"сдвиги" и выводим окончательный сдвиг
    }
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

int LX; // абсцисса источника энергии

int LY; // ордината источника энергии

int TX; // абсцисса Тора

int TY; // ордината Тора

cin >> LX >> LY >> TX >> TY;

while (1) {

int E;

cin >> E;

string hor; // Куда нужно двигаться Тору по оси абсцисс

string ver; // Куда нужно двигаться Тору по оси ординат

// Определяем, куда нужно двигаться Тору по оси Х

if (TX == LX) // Если абсцисса Тора совпадает с абсциссой источника,

hor = ""; // её менять не нужно

else {

if (TX < LX) { // Если абсцисса Тора МЕНЬШЕ абсциссы источника,

hor = "E"; // УВЕЛИЧИМ её, т.е. двинемся на ВОСТОК

TX++; // Фиксируем изменение положения Тора

}

else { // Если абсцисса Тора БОЛЬШЕ абсциссы источника,

hor = "W"; // УМЕНЬШИМ её, т.е. двинемся на ЗАПАД

TX--; // Фиксируем изменение положения Тора

}

// Определяем, куда нужно двигаться Тору по оси Y

if (TY == LY) // Если ордината Тора совпадает с ординатой источника,

ver = ""; // её менять не нужно

else {

if (TY < LY) { // Если ордината Тора меньше ординаты источника,

ver = "S"; // УВЕЛИЧИМ её, т.е. двинемся на ЮГ

TY++; // Фиксируем изменение положения Тора

}

else { // Если ордината Тора больше ординаты источника,

ver = "N"; // УМЕНЬШИМ её, т.е. двинемся на СЕВЕР

TY--; // Фиксируем изменение положения Тора

}

cout << ver + hor << endl; // Склеиваем наши строки-"сдвиги" и выводим окончательный сдвиг

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int LX = in.nextInt(), LY = in.nextInt();
		int TX = in.nextInt(), TY = in.nextInt();
		while (true) {
			int E = in.nextInt();
			String hor, ver;
			if (TX == LX)
				hor = "";
			else {
				if (TX < LX) {
					hor = "E";
					TX++;
				}
				else {
					hor = "W";
					TX--;
				}
			}
			if (TY == LY)
				ver = "";
			else {
				if (TY < LY) {
					ver = "S";
					TY++;
				}
				else {
					ver = "N";
					TY--;
				}
			}
			System.out.println(ver + hor);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int LX = in.nextInt(), LY = in.nextInt();

int TX = in.nextInt(), TY = in.nextInt();

while (true) {

int E = in.nextInt();

String hor, ver;

if (TX == LX)

hor = "";

else {

if (TX < LX) {

hor = "E";

TX++;

}

else {

hor = "W";

TX--;

}

if (TY == LY)

ver = "";

else {

if (TY < LY) {

ver = "S";

TY++;

}

else {

ver = "N";

TY--;

}

System.out.println(ver + hor);

}

Related Images:

The Descent

14/10/2014 by Вустянюк Ігор Дмитрович

Задача

Мы летим на падающем космическом корабле над горами. Наша задача — запрограммировать пушки корабля так, чтобы уничтожить горы, тем самым не дав кораблю в них врезаться.

Гор имеется 8 штук. Корабль летает кругами над горами: сначала слева направо, потом справа налево, и так далее. Один полный «пролёт» состоит из восьми игровых ходов. За один пролёт мы можем выстрелить только один раз и только по горе, над которой находимся. При этом высота горы уменьшится на случайное число.

Чтобы благополучно приземлиться нам нужно уничтожить все горы. Создатели игры дали ценную подсказку: если стрелять на каждом пролёте по самой высокой горе, посадка будет безопасной.

Входные данные для одного игрового хода

В первой строке введены два числа (SX и SY) — соответственно горизонтальная и вертикальная координаты нашего корабля. Горизонтальная меняется слева направо от нуля до семи. Вертикальная, как показал опыт, нам не понадобится.

Следующие восемь строк содержат каждая по одному целому числу от нуля до девяти — высоту соответствующей горы. Высоты перечислены слева направо.

Выходные данные для одного игрового хода

Одна строка: «FIRE», чтобы выстрелить, и «HOLD», если на текущем ходе стрелять не нужно.

Решение

Считаем SX и SY. После этого в цикле for считаем высоты гор. Нам нужно стрелять на каждом пролёте по самой высокой горе. Для этого мы применим приём, уже опробованный нами на практических занятиях: введём новую переменную max_height, в которую поместим высоту первой горы (точнее, нулевой). А в цикле будем обновлять эту переменную, если наткнёмся на более высокую гору. Всё? Нет, не всё. Стрелять мы можем только по горе, которая находится под нами. Чтобы знать, когда стрелять, введём переменную max_position, которая будет хранить координату самой высокой горы. Вначале присвоим ей нулевое значение. А в цикле будем обновлять эту переменную, вместе с переменной max_height.

Когда цикл for завершится, останется только проверить находимся ли мы на текущем ходу над самой высокой горой: для этого будем каждый раз сравнивать текущую координату корабля (SX) с координатой самой высокой горы, которая после цикла for хранится в переменной max_position. В случае совпадения — стреляем, в противном случае — ждём.

Код на С++

#include <iostream>

using namespace std;

int main()
{
    while (true) {
        int SX, SY, current_height, max_height, max_position = 0;
        cin >> SX >> SY >> max_height;
        for (int i = 1; i < 8; i++) {
            cin >> current_height;
            if (max_height < current_height) {
                max_height = current_height;
                max_position = i;
            }
        }
        if (SX == max_position)
            cout << "FIRE" << endl;
        else
            cout << "HOLD" << endl;
    }
}

#include <iostream>

using namespace std;

int main()

{

while (true) {

int SX, SY, current_height, max_height, max_position = 0;

cin >> SX >> SY >> max_height;

for (int i = 1; i < 8; i++) {

cin >> current_height;

if (max_height < current_height) {

max_height = current_height;

max_position = i;

}

if (SX == max_position)

cout << "FIRE" << endl;

else

cout << "HOLD" << endl;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		while (true) {
			Scanner in = new Scanner(System.in);
			int SX, SY, max_height, current_height, max_position = 0;
			SX = in. nextInt();
			SY = in. nextInt();
			max_height = in. nextInt();
			for (int i = 1; i < 8; i++) {
				current_height = in. nextInt();
				if (max_height < current_height) {
					max_height = current_height;
					max_position = i;
				}
			}
			if (SX == max_position)
				System.out.println("FIRE");
			else
				System.out.println("HOLD");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

while (true) {

Scanner in = new Scanner(System.in);

int SX, SY, max_height, current_height, max_position = 0;

SX = in. nextInt();

SY = in. nextInt();

max_height = in. nextInt();

for (int i = 1; i < 8; i++) {

current_height = in. nextInt();

if (max_height < current_height) {

max_height = current_height;

max_position = i;

}

if (SX == max_position)

System.out.println("FIRE");

else

System.out.println("HOLD");

}

Related Images:

А34а

20/09/2014 by Вустянюк Ігор Дмитрович

Задача.

Даны действительные числа [latex] x, y, z [/latex]. Получить [latex]\max\left\{x,y,z \right\}[/latex].

Тесты.

Ввод	Вывод
0 0 0	0
-1 2 3	3
1 3.4 2.2	3.4
-3.5 0 2.1	2.1
-1.9 -7 0	0
-3.4 -2 -1.8	-1.8

Код.

#include <iostream>
using namespace std;
 
int main() {
	double x,y,z,max;
	scanf("%lf %lf %lf", &x, &y, &z);
	if (x <= y) {	// Вычисляем  max{x,y}
		max = y;
	}
	else {
		max = x;
	}
	
	if (max <= z) {	// Если  max{x,y} <= z, то  max{x,y,z} = max{max{x,y},z} = z;
		max = z;	// В противном случае  max{x,y,z} = max{max{x,y},z} = max{x,y}
	}
	printf("max{%4.2lf,%4.2lf,%4.2lf} = %4.2lf \n",x,y,z,max);
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double x,y,z,max;

scanf("%lf %lf %lf", &x, &y, &z);

if (x <= y) { // Вычисляем max{x,y}

max = y;

}

else {

max = x;

}

if (max <= z) { // Если max{x,y} <= z, то max{x,y,z} = max{max{x,y},z} = z;

max = z; // В противном случае max{x,y,z} = max{max{x,y},z} = max{x,y}

}

printf("max{%4.2lf,%4.2lf,%4.2lf} = %4.2lf \n",x,y,z,max);

return 0;

}

Ideone (C++)

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double x, y, z, max;
		x = in.nextDouble();
		y = in.nextDouble();
		z = in.nextDouble();
		if (x <= y)
			max = y;
		else
			max = x;
		if (max <= z)
			max = z;
		System.out.format("max{%.2f, %.2f, %.2f} = %.2f\n", x, y, z, max);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double x, y, z, max;

x = in.nextDouble();

y = in.nextDouble();

z = in.nextDouble();

if (x <= y)

max = y;

else

max = x;

if (max <= z)

max = z;

System.out.format("max{%.2f, %.2f, %.2f} = %.2f\n", x, y, z, max);

}

Ideone (Java)

Решение.

1) Как известно, для любых чисел [latex] x,y \in \mathbb{R} [/latex] [latex] \max\left\{x,y \right\} = x,[/latex] если [latex] x \geq y[/latex], и [latex] \max\left\{x,y \right\} = y,[/latex] в противном случае.

2) Нетрудно доказать, что [latex] \forall x,y,z \in \mathbb{R} [/latex] [latex] \max\left\{x,y,z \right\}=\max\left\{\max\left\{x,y \right\},z \right\}[/latex]

3) С учётом замечания 1), вычислим [latex] \max\left\{x,y\right\}[/latex] и поместим полученное значение в переменную [latex] \max [/latex]

4) С учётом замечаний 1) и 2), если [latex] max \geq z [/latex], то [latex] \max\left\{x,y,z \right\} = z[/latex]. В противном случае, [latex] \max\left\{x,y,z \right\} = \max[/latex].

Related Images:

Ю2.14

18/09/2014 by Вустянюк Ігор Дмитрович

Задача.

Треугольник и точка. Лежит ли точка [latex] M \left( x_{m}, y_{m} \right) [/latex] внутри треугольника, заданного координатами своих вершин [latex] \left( x_{A}, y_{A} \right) [/latex], [latex] \left( x_{A}, y_{A} \right) [/latex], [latex] \left( x_{A}, y_{A} \right) [/latex].

Комментарий.

Предполагаем, что треугольник невырожденный, т.е. точки [latex] A [/latex], [latex] B [/latex] и [latex] C [/latex] не лежат на одной прямой.

Слово «внутри» будем понимать следующим образом: точка «лежит внутри треугольника», если она принадлежит внутренности (в топологическом смысле) этого треугольника. Как следствие, если точка лежит на одной из сторон треугольника, внутри треугольника она НЕ лежит.

Тесты.

Ввод	Вывод
0 0 1 0 1 1 0.5 0.25	Да
0 0 1 0 1 1 -1 -1.5	Нет
-1.5 -1.5 -1.5 4 1 0.5 -1 2	Да
-1.5 -1.5 -1.5 4 1 0.5 -1 0	Нет
0.3 0.2 1.3 0.2 0.3 0.8 0.7 0.4	Да
0.3 0.2 1.3 0.2 0.3 0.8 0.3 0.6	Нет
2 1 0.5 -2 -2 -0.5 0.5 -1	Да
2 1 0.5 -2 -2 -0.5 2 1	Нет

Рассмотрим четыре основных типа треугольников:

ровно одна сторона параллельна оси абсцисс;
ровно одна сторона параллельна оси ординат;
две стороны параллельны координатным осям;
ни одна из сторон не параллельна ни к одной из осей.

Для каждого типа рассмотрим два случая: точка принадлежит его внутренности и не принадлежит. При этом рассмотрим случай (восьмая строка таблицы), когда точка лежит на стороне и постараемся рассмотреть случаи, когда координатами являются нецелые и отрицательные числа.

По моим подсчётам есть 96 вариантов расположения треугольника и точки, с учётом параллельности/непараллельности сторон осям, расположения вершин по координатным четвертям и принадлежности/непринадлежности точки внутренности треугольника. Поэтому хочется верить, что выбранные тестовые примеры достаточно показательные.

Код.

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	int i;
	double a1, a2, b1, b2, c1, c2, x, y, f, g;
	scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &a1, &a2, &b1, &b2, &c1, &c2, &x, &y);
	f = (y - a2)*(b1 - a1) - (x - a1)*(b2 - a2);
	g = (c2 - a2)*(b1 - a1) - (c1 - a1)*(b2 - a2);
	if (f*g > 0) {  // Проверяем, лежат ли точки (x,y) и C по одну сторону от прямой  AB 
		f = (y - a2)*(c1 - a1) - (x - a1)*(c2 - a2);
		g = (b2 - a2)*(c1 - a1) - (b1 - a1)*(c2 - a2);
		if (f*g > 0) {  // Проверяем, лежат ли точки (x,y) и B по одну сторону от прямой  AC 
			f = (y - b2)*(c1 - b1) - (x - b1)*(c2 - b2);
			g = (a2 - b2)*(c1 - b1) - (a1 - b1)*(c2 - b2);
			if (f*g > 0) {  // Проверяем, лежат ли точки (x,y) и A по одну сторону от прямой  BC 
				printf("Да \n");
			}
			else {
				printf("Нет \n");
			}
		}
		else {
			printf("Нет \n");
		}
	}
	else {
		printf("Нет \n");
	}
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int i;

double a1, a2, b1, b2, c1, c2, x, y, f, g;

scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &a1, &a2, &b1, &b2, &c1, &c2, &x, &y);

f = (y - a2)*(b1 - a1) - (x - a1)*(b2 - a2);

g = (c2 - a2)*(b1 - a1) - (c1 - a1)*(b2 - a2);

if (f*g > 0) { // Проверяем, лежат ли точки (x,y) и C по одну сторону от прямой AB

f = (y - a2)*(c1 - a1) - (x - a1)*(c2 - a2);

g = (b2 - a2)*(c1 - a1) - (b1 - a1)*(c2 - a2);

if (f*g > 0) { // Проверяем, лежат ли точки (x,y) и B по одну сторону от прямой AC

f = (y - b2)*(c1 - b1) - (x - b1)*(c2 - b2);

g = (a2 - b2)*(c1 - b1) - (a1 - b1)*(c2 - b2);

if (f*g > 0) { // Проверяем, лежат ли точки (x,y) и A по одну сторону от прямой BC

printf("Да \n");

}

else {

printf("Нет \n");

}

else {

printf("Нет \n");

}

else {

printf("Нет \n");

}

return 0;

}

Ideone (C++)

Код (Java)

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double a1 = in. nextDouble(), a2 = in. nextDouble();
		double b1 = in. nextDouble(), b2 = in. nextDouble();
		double c1 = in. nextDouble(),c2 = in. nextDouble();
		double x = in. nextDouble(), y = in. nextDouble(), f, g;
		f = (y - a2)*(b1 - a1) - (x - a1)*(b2 - a2);
		g = (c2 - a2)*(b1 - a1) - (c1 - a1)*(b2 - a2);
		if (f*g > 0) {
			f = (y - a2)*(c1 - a1) - (x - a1)*(c2 - a2);
			g = (b2 - a2)*(c1 - a1) - (b1 - a1)*(c2 - a2);
			if (f*g > 0) {
				f = (y - b2)*(c1 - b1) - (x - b1)*(c2 - b2);
				g = (a2 - b2)*(c1 - b1) - (a1 - b1)*(c2 - b2);
				if (f*g > 0)
					System.out.println("Yes\n");
				else
					System.out.println("No\n");
			}
			else
				System.out.println("No\n");
		}
		else
			System.out.println("No\n");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double a1 = in. nextDouble(), a2 = in. nextDouble();

double b1 = in. nextDouble(), b2 = in. nextDouble();

double c1 = in. nextDouble(),c2 = in. nextDouble();

double x = in. nextDouble(), y = in. nextDouble(), f, g;

f = (y - a2)*(b1 - a1) - (x - a1)*(b2 - a2);

g = (c2 - a2)*(b1 - a1) - (c1 - a1)*(b2 - a2);

if (f*g > 0) {

f = (y - a2)*(c1 - a1) - (x - a1)*(c2 - a2);

g = (b2 - a2)*(c1 - a1) - (b1 - a1)*(c2 - a2);

if (f*g > 0) {

f = (y - b2)*(c1 - b1) - (x - b1)*(c2 - b2);

g = (a2 - b2)*(c1 - b1) - (a1 - b1)*(c2 - b2);

if (f*g > 0)

System.out.println("Yes\n");

else

System.out.println("No\n");

}

else

System.out.println("No\n");

}

else

System.out.println("No\n");

}

Ideone (Java)

Решение.

Составим уравнения сторон треугольника. Как известно, в эвклидовой геометрии в прямоугольных декартовых координатах уравнение прямой, проходящей через две (различные!) точки [latex] \left( r1, r2 \right) [/latex] и [latex] \left( s1, s2 \right) [/latex] есть [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right) = 0[/latex] . Эта прямая разбивает плоскость на три части: собственно прямую и две открытые полуплоскости, задаваемые неравенствами [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right) < 0[/latex] и [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right) > 0[/latex].
Как известно, точка лежит внутри невырожденного треугольника, если и только если она лежит с каждой вершиной этого треугольника в одной полуплоскости относительно стороны, противоположной этой вершине.
Из 1. заключаем, что точки с декартовыми координатами [latex] \left( x,y \right)[/latex] и [latex] \left( u,v \right)[/latex] лежат по одну сторону от прямой, проходящей через точки [latex] \left( r1,r2 \right)[/latex] и [latex] \left( s1,s2 \right)[/latex], если и только если числа [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right)[/latex] и [latex] \left(v — r2 \right) \left( s1 — r1 \right) — \left( u- r1 \right) \left( s2 — r2 \right)[/latex] отличны от нуля и одного знака, т.е. если произведение этих чисел — строго положительное число.
Проверяем условие из пункта 3. для вершины [latex] C [/latex] и стороны [latex] AB [/latex]. Если условие выполнено, переходим к пункту 5. В противном случае точка внутри треугольника не лежит.
Проверяем условие из пункта 3. для вершины [latex] B [/latex] и стороны [latex] AC [/latex]. Если условие выполнено, переходим к пункту 5. В противном случае точка внутри треугольника не лежит.
Проверяем условие из пункта 3. для вершины [latex] A [/latex] и стороны [latex] BC [/latex]. Если условие выполнено, точка лежит внутри треугольника. В противном случае точка внутри треугольника не лежит.

Related Images:

Ю1.3

18/09/2014 by Вустянюк Ігор Дмитрович

Задача.

Длина отрезка задана в дюймах (1 дюйм = 2,54 см). Перевести значение длины в метрическую системы, т.е. выразить её в метрах, сантиметрах и миллиметрах. Например, 21 дюйм = 0 м 53 см 3,4 м.

Тесты.

Ввод	Вывод
0	0 м 0 см 0 мм
0.3	0 м 0 см 7.62 мм
21	0 м 53 см 3.4 мм
40.5	1 м 2 см 8.7 мм
100	2 м 54 см 0 мм
5000	127 м 0 см 0 мм

Код.

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	double L1, L, m, cm, mm;
	for (int i = 1; i <= 6; i++) {
		scanf("%f", &L1);	 	// Вводим значение длины в дюймах
		L = L1*25.4;                    // Переводим дюймы в миллиметры
	
		m = floor(L/1000);
		cm = floor((L - 1000*m)/10);
		mm = L - 1000*m - 10*cm;

		printf("%4.2f дюймов  =  %.0f м  %.0f см  %.2f мм  \n", L1, m, cm, mm);
	}
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double L1, L, m, cm, mm;

for (int i = 1; i <= 6; i++) {

scanf("%f", &L1); // Вводим значение длины в дюймах

L = L1*25.4; // Переводим дюймы в миллиметры

m = floor(L/1000);

cm = floor((L - 1000*m)/10);

mm = L - 1000*m - 10*cm;

printf("%4.2f дюймов = %.0f м %.0f см %.2f мм \n", L1, m, cm, mm);

}

return 0;

}

Ideone (C++)

Код (Java)

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double L1, L, m, cm, mm;
		L1 = in.nextDouble();
		L = L1 * 25.4;
		
		m = Math.floor(L / 1000);
		cm = Math.floor((L - 1000*m) / 10);
		mm = L - 1000*m - 10*cm;
		System.out.format("%.0f дюймов = %.0f м  %.0f см  %.2f мм", L1, m, cm, mm);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double L1, L, m, cm, mm;

L1 = in.nextDouble();

L = L1 * 25.4;

m = Math.floor(L / 1000);

cm = Math.floor((L - 1000*m) / 10);

mm = L - 1000*m - 10*cm;

System.out.format("%.0f дюймов = %.0f м %.0f см %.2f мм", L1, m, cm, mm);

}

Ideone (Java)

Решение.

Обозначим через [latex] x [/latex] длину в дюймах, которую вводит пользователь; через [latex] y [/latex] длину в миллиметрах. Согласно формуле перевода, [latex] y = 25.4 \cdot x[/latex].

Один метр есть тысяча миллиметров. Чтобы получить целое число метров, содержащихся в [latex] y[/latex] , разделим [latex] y[/latex] на тысячу и извлечём целую часть: [latex] m = \left[\frac{x}{1000} \right][/latex].

Один сантиметр есть десять миллиметров. Избавимся от метров, разделим полученное число на десять и извлечём целую часть — получим целое число сантиметров, содержащихся в [latex] y [/latex]: [latex] y = \left[\frac{y-1000\cdot m}{10} \right] [/latex]

Оставшееся — число миллиметров: [latex] mm = y — 1000 \cdot m — 10 \cdot cm [/latex] .