Ровно 20 простых делителей

28/11/2016 by Мазурок Игорь Евгеньевич

Задача. За 2 секунды проверить предположение о том, что у некоторого числа [latex]n \le 10^{18}[/latex] имеется ровно 20 простых делителей.
Попытаться решить задачу и проверить своё решение можно здесь.

Тесты

Вход	Выход	Примечание
10000000000	Yes	[latex]2^{10}\cdot 5^{10}[/latex]
1048576	Yes	[latex]2^{20}[/latex]
999999999987679232	Yes	[latex]2^19 \cdot 1907348632789[/latex]
2	No	[latex]2^{1}[/latex]
1000000000000000003	No	Простое число. Немного выходит за пределы ограничения задачи, но допустимо для типов unsigned long long
1000000000012845056	Yes	[latex]2^{19}\cdot 1907348632837[/latex] Немного выходит за пределы ограничения задачи, но допустимо для типов unsigned long long
99999989699999923	No	[latex]99999989 \cdot 1000000007[/latex]
8388608	No	[latex]2^{23}[/latex] — слишком много делителей

Решение

Идея решения состоит в попытках деления исходного числа [latex]n[/latex] на последовательно увеличивающиеся целые числа [latex]d,[/latex] начиная с двойки. Если удается произвести деление без остатка, то очередной делитель найден. Исходное число можно разделить на этот делитель и в дальнейшем искать делители полученного частного, т.е. [latex]n \leftarrow \frac{n}{d}.[/latex] Теперь нам остается найти на один делитель меньше. Такая процедура должна будет успешно завершиться ровно 19 раз. Частное от последнего 19-го деления должно оказаться простым числом — тогда простых делителей окажется ровно 20.
При подготовке тестов выяснилось, что трудности могут вызывать следующие ситуации:

No — отрицательный вердикт: слишком мало делителей. В худшем случае одно большое простое число.
Yes — положительный вердикт: 19 небольших делителей и большой 20-й. В худшем случае рассматривается число [latex]2^{19} \cdot 1907348632789 = 999999999987679232[/latex]

В обоих случаях трудности вызывает поиск делителей довольно большого простого числа. Необходимо аккуратно ограничить диапазон поиска возможных делителей так, чтобы не выполнять излишней работы, но и не пропустить делителей.
Зададимся вопросом, как долго нам придётся перебирать возможные делители (начиная с числа 2) пока не встретим первый (наименьший) делитель?
Рассмотрим первый случай (слишком мало делителей). Пусть нам известно, что число имеет [latex]m[/latex] делителей. Первый, встретившийся нам делитель (т.е. наименьший) должен быть таким, чтобы [latex]d^{m} \le n, [/latex] т.е. [latex]d \le n^{\frac{1}{m}} = \sqrt[m]{n}.[/latex] Это очень хорошее ограничение, т.к. в первом случае нам придется перебирать возможные делители до [latex]\left( 10^{18} \right)^{\frac{1}{20}} = 10^{\frac{18}{20}} \le 7.[/latex] Это совсем немного вариантов. Т.е. достаточно проверить деление на 3, 5 и 7 для самого большого возможного [latex]n[/latex]. При правильном выборе границ поиска «страшный» случай огромного простого числа [latex]n[/latex] оказывается очень лёгким.

Границы поиска делителей в худшем случае

Чуть сложнее оказывается ситуация когда есть один маленький делитель (например, 2). Тогда при поиске следующего делителя нам придутся работать с числами [latex]n \le \frac{10^{18}}{2} = 5 \cdot 10^{17}.[/latex] Поскольку теперь останется найти не 20 а только 19 делителей? то ограничение на возможное значение минимального делителя станет таким: [latex]\left( 5 \cdot 10^{17} \right)^{\frac{1}{19}} = \sqrt[19]{5 \cdot 10^{17}} \le 8.[/latex] Что даёт тот же набор возможных простых делителей. Давайте посмотрим, как у нас будут изменяться границы поиска в худшем случае. Т.е. для максимально большого [latex]n[/latex] и делителях равных 2. Рассуждая аналогичным образом можно рассчитать границы поиска остальных делителей в худшем случае:

[latex]m[/latex]	Граница поиска в худшем случае
20	7
19	8
18	9
17	10
16	11
15	12
14	14
13	16
12	19
11	24
10	31
9	42
8	62
7	102
6	198
5	497
4	1976
3	19686
2	1 953 125
1	1 381 067

Как видим значения вполне доступны для полного перебора за 1-2 секунды на обычном персональном компьютере.
Случай с последним делителем будет рассмотрен отдельно далее.

Теперь рассмотрим второй случай. У нас имеется 19 маленьких делителей (в худшем случае это двойки) и одно большое простое число. Насколько большие делители нужно проверить прежде чем заключить, что оставшееся число простое?
Оставшееся после 19 делений на два число не может превышать [latex]\frac{10^{18}}{2^{19}}=0.5 \cdot 5^{18}.[/latex] Если оставшееся число не является простым, то у него должен быть делитель не превышающий квадратного корня из этого числа. Т.е. поиск делителей в этом последнем случае не может продлиться дольше чем до [latex]\sqrt{0.5 \cdot 5^{18}} = 1381067.[/latex]

Код

Составим простую программу по описанному алгоритму.
Код программы можно запустить здесь.
В программе есть два нюанса, на которые следует обратить внимание. Оба они относятся к 8-й строке кода и касаются вычисления верхней границы в цикле подбора делителей.

При извлечении корня может быть получено неточное значение. Это связано как с ошибкой округления. Например, при работе с числами типа double [latex]\sqrt[3]{1000000}[/latex] оказывается не 100, как мы ожидаем, а примерно [latex]99.9999999999999716.[/latex] Из-за этого мы можем не найти делитель в точности равный правой границе интервала поиска. Для компенсации возможной ошибки к правой границе была добавлена некоторая небольшая величина. Конкретное значение выбирается на основании пессимистической оценки возможной погрешности.
Верхняя граница поиска делителей не превышает [latex]\sqrt[m]{n}[/latex] если число делителей [latex]m \ge 2.[/latex]. Когда мы хотим убедиться, что последнее [latex]\left(m=1\right)[/latex] оставшееся число является простым, мы ищем его делители до [latex]\sqrt[2]{n}.[/latex]. Т.е. предполагаем, что число не простое и ищем его делители.

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    unsigned long long n, d = 2;
    cin >> n;
    int m = 20;                     // ищем m делителей числа n
    while (m > 0 && d <= pow(n, 1./max(2, m)) + 1e-10) {
        if (n % d == 0) {           // если делитель найден,
            n /= d;                 // то делим
            m--;                    // и ищем на один делитель меньше
        } else d++;                 // иначе проверяем следующее число
    }
    cout << (m == 1? "Yes" : "No"); // найдено m делителей?
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

unsigned long long n, d = 2;

cin >> n;

int m = 20; // ищем m делителей числа n

while (m > 0 && d <= pow(n, 1./max(2, m)) + 1e-10) {

if (n % d == 0) { // если делитель найден,

n /= d; // то делим

m--; // и ищем на один делитель меньше

} else d++; // иначе проверяем следующее число

}

cout << (m == 1? "Yes" : "No"); // найдено m делителей?

return 0;

}

Задание

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

Related Images:

Вывод чисел в обратном порядке

07/10/2016 by Вадим Гордийчук

Задача

Вводятся некоторые числа вещественного типа. Вывести их в обратном порядке.

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

Некие числа вещественного типа.

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

Введённые числа в обратном порядке.

Тесты

Входные данные	Выходные данные	Входные данные	Выходные данные	Входные данные	Выходные данные
2 4 1	1 4 2	4 9 -6	-6 9 4	0.568 0.925 -0.056	-0.056 0.925 0.568

Код программы

#include <iostream>
using namespace std;

void reverse()
{
    double x;
    if (cin >> x)
    {
        reverse();
        cout << x << "\n";
    }
}

int main()
{
    reverse();
    return 0;
}

#include <iostream>

using namespace std;

void reverse()

{

double x;

if (cin >> x)

{

reverse();

cout << x << "\n";

}

int main()

{

reverse();

return 0;

}

Идея программы

Основная суть программы заключается в использовании рекурсивной функции. Главная функция main обращается к функции reverse, которая будет считывать поток чисел. Если поток чисел продолжается, то функция будет заново обращаться сама к себе и считывать следующие числа. Когда поток закончится, функция прекратит считывать данные, после чего начнётся вывод.

Принцип работы рекурсивной функции reverse:

Решение задачи №1001 на acm.timus.ru, основанное на этом принципе

#include <iostream>
#include <cstdio>
#include <cmath>

void reverse()
{
    double x;
    if (scanf("%lf", &x) > 0)
    {
        reverse();
        printf("%.4f\n", sqrt(x));
    }
}

int main()
{
    reverse();
    return 0;
}

#include <iostream>

#include <cstdio>

#include <cmath>

void reverse()

{

double x;

if (scanf("%lf", &x) > 0)

{

reverse();

printf("%.4f\n", sqrt(x));

}

int main()

{

reverse();

return 0;

}

Ссылки

Related Images:

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

18/09/2016 by Мазурок Игорь Евгеньевич

Рассмотрим общеизвестный ряд чисел A000045:
[latex]0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, \ldots[/latex] Этот ряд представляет собой неотрицательную ветвь последовательности Фибоначчи. Будем считать, что последовательность задаётся следующим рекуррентным соотношением
[latex]f_n=\left\{\begin{matrix}
0, & n=0\\
1, & n=1\\
f_{n-1}+f_{n-2}, & n>1
\end{matrix}\right.[/latex]

Давайте напишем функцию, которая вычисляет [latex]n[/latex]-е по порядку число Фибоначчи, используя приведенное соотношение:

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

unsigned long long f (unsigned short n) {
    return n < 2? n : f(n-1) + f(n-2);
}

int main() {
    cout << f(6);
    return 0;
}

#include <cmath>

#include <iostream>

using namespace std;

unsigned long long f (unsigned short n) {

return n < 2? n : f(n-1) + f(n-2);

}

int main() {

cout << f(6);

return 0;

}

Для теста мы вывели на печать вычисленное этим способом 6-е по порядку число Фибоначчи. Программа напечатала 8. И не ошиблась. Давайте посмотрим как происходили вызовы функций:

Порядок вызовов при вычислении шестого по счёту числа Фибоначчи по прямому рекурсивному алгоритму

Легко видеть, что для вычисления каждого числа Фибоначчи (кроме двух первых) выполняется строго два вызова функции. Т.е. если нам понадобится вычислить, следующее (седьмое) число Фибоначчи, то количество вызовов практически удвоится. И действительно, каждое следующее число вычисляется вдвое дольше, чем предыдущее. При наличии терпения ещё можно как-то дождаться конца вычисления 50-го числа, но дальше вычисляется уж очень долго.
В чём причина? Почему человек, вычисляя на листе бумаги, легко обгоняет компьютер?
Конечно, неэффективный алгоритм.
На рисунке цветом выделены те блоки, вычисление которых действительно необходимо. Число таких блоков растёт с увеличением номера числа линейно, говорят [latex]O\left( n\right)[/latex]. А вот остальные блоки — сплошные повторы и их число растёт как [latex]O\left( 2^n\right)[/latex].
Попробуйте изменить программу так, чтобы она работала быстро (без повторных вычислений.
В качестве упражнения, я попрошу не использовать циклов.
После того, как у Вас всё получится (или окончательно опустятся руки), загляните под спойлер и постарайтесь разобраться с моим вариантом решения задачи.

Рекурсивное решение без повторов

#include <iostream>
using namespace std;

unsigned long long tomorrow (
		unsigned short n, 
		unsigned long long yesterday, 
		unsigned long long today) 
{
	return n == 0? today : tomorrow(n - 1, today, yesterday + today);
}

unsigned long long h (unsigned short n) {
	return tomorrow (n, 0, 1);
}

int main() {
	cout<< f(93) << endl;
	return 0;
}

#include <iostream>

using namespace std;

unsigned long long tomorrow (

unsigned short n,

unsigned long long yesterday,

unsigned long long today)

{

return n == 0? today : tomorrow(n - 1, today, yesterday + today);

}

unsigned long long h (unsigned short n) {

return tomorrow (n, 0, 1);

}

int main() {

cout<< f(93) << endl;

return 0;

}

Related Images:

Совершенные числа

17/08/2016 by Макогон Владимир Сакович

Задача. Найдите все чётные совершенные числа не превышающие заданного числа[latex]M[/latex].

Напомним, что натуральное число [latex]n[/latex] называют совершенным, если оно равно сумме всех своих делителей, не считая его самого. Известно, что все совершенные числа — четные и что первое совершенное число из натурального ряда равно 6. Этим объясняется правило изменения параметра внешнего цикла. Так как все натуральные числа имеют своим делителем единицу, полагаем начальное значение суммы делителей числа S = 1. Во внутреннем цикле организуется перебор всех делителей текущего значения N. Из теории чисел известно, что такому испытанию имеет смысл подвергать числа от 2 до [latex]\frac{n}{2}[/latex], либо даже до [latex]\sqrt{n}[/latex]. Этот не очень совершенный алгоритм реализован в следующем коде:

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

int main() {    
    unsigned long long M;
    cin >> M;
    for (unsigned long long n = 4; n <= M; n += 2) {
        unsigned long long S = 1;
        for (unsigned long long j = 2; j <= sqrt(n) && S <= n; j++) {
            if (n % j == 0) S += n / j + j;
        }
        if (n == S) cout << n << " ";
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

unsigned long long M;

cin >> M;

for (unsigned long long n = 4; n <= M; n += 2) {

unsigned long long S = 1;

for (unsigned long long j = 2; j <= sqrt(n) && S <= n; j++) {

if (n % j == 0) S += n / j + j;

}

if (n == S) cout << n << " ";

}

return 0;

}

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

Теперь рассмотрим другой подход, позволяющий ускорить вычисления. Используем алгоритм нахождения совершенных чисел, более эффективный по сравнению с приведенным ранее. Этот алгоритм основан на известном из теории чисел утверждении Ферма о том, что если натуральное число [latex]p = 2^{k+1}-1[/latex] простое, то число [latex]n = 2^k \cdot (2^{k+1}-1)=p \cdot 2^k[/latex] — совершенное ([latex]k = 1,2,\ldots[/latex]).
Функция prime() определяет, является ли число [latex]p[/latex] простым. Обратите внимание, что функция проверяет в качестве возможных делителей исходного числа только нечетные числа, так как само испытуемое число — нечетное.

// Найти все чётные совершенные числа из unsigned long long
#include <iostream>
#include <cmath>
using namespace std;

// Подпрограмма определяет, является ли число n простым
bool is_prime(unsigned long long n) {  
    unsigned long long  i = 3;
    while (i < sqrt(n)) {
        if (n % i == 0) return false;
        i += 2;
    }
    return true;
}

int main() {
    unsigned long long p = 1, n = 1;
    while (p * n < (4 * n - 1) * 2 * n) { // пока числа увеличиваются
        p = 2 * n - 1; 
        if (is_prime(p)) cout << n * p << " ";
        n <<= 1;
    } 
    return 0;
}

// Найти все чётные совершенные числа из unsigned long long

#include <iostream>

#include <cmath>

using namespace std;

// Подпрограмма определяет, является ли число n простым

bool is_prime(unsigned long long n) {

unsigned long long i = 3;

while (i < sqrt(n)) {

if (n % i == 0) return false;

i += 2;

}

return true;

}

int main() {

unsigned long long p = 1, n = 1;

while (p * n < (4 * n - 1) * 2 * n) { // пока числа увеличиваются

p = 2 * n - 1;

if (is_prime(p)) cout << n * p << " ";

n <<= 1;

}

return 0;

}

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

Related Images:

Лабиринт

02/07/2016 by Маша Лукьянова

Условие:

Имя входного файла: стандартный поток ввода

Имя выходного файла: стандартный поток вывода

Ограничение по времени: 2 second

Ограничение по памяти: 64 мегабайт

Задан лабиринт [latex] N \times N [/latex], некоторые клетки которого могут быть заняты. Дан путь робота длины [latex] k [/latex] по этому лабиринту без указания его начального положения. Известно, что робот до начала движения стоит в одной из свободных клеток. Необходимо определить наименьшее количество передвижений по пути, после которого можно точно определить, где находится робот.

Задача взята из 1-го раунда KPI OPEN 2013 года.

Формат входного файла:

Первая строка входного файла содержит два целых числа через пробел $$ N (1 \leq N \leq 100) $$ и $$k (0 \leq k \leq 10^{5}) $$. В следующих [latex] N [/latex] строках задана карта лабиринта как совокупность 0 и 1 без пробелов: 1 – занятая клетка, 0 – свободная. В последней строке дана последовательность из $$ k (0 \leq k \leq 10^{5} ) $$ символов. Символы задают движение робота по лабиринту: символ [latex] U [/latex] — вверх, [latex] D [/latex] — вниз, [latex] R [/latex] —вправо, [latex] L [/latex] — влево. Других символов в строке передвижений нет, все символы в верхнем регистре латиницы.

Формат выходного файла:

В единственной строке выходного файла выведите единственное целое число не меньше нуля — наименьшее количество передвижений по пути, после которого можно точно определить местоположение робота. Если ответ не существует, либо входные данные некорректны, выведите -1.

Тесты:

№	Входные данные	Выходные данные
1	2 0 11 01	0
2	2 0 11 11	-1
3	2 1 11 01 R	-1
4	3 3 000 010 000 RDU	2
5	5 5 00010 10001 00100 10100 01101 RDUUU	4

Решение:

Если попробовать решить эту задачу «в лоб», то решение не будет удовлетворять пределу по времени, так как в худшем случае, нам надо перебрать $$ 10^{4} $$ возможных начальных позиций и совершить из них $$ 10^{5} $$ ходов, что в результате дает $$ 10^{9} $$ операций.

Решение «в лоб»:

Заведем список позиций в лабиринте, которым соответствуют элементы матрицы, в которые может попасть робот. В изначальном состоянии, без просмотра пути передвижения робота, это будут все позиции в лабиринте, где значение равно $$ 0 $$. После чего, проходя путь робота по шагам, будем для всех позиций в списке проверять:
- Если мы вышли за границу матрицы, или в клетке, в которую мы собираемся перейти стоит $$ 1 $$, тогда удаляем эту позицию, поскольку она для нас недостижима.
- Иначе ничего не делаем.
Если количество текущих вариантов пути стало равным $$ 1 $$, то мы запоминаем количество ходов при которой была достигнута данная ситуация.
Так будем делать до тех пор, пока робот закончил свой путь.
Если после всех проделанных нами операций остался один вариант полностью пройденного пути, тогда ответ найден. А именно это будет ход, после которого у нас кол-во удовлетворяющих позиций стало равным $$ 1 $$. В любом другом случае ответ нельзя определить однозначно.

Другая идея состоит в том, чтобы построить карту «переходов», в которой будет храниться номер хода, на котором робот впервые попал в эту клетку и ее координаты. Эта карта играет роль некоторого шаблона полного пути робота и «накладывая» его на каждый элемент матрицы в качестве начальной позиции, мы проверяем мог ли данный элемент матрицы служить «пунктом отправления» робота. Если такой элемент есть и он единственен, значит, можно однозначно определить начальное положение робота, но для того чтобы определить минимальное количество требуемых ходов-нужно последовательно удалять последние ходы из карты, «накладывая» изменившийся шаблон на каждый элемент, до тех пор, пока количество элементов удовлетворяющих шаблону не возрастет. Что значит, что мы получим номер решающего хода после которого судьба робота решится однозначно, значит ответом будет предыдущий ход. Стоит отметить, что если в карте останется всего лишь один элемент (соответствующий первому ходу), то расположение робота определялось однозначно первым ходом.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <set>
#include <list>
#include <map>
 
#define ll long long int
#define X first
#define Y second
#include <iostream>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    char maze[n][n];//лабиринт
    for(int i = 0; i < n; ++i){
        getchar();
        for(int j = 0; j < n; ++j){
            maze[i][j] = getchar();
        }
    }
    getchar();
    char path[k+1]; //путь
    for(int i = 0; i < k; ++i){
        path[i + 1] = getchar();
    }
    set<pair<int, int> > visited; 
        //ячейки, в которых мы побывали
    map<int, pair<int, int> > nodes; 
        // узлы, которые должен пройти робот (номер хода, координаты)
    pair<int, int> cur = {0, 0};
    visited.insert(cur);
    nodes[0] = cur; 
    //проходим весь путь
    for(int i = 1; i <= k; ++i){
        if(path[i] == 'L'){
            --cur.X;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'R'){
            ++cur.X;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'U'){
            --cur.Y;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'D'){
            ++cur.Y;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }
    }
    int count = 0;
    map<int, int> ans; bool ok = false;
    for(; nodes.size();){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                for(pair<int, pair<int, int> > a : nodes){
                    if(j + a.Y.X < 0 || j + a.Y.X >= n ||
                              // не вышли ли за пределы по строкам
                        i + a.Y.Y < 0 || i + a.Y.Y >= n || 
                              // не вышли ли за пределы по столбцам
                        maze[i + a.Y.Y][j + a.Y.X] == '1'){ 
                              //не попали ли на 1-цу
                        --count;
                        break;
                    }
                }
                ++count;
            }
        }
        auto t = --nodes.end();
        ans[count] = t->X;
        nodes.erase(t);
        count = 0;
        if(ans.size() == 2) break;
        if(!ok){
            ok = 1;
            if(ans.begin()->X != 1){
                cout << -1 << endl;
                return 0;
            }
        }
    }
    if(ans.size() == 1 && ans.begin()->X == 1){
        cout << ans.begin()->Y << endl;
    }else if(ans.size() == 2 && ans.begin()->X == 1){
        cout << ans.begin()->Y << endl;
    }else{
        cout << -1 << endl;
    }
}

100

101

102

103

104

105

106

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <stack>

#include <set>

#include <list>

#include <map>

#define ll long long int

#define X first

#define Y second

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

char maze[n][n];//лабиринт

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

getchar();

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

maze[i][j] = getchar();

}

getchar();

char path[k+1]; //путь

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

path[i + 1] = getchar();

}

set<pair<int, int> > visited;

//ячейки, в которых мы побывали

map<int, pair<int, int> > nodes;

// узлы, которые должен пройти робот (номер хода, координаты)

pair<int, int> cur = {0, 0};

visited.insert(cur);

nodes[0] = cur;

//проходим весь путь

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

if(path[i] == 'L'){

--cur.X;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'R'){

++cur.X;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'U'){

--cur.Y;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'D'){

++cur.Y;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

int count = 0;

map<int, int> ans; bool ok = false;

for(; nodes.size();){

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

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

for(pair<int, pair<int, int> > a : nodes){

if(j + a.Y.X < 0 || j + a.Y.X >= n ||

// не вышли ли за пределы по строкам

i + a.Y.Y < 0 || i + a.Y.Y >= n ||

// не вышли ли за пределы по столбцам

maze[i + a.Y.Y][j + a.Y.X] == '1'){

//не попали ли на 1-цу

--count;

break;

}

++count;

}

auto t = --nodes.end();

ans[count] = t->X;

nodes.erase(t);

count = 0;

if(ans.size() == 2) break;

if(!ok){

ok = 1;

if(ans.begin()->X != 1){

cout << -1 << endl;

return 0;

}

if(ans.size() == 1 && ans.begin()->X == 1){

cout << ans.begin()->Y << endl;

}else if(ans.size() == 2 && ans.begin()->X == 1){

cout << ans.begin()->Y << endl;

}else{

cout << -1 << endl;

}

Submission.

Related Images:

e-olymp 2171. Поиск набора образцов

19/05/2016 by Женя Максимова

Задача. Напишите программу, которая для каждой строки из заданного набора [latex]S[/latex] проверяет, верно ли, что она содержит как подстроку одну из строк из набора [latex]T[/latex].

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

Первая строка содержит натуральное число [latex]n (n\leq100)[/latex] — количество строк в наборе [latex]T[/latex]. Каждая из следующих [latex]n[/latex] строк содержит непустую строку длины не более [latex]80[/latex]-ти символов.

Оставшаяся часть файла содержит строки из набора [latex]S[/latex]. Каждая строка состоит из ASCII символов с кодами от [latex]32[/latex] до [latex]126[/latex] включительно. Строка может быть пустой; гарантируется, что длины строк не превышают [latex]250[/latex]-ти символов.

Гарантируется, что размер входного файла не превышает [latex]1[/latex] Мбайт.

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

Выведите все строки из набора [latex]S[/latex] (в том порядке, в котором они находятся во входном файле), содержащие как подстроку по крайней мере одну строку из набора [latex]T[/latex].

Задача взята с сайта e-olymp.

Тесты

Test	Input	Output
1	3 gr sud abc lksh sudislavl kostroma summer group b	sudislavl group b
2	4 a b + + xxx ababa dfs c + + qwerty xxxx	ababa c + + xxxx
3	1 a a b a c a d	a a a
4	2 bab aba aabba w w w

Код программы

#include <bits/stdc++.h>
using namespace std;

#define in_range(x,y,z) for (int x=y; x<z; x++)
typedef long long ll;

int find_subctr(string t, string s)
{
  const int p = 97;  // основание системы счисления для хеширования строк
  // вычисляем степени числа P, чтобы ускорить процесс хеширования
  vector<ll> p_pow (s.length());
  p_pow[0] = 1;
  for (size_t i=1; i<p_pow.size(); ++i)
    p_pow[i] = p_pow[i-1] * p;
  // вычисляем хеши всех префиксов строки S
  vector<ll> h (s.length());
  for (size_t i=0; i<s.length(); ++i)
    {
      h[i] = (s[i] - 't' + 1) * p_pow[i];
      if (i)  h[i] += h[i-1];
    }
  // посчитаем хеш строки Т
  ll h_t = 0;
  for (size_t i=0; i<t.length(); ++i)
    h_t += (t[i] - 't' + 1) * p_pow[i];
  // сравниваем хеши строки T и подстрок S длины |T|
  for (size_t i = 0; i + t.length() - 1 < s.length(); ++i)
    {
      ll cur_h = h[i+t.length()-1];
      if (i)  cur_h -= h[i-1];
      // если равенство выполняется хотя бы один раз, мы прекращаем поиск
      if (cur_h == h_t * p_pow[i])
        return int(i);
    }
  return -1;
}

int main()
{
  vector<string>T,S,C; // наборы строк T и S, а также набор образцов единичной длины C
  int n;
  cin >> n;
  string tmp;
  getline(cin,tmp);
  in_range(i,0,n)
    {
      getline(cin,tmp);
      if(tmp.length()==1) C.push_back(tmp);
      T.push_back(tmp);
    }
  while(getline(cin,tmp))
    {
      S.push_back(tmp);
    }
  in_range(i,0,S.size())
    {
      string s=S[i];
      if(s=="") continue; // отсекаем случай пустой строки
      if(s.length()==1) // в случае строки единичной длины ищем вхождения образцов из С простым перебором
        {
          in_range(j,0,C.size())
          {
            string c=C[j];
            if(s==c)
              {
                cout << s << "\n";
                break;
              }
          }
          continue;
        }
      in_range(j,0,n) // во всех остальных случаях ищем вхождения строк из Т, используя алгоритм Рабина-Карпа
      {
        string t=T[j];
        int pos = find_subctr(t,s);
        if(pos>=0)
          {
            cout << s << "\n";
            break;
          }
      }
    }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define in_range(x,y,z) for (int x=y; x<z; x++)

typedef long long ll;

int find_subctr(string t, string s)

{

const int p = 97; // основание системы счисления для хеширования строк

// вычисляем степени числа P, чтобы ускорить процесс хеширования

vector<ll> p_pow (s.length());

p_pow[0] = 1;

for (size_t i=1; i<p_pow.size(); ++i)

p_pow[i] = p_pow[i-1] * p;

// вычисляем хеши всех префиксов строки S

vector<ll> h (s.length());

for (size_t i=0; i<s.length(); ++i)

{

h[i] = (s[i] - 't' + 1) * p_pow[i];

if (i) h[i] += h[i-1];

}

// посчитаем хеш строки Т

ll h_t = 0;

for (size_t i=0; i<t.length(); ++i)

h_t += (t[i] - 't' + 1) * p_pow[i];

// сравниваем хеши строки T и подстрок S длины |T|

for (size_t i = 0; i + t.length() - 1 < s.length(); ++i)

{

ll cur_h = h[i+t.length()-1];

if (i) cur_h -= h[i-1];

// если равенство выполняется хотя бы один раз, мы прекращаем поиск

if (cur_h == h_t * p_pow[i])

return int(i);

}

return -1;

}

int main()

{

vector<string>T,S,C; // наборы строк T и S, а также набор образцов единичной длины C

int n;

cin >> n;

string tmp;

getline(cin,tmp);

in_range(i,0,n)

{

getline(cin,tmp);

if(tmp.length()==1) C.push_back(tmp);

T.push_back(tmp);

}

while(getline(cin,tmp))

{

S.push_back(tmp);

}

in_range(i,0,S.size())

{

string s=S[i];

if(s=="") continue; // отсекаем случай пустой строки

if(s.length()==1) // в случае строки единичной длины ищем вхождения образцов из С простым перебором

{

in_range(j,0,C.size())

{

string c=C[j];

if(s==c)

{

cout << s << "\n";

break;

}

continue;

}

in_range(j,0,n) // во всех остальных случаях ищем вхождения строк из Т, используя алгоритм Рабина-Карпа

{

string t=T[j];

int pos = find_subctr(t,s);

if(pos>=0)

{

cout << s << "\n";

break;

}

return 0;

}

Алгоритм

Мы последовательно перебираем все строки [latex]s[/latex] из набора [latex]S[/latex]. Для каждой из них найдем вхождение хотя бы одной строки [latex]t[/latex] из набора [latex]T[/latex]. Для этого мы воспользуемся алгоритмом Рабина-Карпа. Он заключается в следующем: мы сравниваем подстроки [latex]s[/latex] длины [latex]\left | t \right |[/latex] со строкой [latex]t[/latex], предварительно закодировав их с помощью хеша. Если после мы перебрали все подстроки, но так и не получили равенство, строка [latex]t[/latex] не является подстрокой [latex]s[/latex] и мы переходим к следующему образцу.

Однако данный алгоритм не целесообразно использовать для строк единичной длины. Про большом количестве таких строк неэффективность алгоритма становится очень заметной. Поэтому мы создаем отдельный набор образцов, состоящих ровно из одного символа. Если на вход поступает строка единичной длины, мы просто ищем ее в этом наборе за [latex]O(n)[/latex].

Код программы

Засчитанное решение на сайте e-olymp.com

Related Images:

e-olymp 1073. Статическая сложность

05/03/2016 by Сплошнов Кирилл

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится целое число [latex]k[/latex] — число программ во входном файле. Затем идут [latex]k[/latex] программ, удовлетворяющих приведенной грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах [latex]BEGIN[/latex], [latex]END[/latex], [latex]LOOP[/latex] и [latex]OP[/latex], нет их и в целых числах.

Вложенность операторов [latex]LOOP[/latex] не превышает [latex]10[/latex], размер входного файла не более [latex]2[/latex] Кбайт, коэффициенты многочлена в ответе не превышают [latex]50000[/latex].

(Примечание: то, что представляет из себя программа, можно прочитать по ссылке выше.)

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

Для каждой программы сначала идет строка с номером программы. В следующей строке записывается время работы программы в терминах [latex]n[/latex] — многочлен степени не более [latex]10[/latex]. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое большей степени должно предшествовать слагаемому меньшей степени, слагаемые с коэффициентом [latex]0[/latex] не записываются, множители [latex]1[/latex] не записываются. Общий вид второй строки [latex]Runtime = a*n^{10}+b*n^9+\ldots+i*n^2+j*n+k[/latex]. Если время выполнения нулевое, нужно вывести [latex]Runtime = 0[/latex]. За строкой с многочленом должна следовать пустая строка, кроме последнего тестового случая.

Решение

Создадим массив коэффициентов [latex]coefficients[/latex] на 11 элементов (нулевой элемент — свободный член, 10-й — десятая (максимальная) степень). В цикле для каждой программы будем:

Обнулять массив [latex]coefficients[/latex].
Заполнять его новыми данными с помощью функции void getCoefficients(int* coefficients);
Строить на основании полученных коэффициентов требуемую строку-многочлен, за это отвечает функция string toString(int* coefficients);
Выводить требуемую информацию.

Рассмотрим процесс заполнения массива. Создадим вектор для строк [latex]params[/latex], где будем хранить кол-ва повторений для всех открытых циклах, от внешнего к внутреннему, и переменную-счетчик [latex]keywords[/latex]. Функция будет завершать свою работу при значении [latex]keywords[/latex] равном [latex]0[/latex]. Изначально присвоим [latex]keywords = 1[/latex] (оператор [latex]BEGIN[/latex]). Далее, в цикле будем, в зависимости от прочитанного оператора:

[latex]END[/latex]: уменьшаем значение [latex]keywords[/latex] на [latex]1[/latex], удаляем последний элемент из [latex]params[/latex] (чтобы не было проблем с последним оператором [latex]END[/latex] (пустой вектор), положим в него перед циклом строку «[latex]1[/latex]»). Если [latex]keywords[/latex] равно нулю — завершаем работу.
[latex]LOOP[/latex]: увеличиваем значение [latex]keywords[/latex] на [latex]1[/latex], считываем следующую строку и добавляем ее в конец [latex]params[/latex].
[latex]OP[/latex]: Считываем следующую строку, преобразовываем ее к числу (кол-ву операций) стандартной функцией stoi(). Далее, проходя по строкам из [latex]params[/latex], если строка равна [latex]n[/latex], увеличиваем степень (номер ячейки массива, куда прибавим результат) на [latex]1[/latex], иначе — преобразовываем к числу и домножаем на кол-во операций. Прибавляем полученный результат к числу в соответствующей ячейке массива.

Функция toString() реализована достаточно просто (см. код). Пробегаем по элементам массива с конца, и если элемент [latex]n[/latex] не равен нулю, прибавляем к строке-многочлену соответствующий набор символов (отдельно учитывая случаи при [latex]n = 1[/latex], [latex]n=-1[/latex], первой и нулевой степени и т.д.). Если в итоге строка пустая, возвращаем «[latex]0[/latex]».

Тесты

№

Ввод

Вывод

2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END

BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END

Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

3
BEGIN
END

BEGIN
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
END END END OP 3
END END END OP 3
END END END OP 3
END

BEGIN OP 42
LOOP n LOOP 5 LOOP n
OP 7 END OP 2 END OP 1 END
OP 1 END

Program #1
Runtime = 0

Program #2
Runtime = n^9+4*n^6+4*n^3+3

Program #3
Runtime = 35*n^2+11*n+43

Код

#include <iostream>
#include <string>
#include <vector>
#define MAX_POWER 10
using namespace std;

void getCoefficients(int* coefficients)
{
	int keywords = 1;
	vector<string> params;
	string begin;
	cin >> begin;
	params.push_back(((string) "1")); //чтобы вектор не был пустой на последнем END (который соответствует BEGIN)
	while (true)
	{
		string keyword;
		cin >> keyword;
		if (keyword == (string)"END")
        {
            keywords--;
            params.pop_back();
            if (keywords == 0) 
            {
            	break;
            }
        }
        else if (keyword == (string)"LOOP")
        {
            keywords++;
            string param;
            cin >> param;
            params.push_back(param);
        }
        else if (keyword == (string)"OP")
        {
        	string num;
        	cin >> num;
            int coefficient = stoi(num);
            int multiplier = 1, pow = 0;
            for (string param : params)
            {
                if (param == (string)"n") 
                {
                	pow++;
                }
                else 
                {
                	multiplier *= stoi(param);
                }
            }
            coefficients[pow] += coefficient * multiplier;
        }
	}
}

string toString(int* coefficients)
{
	string result;
    for (int i = MAX_POWER; i > 0; i--)
    {
        if (coefficients[i] != 0)
            {
                if (coefficients[i] == 1) 
                {
                	result += "n";
                }
                else if (coefficients[i] == -1) 
                {
                	result += "-n";
                }
                else
                {
                	result += to_string(coefficients[i]); //стандартная функция, преобразовывает число в строку
                	result += "*n";
                }
                if (i != 1) //если степень не первая, добавляем "^[степень]"
                {
                	result += "^";
                	result += to_string(i);
                }
            }
            if (coefficients[i-1] > 0 && result.length() != 0) //проверка, чтобы + не стоял в начале строки и между членами не было "+-"
            {
            	result += "+";
            }
        }
        if (result.length() == 0 || coefficients[0] != 0) //прибавляем последний коэффициент, если он не равен нулю или строка пустая
        {
        	result += to_string(coefficients[0]);
        }
        return result;
}

int main() 
{
	int n;
	cin >> n;
	int coefficients[MAX_POWER + 1];
	for (int i = 1; i <= n; i++)
	{
		cout << "Program #" << i << endl;
		fill(coefficients, coefficients + MAX_POWER + 1, 0); //обнуляем массив коэффициентов
		getCoefficients(coefficients);
		cout << "Runtime = " << toString(coefficients) << endl;
		if (i != n)
		{
			cout << endl; 
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <iostream>

#include <string>

#include <vector>

#define MAX_POWER 10

using namespace std;

void getCoefficients(int* coefficients)

{

int keywords = 1;

vector<string> params;

string begin;

cin >> begin;

params.push_back(((string) "1")); //чтобы вектор не был пустой на последнем END (который соответствует BEGIN)

while (true)

{

string keyword;

cin >> keyword;

if (keyword == (string)"END")

{

keywords--;

params.pop_back();

if (keywords == 0)

{

break;

}

else if (keyword == (string)"LOOP")

{

keywords++;

string param;

cin >> param;

params.push_back(param);

}

else if (keyword == (string)"OP")

{

string num;

cin >> num;

int coefficient = stoi(num);

int multiplier = 1, pow = 0;

for (string param : params)

{

if (param == (string)"n")

{

pow++;

}

else

{

multiplier *= stoi(param);

}

coefficients[pow] += coefficient * multiplier;

}

string toString(int* coefficients)

{

string result;

for (int i = MAX_POWER; i > 0; i--)

{

if (coefficients[i] != 0)

{

if (coefficients[i] == 1)

{

result += "n";

}

else if (coefficients[i] == -1)

{

result += "-n";

}

else

{

result += to_string(coefficients[i]); //стандартная функция, преобразовывает число в строку

result += "*n";

}

if (i != 1) //если степень не первая, добавляем "^[степень]"

{

result += "^";

result += to_string(i);

}

if (coefficients[i-1] > 0 && result.length() != 0) //проверка, чтобы + не стоял в начале строки и между членами не было "+-"

{

result += "+";

}

if (result.length() == 0 || coefficients[0] != 0) //прибавляем последний коэффициент, если он не равен нулю или строка пустая

{

result += to_string(coefficients[0]);

}

return result;

}

int main()

{

int n;

cin >> n;

int coefficients[MAX_POWER + 1];

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

{

cout << "Program #" << i << endl;

fill(coefficients, coefficients + MAX_POWER + 1, 0); //обнуляем массив коэффициентов

getCoefficients(coefficients);

cout << "Runtime = " << toString(coefficients) << endl;

if (i != n)

{

cout << endl;

}

return 0;

}

Ссылки

Засчитанное решение на e-olymp.

Рабочий код на ideaone.

Related Images:

e-olymp 1072. Химические реакции

04/03/2016 by Сплошнов Кирилл

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится формула — левая часть уравнения, во второй- одно число [latex]N (1 \leq N \leq 10)[/latex] — количество рассматриваемых правых частей, в каждой из последующих [latex]N[/latex] строк — одна формула — предполагаемая правая часть уравнения.

Длина формулы не превосходит [latex]100[/latex] символов, каждый отдельный химический элемент встречается всего не более [latex]10000[/latex] раз в каждой формуле.

(Примечание: понятие формулы в данном алфавите можно прочитать по ссылке выше.)

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

Для каждой из [latex]N[/latex] заданных строк вывести одну строку вида

формула левой части==формула правой части

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

формула левой части!=формула правой части

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

Решение (вспомогательные функции)

Так как задача достаточно объемная, напишем ряд вспомогательных функций:

Определяет, является ли символ цифрой.

bool isDigit(char c);

1

bool isDigit(char c);
Определяет, является ли символ буквой в верхнем регистре.

bool isUpperCaseLetter(char c);

1

bool isUpperCaseLetter(char c);
Определяет, является ли символ буквой в нижнем регистре.

bool isLowerCaseLetter(char c);

1

bool isLowerCaseLetter(char c);
Будем хранить содержимое формулы используя структуру map (карта), ключами будут выступать названия элементов (строки), значениями — количества их вхождений. Если элемента в карте нет, добавляем пару <элемент, кол-во>, иначе — прибавляем к старом числу вхождений новое. За это отвечает следующая функция.

void update(map<string, int> &map, string key, int value);

1

void update(map<string, int> &map, string key, int value);
Для простоты разобьем формулу на подформулы (по знаку [latex]+[/latex], если он встречается), и будем работать с каждой формулой по отдельности. Функция разбивает строку на подстроки по знаку [latex]+[/latex] и заполняет ими вектор [latex]storage[/latex] (так как мы не знаем кол-во подформул заранее, вектор предпочтительнее массива).

void split(string formula, vector<string> &storage);

1

void split(string formula, vector<string> &storage);
По условию, перед каждой подформулой может идти множитель, относящейся ко всей подформуле. Функция возвращает множитель ( [latex]1[/latex], если множитель не записан явно).

int getMultiplier(string formula);

1

int getMultiplier(string formula);
Основная функция. Добавляет в карту [latex]content[/latex] содержимое подформулы.

void getContent(string formula, int multiplier, map<string, int> &content);

1

void getContent(string formula, int multiplier, map<string, int> &content);
Обрабатывает формулу. Просто вызывает функции №[latex]6[/latex] и №[latex]7[/latex] по очереди для каждой из подформул (элементов из [latex]subformulas[/latex]).

void process(vector<string> subformulas, map<string, int> &content);

1

void process(vector<string> subformulas, map<string, int> &content);

Решение (основной алгоритм)

Все вспомогательные функции реализованы достаточно просто (см. код и комментарии). Рассмотрим основную функцию, алгоритм работы которой, по сути, почти является алгоритмом решения задачи.

void getContent(string formula, int multiplier, map<string, int> &content);

1	void getContent(string formula, int multiplier, map<string, int> &content);

Тут:

[latex]formula[/latex] — подформула обрабатываемой формулы (без общего множителя);
[latex]multiplier[/latex] — множитель, определяется предыдущей функцией, перед вызовом данной;
[latex]content[/latex] — карта, куда записываются элементы всех подформул текущей формулы (доступ осуществляется по адресу).

Алгоритм разделяется на 2 случая, в зависимости от наличия скобок. Предположим, скобок в подформуле (далее — просто формуле) нет. Заведем переменные [latex]name[/latex] (название элемента. тип string) и [latex]coefficient[/latex] (задний коэффициент, тип string). Тогда, проходя по порядку по символам формулы, будем выполнять следующие действия в зависимости от текущего символа([latex]c[/latex]):

[latex]c[/latex] — цифра: добавляем его в конец строки [latex]coefficient[/latex];
[latex]c[/latex] — буква в нижнем регистре: добавляем его в конец строки [latex]name[/latex];
[latex]c[/latex] — буква в верхнем регистре: если строка [latex]name[/latex] — пустая (первый элемент в формуле), то добавляем его в конец строки [latex]name[/latex]. Иначе, сперва обнуляем [latex]name[/latex], потом добавляем. Тогда, если строка [latex]coefficient[/latex] — пустая, присваиваем [latex]coefficient=[/latex]»[latex]1[/latex]». Получаем количество вхождений элемента как [latex]multiplier*stoi(coefficient)[/latex], где stoi() — стандартная функция, преобразующая число к строке. Затем добавляем в карту элемент и полученное кол-во вхождений.

update(content, name, multiplier * stoi(coefficient));

140

update(content, name, multiplier * stoi(coefficient));

(Примечание: пункт [latex]3[/latex] для последнего элемента (кроме обновления значения [latex]name[/latex]) придется повторить отдельно.)

update(content, name, multiplier * stoi(coefficient));

153	update(content, name, multiplier * stoi(coefficient));

Если же в формуле имеются скобки, то:

Находим первую открывающую скобку.
Находим соответствующую ей закрывающую скобку.
Для выражения в скобках вычисляем задний коэффициент (см. код), заносим в переменную [latex]newMultiplier[/latex] значение множителя для выражения внутри скобок.
Рекурсивно вызываем функцию getContent() для:
1. Выражения перед открывающей скобкой, если формула не начинается с нее.
  
  getContent(formula.substr(0, begin - 1), multiplier, content);
  
  106
  
  getContent(formula.substr(0, begin - 1), multiplier, content);
  
  ([latex]begin[/latex] — номер первого символа внутри скобок.)
2. Выражения внутри скобок.
  
  getContent(formula.substr(begin, end - begin), newMultiplier, content);
  
  108
  
  getContent(formula.substr(begin, end - begin), newMultiplier, content);
  
  ([latex]end[/latex] — номер закрывающей скобки.)
3. Выражения после закрывающей скобки или заднего коэффициента, если присутствует (если только скобка/коэффициент не является концом формулы).
  
  getContent(formula.substr(afterEnd), multiplier, content);
  
  111
  
  getContent(formula.substr(afterEnd), multiplier, content);
  
  ([latex]afterEnd[/latex] — следующий после скобки/коэффициента символ.)

Этот алгоритм фактически является решением задачи. Теперь в методе [latex]main[/latex] надо всего лишь обработать главную формулу, а затем для каждого случая в цикле — сравниваемую с ней формулу, сравнив после содержимое их карт (сравнение осуществляется просто используя оператор сравнения ==). Обработка подразумевает последовательный вызов функций split() и process().

Тесты

№	Ввод	Вывод
1	C2H5OH+3O2+3(SiO2) 6 2CO2+3H2O+3SiO2 2C+6H+13O+3Si 99C2H5OH+3SiO2 3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)+Ge 3(Si(O)2)+2CO+3H2O+O2	C2H5OH+3O2+3(SiO2)==2CO2+3H2O+3SiO2 C2H5OH+3O2+3(SiO2)==2C+6H+13O+3Si C2H5OH+3O2+3(SiO2)!=99C2H5OH+3SiO2 C2H5OH+3O2+3(SiO2)==3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)!=C2H5OH+3O2+3(SiO2)+Ge C2H5OH+3O2+3(SiO2)==3(Si(O)2)+2CO+3H2O+O2
2	2H2O 5 HHOHHO 2H+H2+(O(O)) 2((H2)O) HOHHOHe H4O	2H2O==HHOHHO 2H2O==2H+H2+(O(O)) 2H2O==2((H2)O) 2H2O!=HOHHOHe 2H2O!=H4O
3	8Zn+Ar4+Ne 3 Ne(Ar2(Zn)4)2 2Ne(Ar2(Zn)4) Ne+2Zn2(((((Ar)))))2Zn2	8Zn+Ar4+Ne==Ne(Ar2(Zn)4)2 8Zn+Ar4+Ne!=2Ne(Ar2(Zn)4) 8Zn+Ar4+Ne==Ne+2Zn2(((((Ar)))))2Zn2

Код

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
using namespace std;

bool isDigit(char c) { return  c >= '0' && c <= '9'; }

bool isUpperCaseLetter(char c) { return  c >= 'A' && c <= 'Z'; }

bool isLowerCaseLetter(char c) { return  c >= 'a' && c <= 'z'; }

void update(map<string, int> &map, string key, int value)
{
    if (map.count(key)) //вернет 0 (false) если элемент не найден, иначе - 1 (true)
    {
        map.at(key) = map.at(key) + value; //обновляем значение элемента в карте
    }
    else
    {
        map.insert(make_pair(key, value)); //добавляем элемент в карту
    }
}

void split(string formula, vector<string> &storage)
{
    int begin = 0, length = 0;
    for (int i = 0; i < formula.length(); i++)
    {
        if (formula.at(i) == '+')
        {
            storage.push_back(formula.substr(begin, length));
            length = 1;
            begin = ++i;
        }
        else
        {
            length++;
        }
    }
    storage.push_back(formula.substr(begin, length));
}

int getMultiplier(string formula)
{
    int res = 0;
    for (int i = 0; i < formula.length(); i++)
    {
        if (isDigit(formula.at(i))) 
        {
            res *= 10;
            res += (formula.at(i) - '0'); //получаем из символа соответствующую цифру
        }
        else break;
    }
    return res == 0 ? 1 : res; //0 - если перед формулой нет множителя, тогда он должен быть 1
}

void getContent(string formula, int multiplier, map<string, int> &content)
{ 
    if (formula.find('(') != string::npos) //если есть скобки
    {
        int begin = formula.find('(') + 1; //первый символ внутри скобок
        int end;
        int bracketCounter = 1;
        for (int i = begin; true; i++)
        {
            if (formula.at(i) == '(')
            {
                bracketCounter ++;
            }
            else if (formula.at(i) == ')')
            {
                bracketCounter--;
                if (bracketCounter == 0)
                {
                    end = i; //находим соответствующую закрывающую скобку
                    break;
                }
            }
        }
        int newMultiplier = multiplier;
        int afterEnd = end + 1;
        int backCoefficient = 0; //вычисляем коэффициент за скобочным выражением
        for (int i = 1; true; i++)
        {
            if (end + i != formula.length() && isDigit(formula.at(end + i))) //пока есть числа за закрывающей скобкой, обновляем значение заднего коэффициента
            {
                backCoefficient *= 10;
                backCoefficient += (formula.at(end + i) - '0');
                afterEnd++;
            }
            else
            {
                if (backCoefficient == 0) //если чисел после закрывающей скобки нет, коэффициент равен 1
                {
                    backCoefficient++;
                }
                newMultiplier *= backCoefficient; //вычисляем новое значение множителя для выражения внутри скобок
                break;
            }
        }
        if (begin != 1)
        {
            getContent(formula.substr(0, begin - 1), multiplier, content); 
        }
        getContent(formula.substr(begin, end - begin), newMultiplier, content); 
        if (afterEnd < formula.length())
        {
            getContent(formula.substr(afterEnd), multiplier, content);
        }
    }
    else //если скобок нет
    {
        string name = "";
        string coefficient = "";
        for (char c : formula)
        {
            if (isDigit(c)) 
            {
                coefficient += c;
            }
            else if (isLowerCaseLetter(c)) 
            {
                name += c;
            }
            else if (isUpperCaseLetter(c))
            {
                if (name.empty()) 
                {
                    name += c;
                }
                else
                {
                    if (coefficient.empty()) 
                    {
                        coefficient = "1";
                    }
                    update(content, name, multiplier * stoi(coefficient));
                    name.clear();
                    name += c;
                    coefficient = "";
                }
            }
        }
        if (!name.empty())
        {
            if (coefficient.empty()) 
            {
                coefficient = "1";
            }
            update(content, name, multiplier * stoi(coefficient));
        }
    }
}

void process(vector<string> subformulas, map<string, int> &content)
{
    for (string subformula : subformulas) //для каждой подформулы:
    {
        int multiplier = getMultiplier(subformula); //вычисляем множитель перед ней
        if (multiplier != 1) //если множитель записан явно
        {
            getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content); //передаем в функцию подформулу, начиная с первого символа, не относящегося к переднему множителю
        }
        else
        {
            getContent(subformula, multiplier, content); //иначе передаем подформулу целиком
        }
    }
}

int main() 
{
    string mainFormula;
    vector<string> mainSubformulas;
    map<string, int> mainContent;
    cin >> mainFormula;
    split(mainFormula, mainSubformulas);
    process(mainSubformulas, mainContent);
    int n;
    cin >> n;
    string formulaToCompare;
    vector<string> subformulasToCompare;
    map<string, int> contentToCompare;
    for (int i = 0; i < n; i++)
    {
        subformulasToCompare.clear(); //
        contentToCompare.clear();
        cin >> formulaToCompare;
        split(formulaToCompare, subformulasToCompare);
        process(subformulasToCompare, contentToCompare);
        cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << endl;
    }
    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

#include <iostream>

#include <cmath>

#include <string>

#include <vector>

#include <map>

using namespace std;

bool isDigit(char c) { return c >= '0' && c <= '9'; }

bool isUpperCaseLetter(char c) { return c >= 'A' && c <= 'Z'; }

bool isLowerCaseLetter(char c) { return c >= 'a' && c <= 'z'; }

void update(map<string, int> &map, string key, int value)

{

if (map.count(key)) //вернет 0 (false) если элемент не найден, иначе - 1 (true)

{

map.at(key) = map.at(key) + value; //обновляем значение элемента в карте

}

else

{

map.insert(make_pair(key, value)); //добавляем элемент в карту

}

void split(string formula, vector<string> &storage)

{

int begin = 0, length = 0;

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

{

if (formula.at(i) == '+')

{

storage.push_back(formula.substr(begin, length));

length = 1;

begin = ++i;

}

else

{

length++;

}

storage.push_back(formula.substr(begin, length));

}

int getMultiplier(string formula)

{

int res = 0;

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

{

if (isDigit(formula.at(i)))

{

res *= 10;

res += (formula.at(i) - '0'); //получаем из символа соответствующую цифру

}

else break;

}

return res == 0 ? 1 : res; //0 - если перед формулой нет множителя, тогда он должен быть 1

}

void getContent(string formula, int multiplier, map<string, int> &content)

{

if (formula.find('(') != string::npos) //если есть скобки

{

int begin = formula.find('(') + 1; //первый символ внутри скобок

int end;

int bracketCounter = 1;

for (int i = begin; true; i++)

{

if (formula.at(i) == '(')

{

bracketCounter ++;

}

else if (formula.at(i) == ')')

{

bracketCounter--;

if (bracketCounter == 0)

{

end = i; //находим соответствующую закрывающую скобку

break;

}

int newMultiplier = multiplier;

int afterEnd = end + 1;

int backCoefficient = 0; //вычисляем коэффициент за скобочным выражением

for (int i = 1; true; i++)

{

if (end + i != formula.length() && isDigit(formula.at(end + i))) //пока есть числа за закрывающей скобкой, обновляем значение заднего коэффициента

{

backCoefficient *= 10;

backCoefficient += (formula.at(end + i) - '0');

afterEnd++;

}

else

{

if (backCoefficient == 0) //если чисел после закрывающей скобки нет, коэффициент равен 1

{

backCoefficient++;

}

newMultiplier *= backCoefficient; //вычисляем новое значение множителя для выражения внутри скобок

break;

}

if (begin != 1)

{

getContent(formula.substr(0, begin - 1), multiplier, content);

}

getContent(formula.substr(begin, end - begin), newMultiplier, content);

if (afterEnd < formula.length())

{

getContent(formula.substr(afterEnd), multiplier, content);

}

else //если скобок нет

{

string name = "";

string coefficient = "";

for (char c : formula)

{

if (isDigit(c))

{

coefficient += c;

}

else if (isLowerCaseLetter(c))

{

name += c;

}

else if (isUpperCaseLetter(c))

{

if (name.empty())

{

name += c;

}

else

{

if (coefficient.empty())

{

coefficient = "1";

}

update(content, name, multiplier * stoi(coefficient));

name.clear();

name += c;

coefficient = "";

}

if (!name.empty())

{

if (coefficient.empty())

{

coefficient = "1";

}

update(content, name, multiplier * stoi(coefficient));

}

void process(vector<string> subformulas, map<string, int> &content)

{

for (string subformula : subformulas) //для каждой подформулы:

{

int multiplier = getMultiplier(subformula); //вычисляем множитель перед ней

if (multiplier != 1) //если множитель записан явно

{

getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content); //передаем в функцию подформулу, начиная с первого символа, не относящегося к переднему множителю

}

else

{

getContent(subformula, multiplier, content); //иначе передаем подформулу целиком

}

int main()

{

string mainFormula;

vector<string> mainSubformulas;

map<string, int> mainContent;

cin >> mainFormula;

split(mainFormula, mainSubformulas);

process(mainSubformulas, mainContent);

int n;

cin >> n;

string formulaToCompare;

vector<string> subformulasToCompare;

map<string, int> contentToCompare;

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

{

subformulasToCompare.clear(); //

contentToCompare.clear();

cin >> formulaToCompare;

split(formulaToCompare, subformulasToCompare);

process(subformulasToCompare, contentToCompare);

cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << endl;

}

return 0;

}

Ссылки

Засчитанное решение на e-olymp.

Код на ideaone.

Related Images:

e-olymp 1077. Java против C++

27/02/2016 by Женя Максимова

Задача. Сторонники языков Java и C++ часто спорят о том, какой язык лучше для решения олимпиадных задач. Одни говорят, что в Java есть масса полезных библиотек для работы со строками, хорошо реализованы механизмы чтения и вывода данных, а так же радует встроенные возможности для реализации длинной арифметики. С другой стороны, С++ является классическим языком, скорость выполнения программ благодаря существующим компиляторам (например, Intel Compiler 10.0) гораздо выше, чем у Java.

Но сейчас нас интересует лишь небольшие отличия, а именно соглашения, которыми пользуются программисты при описании имен переменных в Java и C++. Известно, что для понимания значений переменных часто используют английские слова или даже целые предложения, описывающие суть переменных, содержащих те или иные значения. Приведем ниже правила описания переменных, которыми руководствуются программисты, реализующие программы на Java и C++.

В языке Java принято первое слово, входящее в название переменной записывать с маленькой латинской буквы, следующее слово идет с большой буквы (только первая буква слова большая), слова не имеют разделителей и состоят только из латинских букв. Например, правильные записи переменных в Java могут выглядеть следующим образом: javaIdentifier, longAndMnemonicIdentifier, name,nEERC.

В языке C++ для описания переменных используются только маленькие латинские символы и символ «_», который отделяет непустые слова друг от друга. Примеры: java_identifier, long_and_mnemonic_identifier, name, n_e_e_r_c.

Вам требуется написать программу, которая преобразует переменную, записанную на одном языке в формат другого языка.

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

Во входном файле задано наименование переменной длиной не более [latex]100[/latex] символов.

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

В выходной файл требуется вывести аналог имени переменной в другом языке. Т.е. если переменная представлена в формате Java, то следует перевести в формат C++ и наоборот. В том случае, когда имя переменной не соответствует ни одному из вышеописанных языков, следует вывести «Error!«.

Задача взята с сайта e-olymp.

Тесты

Test	Input	Output
1	java_word	javaWord
2	cppWorD	cpp_wor_d
3	simpleword	simpleword
4	two__underscores	Error!
5	_underscore_in_the_beginning	Error!
6	underscore_in_the_end_	Error!
7	UppercaseInTheBeginning	Error!
8	mixed_Style	Error!

Код программы

#include <iostream>
#include <cstring>
using namespace std;
const int START = 0; //start state
const int CONTINUE = 1; //common prefix identifier state
const int JAVAWORD = 2; //2-4 intermediate states
const int CPPWORD = 3;
const int CPPDEL = 4; //CPP-delimeter
const int JAVA = 5; //5-10 final states
const int CPP = 6;
const int UNIVERSAL = 7;
const int JAVAERR = 8; //Error in JAVA
const int CPPERR = 9; //Error in CPP
const int ERROR = 10;
char var[101];
char result[203] = {'\0'}; //fill the resulting string with zero code characters
int reslen = 0; //the length of the resulting string
int state;
bool is_small(char c) //supporting function
{
  return ('a'<= c && c <= 'z');
}
bool is_big(char c) //supporting function
{
  return ('A'<= c && c <= 'Z');
}
bool is_underscore(char c) //supporting function
{
  return (c == '_');
}
int selection_of_style(char * var, size_t len) //determines preliminary type of string
{
  char c=var[0];
  state = START;
  if(is_small(c))
    {
      state = CONTINUE;
    }
  if(is_big(c))
    {
      state = ERROR;
      return state;
    }
  if(is_underscore(c))
    {
      state = ERROR;
      return state;
    }
  for (int i=1; i<len; i++)
    {
      c=var[i];
      if(is_small(c)) state = state;
      if(is_big(c))
        {
          state = JAVAWORD;
          return state;
        }
      if(is_underscore(c))
        {
          state = CPPWORD;
          return state;
        }
    }
  //if(state == CONTINUE)
  //in the end os the word we are still in the state CONTINUE
  state = UNIVERSAL;
  return state;
}
int is_java(char * var, size_t len)//check if the word is a correct java variable
{
  for (int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          state = state;
        }
      if(is_big(c))
        {
          state = state;
        }
      if(is_underscore(c))
        {
          state = JAVAERR;
          return state;
        }
    }
  if(state == JAVAWORD)
    {
      state = JAVA;
    }
  return state;
}
int is_cpp(char * var, size_t len) //check if the word is a correct cpp variable
{
  for (int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          if(state == CPPDEL)
            {
              state = CPPWORD;
            }
          else
            state = state;
        }
      if(is_big(c))
        {
          state = JAVAERR;
          return state;
        }

      if(is_underscore(c))
        {
          if(state == CPPDEL)
            {
              state = CPPERR;
              return state;
            }
          state = CPPDEL;
        }
    }
  if(state == CPPWORD)
    {
      state = CPP;
    }
  if(state == CPPDEL) //underscore in the end is an error too
    {
      state = CPPERR;
    }
  return state;
}
void java_to_cpp(char * var, size_t len) //function-translator
{
  for(int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          result[reslen++] = var[i]; //append character to resulting string
        }
      if(is_big(c))
        {
          result[reslen++] = '_';
          result[reslen++] = var[i]+32;
        }
    }
}
void cpp_to_java(char * var, size_t len) //function-translator
{
  for(int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          result[reslen++] = var[i];
        }
      if(is_underscore(c))
        {
          result[reslen++]=var[++i]-32;
        }
    }
}
int main()
{
  cin >> var;
  size_t len = strlen(var);
  state = selection_of_style(var, len);
  if(state == ERROR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == JAVAWORD)
    state = is_java(var,len);
  if(state == CPPWORD)
    state = is_cpp(var,len);
  if (state == UNIVERSAL)
    {
      cout << var << endl;
      return 0;
    }
  if(state == JAVAERR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == CPPERR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == JAVA)
    {
      java_to_cpp(var,len);
      cout << result;
      return 0;
    }
  if(state==CPP)
    {
      cpp_to_java(var,len);
      cout << result;
      return 0;
    }
  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

#include <iostream>

#include <cstring>

using namespace std;

const int START = 0; //start state

const int CONTINUE = 1; //common prefix identifier state

const int JAVAWORD = 2; //2-4 intermediate states

const int CPPWORD = 3;

const int CPPDEL = 4; //CPP-delimeter

const int JAVA = 5; //5-10 final states

const int CPP = 6;

const int UNIVERSAL = 7;

const int JAVAERR = 8; //Error in JAVA

const int CPPERR = 9; //Error in CPP

const int ERROR = 10;

char var[101];

char result[203] = {'\0'}; //fill the resulting string with zero code characters

int reslen = 0; //the length of the resulting string

int state;

bool is_small(char c) //supporting function

{

return ('a'<= c && c <= 'z');

}

bool is_big(char c) //supporting function

{

return ('A'<= c && c <= 'Z');

}

bool is_underscore(char c) //supporting function

{

return (c == '_');

}

int selection_of_style(char * var, size_t len) //determines preliminary type of string

{

char c=var[0];

state = START;

if(is_small(c))

{

state = CONTINUE;

}

if(is_big(c))

{

state = ERROR;

return state;

}

if(is_underscore(c))

{

state = ERROR;

return state;

}

for (int i=1; i<len; i++)

{

c=var[i];

if(is_small(c)) state = state;

if(is_big(c))

{

state = JAVAWORD;

return state;

}

if(is_underscore(c))

{

state = CPPWORD;

return state;

}

//if(state == CONTINUE)

//in the end os the word we are still in the state CONTINUE

state = UNIVERSAL;

return state;

}

int is_java(char * var, size_t len)//check if the word is a correct java variable

{

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

{

char c = var[i];

if(is_small(c))

{

state = state;

}

if(is_big(c))

{

state = state;

}

if(is_underscore(c))

{

state = JAVAERR;

return state;

}

if(state == JAVAWORD)

{

state = JAVA;

}

return state;

}

int is_cpp(char * var, size_t len) //check if the word is a correct cpp variable

{

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

{

char c = var[i];

if(is_small(c))

{

if(state == CPPDEL)

{

state = CPPWORD;

}

else

state = state;

}

if(is_big(c))

{

state = JAVAERR;

return state;

}

if(is_underscore(c))

{

if(state == CPPDEL)

{

state = CPPERR;

return state;

}

state = CPPDEL;

}

if(state == CPPWORD)

{

state = CPP;

}

if(state == CPPDEL) //underscore in the end is an error too

{

state = CPPERR;

}

return state;

}

void java_to_cpp(char * var, size_t len) //function-translator

{

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

{

char c = var[i];

if(is_small(c))

{

result[reslen++] = var[i]; //append character to resulting string

}

if(is_big(c))

{

result[reslen++] = '_';

result[reslen++] = var[i]+32;

}

void cpp_to_java(char * var, size_t len) //function-translator

{

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

{

char c = var[i];

if(is_small(c))

{

result[reslen++] = var[i];

}

if(is_underscore(c))

{

result[reslen++]=var[++i]-32;

}

int main()

{

cin >> var;

size_t len = strlen(var);

state = selection_of_style(var, len);

if(state == ERROR)

{

cout << "Error!" << endl;

return 0;

}

if(state == JAVAWORD)

state = is_java(var,len);

if(state == CPPWORD)

state = is_cpp(var,len);

if (state == UNIVERSAL)

{

cout << var << endl;

return 0;

}

if(state == JAVAERR)

{

cout << "Error!" << endl;

return 0;

}

if(state == CPPERR)

{

cout << "Error!" << endl;

return 0;

}

if(state == JAVA)

{

java_to_cpp(var,len);

cout << result;

return 0;

}

if(state==CPP)

{

cpp_to_java(var,len);

cout << result;

return 0;

}

return 0;

}

Алгоритм

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

Для удобства я изобразила этот алгоритм в виде схемы:

*круговая стрелочка означает, что мы остаемся в этом же состоянии.

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

Когда мы считываем очередной символ, мы переходим в другое состояние либо остаемся в предыдущем. В состояние Error(отмечено красным) мы переходим, если считаем какую-любо последовательность символов, не подходящую ни под один из стандартов.

Отдельно следует поговорить о состоянии CPP delimeter. Оно используется для контроля количества подчеркиваний. Если в нашей предполагаемой С++ переменной встречается подчеркивание, ей сразу же присваивается данное состояние, чтобы, при наличии второго подчеркивания сразу же перевести ее в состояние Error in CPP.

Финальные состояния отмечены зеленым цветом. В них мы переходим только после окончания строки непосредственно из предыдущего состояния. Переход в состояние Universal означает, что исходная строка состоит исключительно из маленьких букв и подходит как для языка Java, так и для C++.

Определив стандарт, к которому принадлежит переменная, мы вызываем блок перевода. Результат всегда записываем в отдельную переменную. В случае Java мы снова последовательно перебираем все символы строки и заменяем каждую встретившуюся большую букву на подчеркивание и эту же букву в маленьком регистре. Размер строки в этом случае увеличивается на количество больших букв в ее исходном варианте. В случае же С++ мы удаляем каждое подчеркивание, сдвигая все последующие символы, а первый из них переводим в большой регистр. Очевидно, что размер строки в этом случае будет уменьшен на количество подчеркиваний.

Код программы

Засчитаное решение на сайте e-olymp

Related Images:

Обратная польская запись

21/12/2015 by Зелінський Вячеслав Олександрович

// Символы во входном потоке следует вводить через пробел.
import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone{
 
	public static void main (String[] args) throws java.lang.Exception{
		try{
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			String line;
			String a1="";
			int st_len=0;
			Stack<String> st = new Stack();
			while( (line = reader.readLine()) != null){
				String[] a = line.split(" ");
				for(int i = 0 ; i < a.length ; i++){
					if(!a[i].equals("+") && !a[i].equals("-") && !a[i].equals("*") && !a[i].equals("/") && !a[i].equals("(") && !a[i].equals(")")){
						a1+=a[i];
					}
					else{
						if((a[i].equals("+") || a[i].equals("-")) && st_len>0){
							for(int j=0; j<2;j++){
								if(st_len>0){
									if(!st.peek().equals("(")){
										a1+=st.pop();
										st_len--;
									}
								}
							} 
						}
						if((a[i].equals("*") || a[i].equals("/")) && st_len>0){
							for(int j=0; j<1;j++){
								if(!st.peek().equals("(") && !st.peek().equals("+") && !st.peek().equals("-")){
									a1+=st.pop();
									st_len--;
								}
							} 
						}
						if(a[i].equals(")") && st_len>0){
							for(int j=0; j<=st_len+2;j++){
								if(!st.peek().equals("(")){
									a1+=st.pop();
									st_len--;
								}
							}
							if(st_len!=0){
					    		a1+=st.pop();
					   			st_len--;
							}
						}
						st.push(a[i]);
						st_len++;
					}
			}
			for(int i = 0 ; i < st_len ; i++){
				a1+=st.pop();
			}
			for(int i = 0 ; i < a1.length() ; i++){
				if(a1.charAt(i)!='(' && a1.charAt(i)!=')')
					System.out.print(a1.charAt(i)+" ");
				}
			}
		}catch(IOException ex){
			System.err.println("Eror");
		}
	}
}

// Символы во входном потоке следует вводить через пробел.

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone{

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

try{

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

String line;

String a1="";

int st_len=0;

Stack<String> st = new Stack();

while( (line = reader.readLine()) != null){

String[] a = line.split(" ");

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

if(!a[i].equals("+") && !a[i].equals("-") && !a[i].equals("*") && !a[i].equals("/") && !a[i].equals("(") && !a[i].equals(")")){

a1+=a[i];

}

else{

if((a[i].equals("+") || a[i].equals("-")) && st_len>0){

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

if(st_len>0){

if(!st.peek().equals("(")){

a1+=st.pop();

st_len--;

}

if((a[i].equals("*") || a[i].equals("/")) && st_len>0){

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

if(!st.peek().equals("(") && !st.peek().equals("+") && !st.peek().equals("-")){

a1+=st.pop();

st_len--;

}

if(a[i].equals(")") && st_len>0){

for(int j=0; j<=st_len+2;j++){

if(!st.peek().equals("(")){

a1+=st.pop();

st_len--;

}

if(st_len!=0){

a1+=st.pop();

st_len--;

}

st.push(a[i]);

st_len++;

}

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

a1+=st.pop();

}

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

if(a1.charAt(i)!='(' && a1.charAt(i)!=')')

System.out.print(a1.charAt(i)+" ");

}

}catch(IOException ex){

System.err.println("Eror");

}

Алгоритм:

Пока строка содержит символы для чтения, читаем очередной символ. Далее рассматриваются варианты:
1) Если символ не является символом функции или скобкой, добавляем его к выходной строке.
2)

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

Код на Ideone.

Related Images:

e-olymp 6. Путёвки

21/12/2015 by Александр Коломеец

Постановка задачи

e-olymp 6. Путёвки

Туристическая фирма не успела из-за больших морозов продать [latex]n[/latex] ([latex]n < 15[/latex]) путёвок на горнолыжные базы, срок действия которых уже наступил. С целью уменьшения убытков, было решено с 1 февраля все такие путёвки, которым осталось [latex]d_k[/latex] ([latex]d_k \le 30[/latex]) дней, продавать по номинальной стоимости – по [latex]c_k[/latex] ([latex]c_k \le 100[/latex]) грн за день только за те дни, что остались со дня продажи ([latex]k = 1..n[/latex]).

На какую наибольшую сумму можно реализовать эти путёвки, если каждый день продавать по одной путёвке?

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

Первая строка содержит количество путёвок [latex]n[/latex]. Каждая из следующих [latex]n[/latex] строк содержит два числа – количество дней [latex]d_k[/latex] и стоимость дня [latex]c_k[/latex].

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

Максимальная сумма прибыли.

Алгоритм решения

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

Первая путёвка

срок действия: 2
номинальная стоимость: 13

Вторая путёвка

срок действия: 1
номинальная стоимость: 33

Третья путёвка

срок действия: 3
номинальная стоимость: 7

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

Путевки	Перебор всех возможных вариантов
	Вариант 1		Вариант 2
	Очередность	Результат	Очередность	Результат
Первая	1	20	1	20
Вторая	2		3
Третья	3		2
	Вариант 3		Вариант 4
	Очередность	Результат	Очередность	Результат
Первая	2	53	2	20
Вторая	1		3
Третья	3		1
	Вариант 5		Вариант 6
	Очередность	Результат	Очередность	Результат
Первая	3	40	3	7
Вторая	1		2
Третья	2		1

Теперь очевидно, что максимальная сумма прибыли равна 53. Таким образом можно решить данную задачу при любых входных данных. Но возникает проблема, когда путевок слишком много (или даже не очень). Количество перестановок для [latex]n[/latex] элементов равно [latex]n![/latex]. Это значит, что при количестве путевок, равном [latex]14[/latex] (максимальное возможное количество в данной задаче), количество перестановок равно [latex]14! = 87178291200[/latex], а ведь для каждой необходимо подсчитать сумму за реализованые путевки. Современные компьютеры не могут справиться с этой задачей за короткий промежуток времени, поэтому явным решением является оптимизация программы.

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

Тесты

Входные данные	Выходные данные
4 2 37 3 45 1 46 4 30	232
3 1 1 2 2 3 3	11
4 1 2 3 4 5 6 7 8	84

Реализация

ideone: ссылка
Засчитаное решение: ссылка

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

struct ticket {
	int id, validity, price;
};

int cutDown(ticket tickets[], int count) {
	for(int validity = 0; validity <= min(30, count - 1); validity++) {
		int ticketsCount = 0;
		for(int i = 0; i < count; i++) {
			if(tickets[i].validity == validity) {
				ticketsCount++;
			}
		}
		while(ticketsCount > validity) {
			int cheapestTicketPosition = -1;
			int cheapestTicketPrice = 101;
			for(int i = 0; i < count; i++) {
				if(tickets[i].validity == validity && tickets[i].price < cheapestTicketPrice) {
					cheapestTicketPrice = tickets[i].price;
					cheapestTicketPosition = i;
				}
			}
			tickets[cheapestTicketPosition] = tickets[--count];
			ticketsCount--;
		}
	}
	return count;
}

bool comparator(const ticket t1, const ticket t2) {
	return t1.id < t2.id;
}

int main() {
	int count;
	cin >> count;
	ticket tickets[count];
	for(int i = 0; i < count; i++) {
		tickets[i].id = i;
		cin >> tickets[i].validity >> tickets[i].price;
	}
	count = cutDown(tickets, count);
	sort(tickets, tickets + count, comparator);
	int maxProfit = 0;
	do {
		int profit = 0;
		for(int i = 0; i < count; i++) {
			profit += tickets[i].validity > i ? tickets[i].price * (tickets[i].validity - i) : 0;
		}
		maxProfit = max(profit, maxProfit);
	} while(next_permutation(tickets, tickets + count, comparator));
	cout << maxProfit << endl;
	return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

struct ticket {

int id, validity, price;

};

int cutDown(ticket tickets[], int count) {

for(int validity = 0; validity <= min(30, count - 1); validity++) {

int ticketsCount = 0;

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

if(tickets[i].validity == validity) {

ticketsCount++;

}

while(ticketsCount > validity) {

int cheapestTicketPosition = -1;

int cheapestTicketPrice = 101;

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

if(tickets[i].validity == validity && tickets[i].price < cheapestTicketPrice) {

cheapestTicketPrice = tickets[i].price;

cheapestTicketPosition = i;

}

tickets[cheapestTicketPosition] = tickets[--count];

ticketsCount--;

}

return count;

}

bool comparator(const ticket t1, const ticket t2) {

return t1.id < t2.id;

}

int main() {

int count;

cin >> count;

ticket tickets[count];

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

tickets[i].id = i;

cin >> tickets[i].validity >> tickets[i].price;

}

count = cutDown(tickets, count);

sort(tickets, tickets + count, comparator);

int maxProfit = 0;

do {

int profit = 0;

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

profit += tickets[i].validity > i ? tickets[i].price * (tickets[i].validity - i) : 0;

}

maxProfit = max(profit, maxProfit);

} while(next_permutation(tickets, tickets + count, comparator));

cout << maxProfit << endl;

return 0;

}

Related Images:

Интересная последовательность

22/09/2015 by Сплошнов Кирилл

Условие (OCPC-2015)

Дана последовательность из [latex]n[/latex] чисел: [latex]x_0[/latex], [latex]x_1[/latex], [latex]x_2, \ldots, x_{n-1}[/latex], где [latex]x_0[/latex] — кол-во чисел [latex]0[/latex] в данной последовательности, [latex]x_1[/latex] — кол-во чисел [latex]1[/latex], и так далее…

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

Число [latex]n[/latex] — количество членов последовательности.

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

Искомая последовательность.

Размышления над решением:

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

[latex]x_0 + x_1 + [/latex]…[latex] + x_{n-1} = n[/latex] (1)

Далее заметим, что [latex]x_0[/latex] не может равняться нулю (ведь записав туда [latex]0[/latex], мы сразу же увеличиваем кол-во нулей до одного). Тогда [latex]x_0[/latex] равняется другому числу [latex]k[/latex], положим, большему чем 2. Тогда, [latex]x_k = 1[/latex].

Далее, положив [latex]x_1 = 2[/latex] и [latex]x_2 = 1[/latex], получаем последовательность, не нуждающуюся в дальнейших преобразованиях, в чем легко убедиться. Для наглядности:

Член последовательности	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	…	[latex]x_k[/latex]	…
Чему равен	k	2	1	0	1	0
Комментарий	[latex]k[/latex] будет найдено ниже	Количество чисел [latex]1[/latex] равно двум	Количество чисел [latex]2[/latex] равно одному	На этом промежутке только нули	[latex]k[/latex] больше двух	На этом промежутке только нули

Теперь вычислим [latex]k[/latex]. По формуле (1):

[latex]k + 2 + 1 + 1 = n[/latex]; [latex]k = n — 4[/latex]

(Примечание: При попытки подставить другие значения вместо [latex]x_1[/latex] или [latex]x_2[/latex] получится нестабильная последовательность, членам которой не получится присвоить значения согласно условию. Положив, например, [latex]x_1 = 3[/latex], нам придется увеличить кол-во единиц, что приведет к необходимости использовать другие числа последовательности, что в итоге обязательно приведет к нарушению необходимого условия (1) — сумма уже присвоенных ненулевых чисел попросту превысит количество ее оставшихся членов. Аналогично, если присвоить [latex]x_2 = 2[/latex], и уж тем более, при внесении более «крупных» изменений в последовательность. Таким образом, найденное решение является единственным.)

Очевидно, минимальное «рабочее» значение [latex]n[/latex] равно семи (при [latex]k = 2 + 1 = 3[/latex]).

Тесты (1) :

[latex]n[/latex]	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	[latex]x_3[/latex]	[latex]x_4[/latex]	[latex]x_5[/latex]	[latex]x_6[/latex]	[latex]x_7[/latex]	[latex]x_8[/latex]	…
7	3	2	1	1	0	0	0
8	4	2	1	0	1	0	0	0
9	5	2	1	0	0	1	0	0	0
…	[latex]n — 4[/latex]	2	1	0	…	…	…	…	…	…

Для [latex]n[/latex] меньше семи, решение (или их отсутствие) было найдено подбором.

Тесты (2) :

[latex]n[/latex]	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	[latex]x_3[/latex]	[latex]x_4[/latex]	[latex]x_5[/latex]
1	Решений нет
2	Решений нет
3	Решений нет
4	1 2	2 0	1 2	0 0
5	2	1	2	0	0
6	Решений нет

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

Код данной программы :

#include <iostream>
using namespace std;

int main() 
{
	int n;
	cin >> n;
	if (n < 4 || n == 6) // особые случаи (1)
		cout << "Решений нет" << endl;
	else if (n == 4) // особые случаи (2)
    {
        cout << "1 2 1 0" << endl;
        cout << "2 0 2 0" << endl;
    }
	else if (n == 5) // особый случай (3)
		cout << "2 1 2 0 0" << endl;
	else // алгоритм для общего случая
	{
		int number[n]; // создаем массив членов последовательности
		for (int i = 0; i < n; i++) // приравниваем все числа к нулю
			number[i] = 0;
		number[0] = n - 4; // выставляем значения для ненулевых членов
		number[1] = 2;
		number[2] = 1;
		number[n - 4] = 1;
		for (int i = 0; i < n; i++) // выводим по очереди элементы последовательности на экран
			cout << number[i] << " ";
		cout << endl; 
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

if (n < 4 || n == 6) // особые случаи (1)

cout << "Решений нет" << endl;

else if (n == 4) // особые случаи (2)

{

cout << "1 2 1 0" << endl;

cout << "2 0 2 0" << endl;

}

else if (n == 5) // особый случай (3)

cout << "2 1 2 0 0" << endl;

else // алгоритм для общего случая

{

int number[n]; // создаем массив членов последовательности

for (int i = 0; i < n; i++) // приравниваем все числа к нулю

number[i] = 0;

number[0] = n - 4; // выставляем значения для ненулевых членов

number[1] = 2;

number[2] = 1;

number[n - 4] = 1;

for (int i = 0; i < n; i++) // выводим по очереди элементы последовательности на экран

cout << number[i] << " ";

cout << endl;

}

return 0;

}

Также есть ссылка на рабочий код на Ideaone для желающих провести дополнительные тесты:

Ideaone.com

Related Images:

e-olymp 128. Счастливые билеты

21/09/2015 by Женя Максимова

Задача. Подсчитайте количество счастливых билетов, у которых сума первых трёх цифр равна [latex]N(N \leq 27)[/latex].

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

Тесты

Число [latex]N[/latex]	3	27	26	1	10
Количество билетов	100	1	9	9	3969

Код программы

#include <iostream>
using namespace std;
int main() 
{
  int N, c = 0;
  cin >> N;
  for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа
  {
     for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры
     {
        if ( N - i - j >= 0 && N - i - j < 10 ) //условие для третьей цифры
        { c++; } //подсчет подходящих номеров
     }
  }
  cout << c*c; //увеличение количества в c раз для шестизначного числа
  return 0;
}

#include <iostream>

using namespace std;

int main()

{

int N, c = 0;

cin >> N;

for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа

{

for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры

{

if ( N - i - j >= 0 && N - i - j < 10 ) //условие для третьей цифры

{ c++; } //подсчет подходящих номеров

}

cout << c*c; //увеличение количества в c раз для шестизначного числа

return 0;

}

Алгоритм

Любой шестизначный номер мы можем представить как 2 трехзначных номера.

Рассмотрим все варианты трехзначных номеров. Две первые цифры такого номера могут быть любыми. Переберем все их комбинации с помощью двух вложенных циклов. Для третьей цифры введем специальное условие. Она должна быть результатом вычитания двух первых цифр из [latex]N[/latex], а также быть именно цифрой, то есть меньшей 10.

Когда в цикле встречается подходящая комбинация, мы увеличиваем счетчик [latex]c[/latex] на 1. Поскольку на самом деле номер шестизначный, то каждой удачной комбинации в первой его половине будет соответствовать [latex]c[/latex] комбинаций во второй. Следовательно, искомое число счастливых билетов будет равно [latex]c \cdot c[/latex].

Решение

Код программы

Related Images:

e-olymp 138. Банкомат

20/09/2015 by Женя Максимова

Задача. В банкомате имеются в достаточном количестве купюры номиналом [latex]10, 20, 50, 100, 200[/latex] и [latex]500[/latex] гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в [latex]n[/latex] гривен[latex](0 \leq n \leq 1000001)[/latex], или вывести [latex]-1[/latex], если указанную сумму выдать нельзя.

Тесты

Сумма	130	999	7360	3	80	123450	567	440
Число купюр	3	-1	18	-1	3	249	-1	4

Код программы:

#include <stdio.h>
int Q[] = { 500, 200, 100, 50, 20, 10 }; //создание одномерного массива, в который входят все имеющиеся купюры
int main()
{
 int n, q, x; //q - вспомогательная переменная в цикле
 scanf("%d",&n); 
 x=0; //количество купюр,  ему по умолчанию присваивается 0
 for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему
 {
    q = Q[i]; 
    x += n / q; //считаем, сколько раз входит купюра в сумму
    n %= q;  //сумме присваивается остаток от деления на данную купюру
 }
 if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать
 printf("%d",x); 
 return 0;
}

#include <stdio.h>

int Q[] = { 500, 200, 100, 50, 20, 10 }; //создание одномерного массива, в который входят все имеющиеся купюры

int main()

{

int n, q, x; //q - вспомогательная переменная в цикле

scanf("%d",&n);

x=0; //количество купюр, ему по умолчанию присваивается 0

for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему

{

q = Q[i];

x += n / q; //считаем, сколько раз входит купюра в сумму

n %= q; //сумме присваивается остаток от деления на данную купюру

}

if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать

printf("%d",x);

return 0;

}

Алгоритм

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

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

Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Чтобы выяснить, так ли это, мы смотрим, что осталось от суммы после применения жадного»алгоритма. Если остаток равен [latex]0[/latex], то исходную сумму можно получить с помощью имеющихся купюр, и на экран выводится результат, полученный в цикле. Если же остаток больше [latex]0[/latex], такую операцию осуществить невозможно и программа выводит [latex]-1[/latex].

Решение

Код программы

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:

А 1041

29/06/2015 by Зелінський Вячеслав Олександрович

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

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

#include <iostream>
#include <cstdlib>

using namespace std;

const int COUNT_EL = 8, WIDTH = 8, HEIGHT = 8;
const bool SET_DIA = true, DEL_DIA = false;
int a[HEIGHT][WIDTH];				// доска
bool is_set[HEIGHT][WIDTH];			// Расположение слонов на доске
int count_null = WIDTH * HEIGHT;		// Количество пустых клеток
bool isEnd = false;				// Флаг выхода из рекурсии
const bool FIRST = true, SECOND = false;	// флаги для индификации диагоналей

int diagonal(bool is_firstD, bool set, int x, int y, int i, int j){ // осуществляет все операции с диагоналями
	while(y<HEIGHT && (is_firstD? (x<WIDTH) : (x >= 0))){					// заполняем/очищаем первую\вторую диагональ
		if(is_firstD? true : x != j || y != i){
			if(set){							  
				a[y][x]++;
				if(a[y][x] == 1){				
					count_null--;
				}
			}else{								  
				a[y][x]--;
				if(a[y][x] == 0){					
					count_null++;
				}
			}
		}
		x += (is_firstD? 1 : -1);
		y++;
	}
}

int space(bool set, int level, int i, int j){	// функция осуществляет операции с диагоналями (установку \ удаление)
	is_set[i][j] = set;			// Сохраняем последнее расположение слонов
	int x, y;
	if(j>i){	// ищем начало прохода первой диагонали (параллельной или идентичной главной)
		y = 0;
		x = j-i;
	}else{
		x = 0;
		y = i-j;
	}
	diagonal(FIRST, set, x, y, i, j);
	// ищем начало второй диагонали (перпендикулярной главной (побочной))
	int sum = i+j;
	if(sum < WIDTH){
		x = sum;
		y = 0;
	}else{
		x = WIDTH-1;
		y = sum-x;
	}
	diagonal(SECOND, set, x, y, i, j);
}

bool find_permutation(int level=0){		
	level++;

	for(int i = level-1, j = (level==1?1:0); j < WIDTH ; j++){			
	/*экспериментально было замечено, что при установки первого слона в самом начале строки нужных нам последовательностей найдено не будет
	  именно по этой причине, если мы задаем первого слона, то начинаем со второй ячейки строки 
	*/
		if(a[i][j] == 0){			
			space(SET_DIA, level, i, j);							// устанавливаем слона и поле под его боем 
			if(level != COUNT_EL){											
				find_permutation(level);											
				if(isEnd){						
					return false;
				}
			}else if(count_null == 0){					  
				cout << "Ответ найден:"<< endl << endl;			
				for( int i1=0 ; i1<HEIGHT ; i1++ ){			
					for( int j1=0 ; j1<WIDTH ; j1++ ){
						cout << (is_set[i1][j1]? 1 : 0) << (j1+1 == WIDTH ? '\n' : ' ' );
					}
				}
				isEnd = true;						
				return false;						
			}
			space(DEL_DIA, level, i, j);// удаляем слона и поле под его боем 							
		}
	}
	level--;
}

int main(){
	find_permutation();
}

#include <iostream>

#include <cstdlib>

using namespace std;

const int COUNT_EL = 8, WIDTH = 8, HEIGHT = 8;

const bool SET_DIA = true, DEL_DIA = false;

int a[HEIGHT][WIDTH]; // доска

bool is_set[HEIGHT][WIDTH]; // Расположение слонов на доске

int count_null = WIDTH * HEIGHT; // Количество пустых клеток

bool isEnd = false; // Флаг выхода из рекурсии

const bool FIRST = true, SECOND = false; // флаги для индификации диагоналей

int diagonal(bool is_firstD, bool set, int x, int y, int i, int j){ // осуществляет все операции с диагоналями

while(y<HEIGHT && (is_firstD? (x<WIDTH) : (x >= 0))){ // заполняем/очищаем первую\вторую диагональ

if(is_firstD? true : x != j || y != i){

if(set){

a[y][x]++;

if(a[y][x] == 1){

count_null--;

}

}else{

a[y][x]--;

if(a[y][x] == 0){

count_null++;

}

x += (is_firstD? 1 : -1);

y++;

}

int space(bool set, int level, int i, int j){ // функция осуществляет операции с диагоналями (установку \ удаление)

is_set[i][j] = set; // Сохраняем последнее расположение слонов

int x, y;

if(j>i){ // ищем начало прохода первой диагонали (параллельной или идентичной главной)

y = 0;

x = j-i;

}else{

x = 0;

y = i-j;

}

diagonal(FIRST, set, x, y, i, j);

// ищем начало второй диагонали (перпендикулярной главной (побочной))

int sum = i+j;

if(sum < WIDTH){

x = sum;

y = 0;

}else{

x = WIDTH-1;

y = sum-x;

}

diagonal(SECOND, set, x, y, i, j);

}

bool find_permutation(int level=0){

level++;

for(int i = level-1, j = (level==1?1:0); j < WIDTH ; j++){

/*экспериментально было замечено, что при установки первого слона в самом начале строки нужных нам последовательностей найдено не будет

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

if(a[i][j] == 0){

space(SET_DIA, level, i, j); // устанавливаем слона и поле под его боем

if(level != COUNT_EL){

find_permutation(level);

if(isEnd){

return false;

}

}else if(count_null == 0){

cout << "Ответ найден:"<< endl << endl;

for( int i1=0 ; i1<HEIGHT ; i1++ ){

for( int j1=0 ; j1<WIDTH ; j1++ ){

cout << (is_set[i1][j1]? 1 : 0) << (j1+1 == WIDTH ? '\n' : ' ' );

}

isEnd = true;

return false;

}

space(DEL_DIA, level, i, j);// удаляем слона и поле под его боем

}

level--;

}

int main(){

find_permutation();

}

Определяем переменные: количество слонов, длинна и ширина шахматного поля, массив клеток поля. Далее определяем булевы переменные для добавления и удаления диагоналей, расположения слонов, выхода из рекурсии. Функция «giagonal» осуществляет все операции с диагоналями. Добавляет/удаляет диагонали(параллельные главной или побочной). Она принимает булевы переменные для определения того, добавляем мы главную диагональ или побочную, собираемся мы добавлять диагональ или удалять. А также координаты начала диагоналей, координаты расположения слона. Если клетку бьет какой-либо слон, прибавляем к ее значению 1. При этом число свободных клеток уменьшается. Если же мы удаляем диагональ, то просто уменьшаем количество бьющих данную клетку слонов (это указывается в самой клетке). Если удаленный слон был единственным, кто ее бил, увеличиваем число свободных клеток. Функция «space». Она используется как для удаления, так и для добавления диагоналей. В ней мы запоминаем последнее расположение слонов на доске и далее ищем начало прохода диагоналей. Для этого сначала мы определяем в какой части доски находится поставленный слон и исходя из этого, если оказалось, что координата по горизонтали больше координаты по вертикали, то следовательно начало первой диагонали будет в первой строке, в противном случае ее начало будет в первом столбце. Вторые координаты зависят от разности j-i. При поиске начала второй диагонали используем сумму i+j, если эта сумма меньше 8 (то есть слон находится ближе к верхнему левому углу доски, чем к правому нижнему) тогда диагональ начинается в первом столбце. Функция «find_permutation» (рекурсивно расставляет слонов). С каждой новым поставленным слоном увеличиваем переменную level, для определения в последствии момента установки последнего слона. Просматриваем клетки, если какая-то из них не под боем-ставим туда слона и запускаем функцию «space» для него. Так расставляем их, пока число слонов не достигнет 8. Если после какой-либо расстановки мы нашли правильный ответ, то используя булеву переменную isEnd выходим из рекурсии. Если после установки восьмого слона оказалось, что все поля были заполнены, то мы выводим: «Ответ найден» и печатаем доску (если булева переменная is_set — true, то есть этот элемент слон, тогда выводим 1, остальные клетки — 0). Далее выходим из всех циклов, определив переменную isEnd = true. Удаляем слонов и битые ими поля. Конец программы.

ideone.com

Related Images:

А1035

28/06/2015 by Ковальський Олександр Дмитрович

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

Пример

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

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

a1
b3
d2
b1

a1
h8

a1
c2
e3
g2
h4
g6
h8

Решение

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

struct coord
	{
		int x,y;
	};
const int n=8;
int main()
	{
		int chessboard[n][n];
		bool k;
		string s0,s1;
		int step=0;
		coord start, finish;
		cin>>s0>>s1;
		start.x=(int)s0[0]-97;
		start.y=s0[1]-49;
		finish.x=(int)s1[0]-97;
		finish.y=s1[1]-49;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				chessboard[i][j]=-1;
		chessboard[start.x][start.y]=0;
		k=true;
		while(chessboard[finish.x][finish.y]==-1)
			{
				k=false;
				for(int i=0;i<n;i++)
					for(int j=0;j<n;j++)
						if(chessboard[i][j]==step)
							{
								for(int a=fmax(0,i-2);a<=fmin(n-1,i+2);a++)
									for(int b=fmax(0,j-2);b<=fmin(n-1,j+2);b++)
										if((chessboard[a][b]==-1)&&(((abs(i-a)==2)&&(abs(j-b)==1))||((abs(i-a)==1)&&(abs(j-b)==2))))
											{
              									chessboard[a][b]=step+1;
              									k=true;
											}
							}
					if(!k) chessboard[finish.x][finish.y]=0;
					else step++;
			}
		if (chessboard[finish.x][finish.y]==0) cout<<"start=finish"<<endl;
		else
			{
				coord path[8];
				path[0].x=finish.x;
				path[0].y=finish.y;
				for(int i=0;i<step;i++)
					{
						int x=path[i].x;
						int y=path[i].y;
						for(int a=fmax(0,x-2);a<=fmin(n-1,x+2);a++)
							for(int b=fmax(0,y-2);b<=fmin(n-1,y+2);b++)
								if((chessboard[a][b]==chessboard[x][y]-1)&&(((abs(x-a)==2)&&(abs(y-b)==1))||((abs(x-a)==1)&&(abs(y-b)==2))))
									{
										path[i+1].x=a;
										path[i+1].y=b;
									}
					}
				for(int i=step;i>=0;i--)
				cout<<(char)(path[i].x+97)<<path[i].y+1<<endl;
			}
		return 0;
	}

#include <iostream>

#include <math.h>

using namespace std;

struct coord

{

int x,y;

};

const int n=8;

int main()

{

int chessboard[n][n];

bool k;

string s0,s1;

int step=0;

coord start, finish;

cin>>s0>>s1;

start.x=(int)s0[0]-97;

start.y=s0[1]-49;

finish.x=(int)s1[0]-97;

finish.y=s1[1]-49;

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

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

chessboard[i][j]=-1;

chessboard[start.x][start.y]=0;

k=true;

while(chessboard[finish.x][finish.y]==-1)

{

k=false;

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

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

if(chessboard[i][j]==step)

{

for(int a=fmax(0,i-2);a<=fmin(n-1,i+2);a++)

for(int b=fmax(0,j-2);b<=fmin(n-1,j+2);b++)

if((chessboard[a][b]==-1)&&(((abs(i-a)==2)&&(abs(j-b)==1))||((abs(i-a)==1)&&(abs(j-b)==2))))

{

chessboard[a][b]=step+1;

k=true;

}

if(!k) chessboard[finish.x][finish.y]=0;

else step++;

}

if (chessboard[finish.x][finish.y]==0) cout<<"start=finish"<<endl;

else

{

coord path[8];

path[0].x=finish.x;

path[0].y=finish.y;

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

{

int x=path[i].x;

int y=path[i].y;

for(int a=fmax(0,x-2);a<=fmin(n-1,x+2);a++)

for(int b=fmax(0,y-2);b<=fmin(n-1,y+2);b++)

if((chessboard[a][b]==chessboard[x][y]-1)&&(((abs(x-a)==2)&&(abs(y-b)==1))||((abs(x-a)==1)&&(abs(y-b)==2))))

{

path[i+1].x=a;

path[i+1].y=b;

}

for(int i=step;i>=0;i--)

cout<<(char)(path[i].x+97)<<path[i].y+1<<endl;

}

return 0;

}

Читаем входные данные. Преобразуем их в координаты начального и финального поля на шахматной доске. Массив chessboard сначала заполняем -1 (не пройденные поля), затем значение в поле с начальными координатами присваиваем 0. Затем будем отмечать все доступные ходы коня до тех пор пока не изменится значение в финальном поле. Затем, если у нас не совпали начальное и финальное поле будем восстанавливать путь коня. Создаем массив в котором и будет путь коня. Первое значение которое мы заносим в массив будет наше финальное поле. Затем с этого поля будем рассматривать все возможные ходы которые пройдут по уже помеченным клеткам. Если в финальное поле можно было попасть несколькими путями одинаковой длины то нам не имеет значение каким из них возвращаться в начальное поле. Затем выводим массив пути в обратном порядке.

Код на ideone.

Related Images:

A1031

06/06/2015 by Денисова Ольга

Задача. Получить все перестановки элементов 1, …, 6.

Решение

Все перестановки считаются и выводятся с помощью рекурсивной функции perestanovka().

Когда в ней складывается новый набор элементов, проверяем что бы в нем не было повторяющихся значений (считаем факториал и сумму, они должны совпадать со стандартом (6! = 720, 1+2+3+4+5+6 = 21) и тогда выводим.

Что бы убедиться, что выведено правильное количество перестановок, выводим в конце значение счетчика cnt (находится внутри функции perestanovka()) и требуемое значение перестановок ( 6! = 720). Эти значения совпадают.

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

const int n = 6;
int cnt = 0;
int a[n]; 
int ft, sum;

unsigned int fact(unsigned int n) { return ( ! n || n == 1 ) ? 1 : n * fact(n - 1); }
unsigned int summa(unsigned int n) { return ( ! n || n == 1 ) ? 1 : n + summa(n - 1); }

void perestanovka(int k) { 
	int pr, sm; 
	for ( a[k] = 1; a[k] <= n; a[k]++) { 
		if ( k == n-1) {
			pr = 1; 
			sm = 0; 
			for ( int i = 0; i < n; i++) {
				pr = pr*a[i];
				sm += a[i]; 
			}
			if ( (ft == pr) && (sum == sm) ){
				for ( int i = 0; i < n; i++) cout << a[i];
				cout << endl ;
				cnt++;
			} 
		} 
		else perestanovka(k+1);
	}
	return;
}

int main() { 
	ft = fact(n);
	sum = summa(n);
	perestanovka(0);
	cout << endl << cnt << "/" << fact(n) << endl;
}

#include <iostream>

#include <stdio.h>

using namespace std;

const int n = 6;

int cnt = 0;

int a[n];

int ft, sum;

unsigned int fact(unsigned int n) { return ( ! n || n == 1 ) ? 1 : n * fact(n - 1); }

unsigned int summa(unsigned int n) { return ( ! n || n == 1 ) ? 1 : n + summa(n - 1); }

void perestanovka(int k) {

int pr, sm;

for ( a[k] = 1; a[k] <= n; a[k]++) {

if ( k == n-1) {

pr = 1;

sm = 0;

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

pr = pr*a[i];

sm += a[i];

}

if ( (ft == pr) && (sum == sm) ){

for ( int i = 0; i < n; i++) cout << a[i];

cout << endl ;

cnt++;

}

else perestanovka(k+1);

}

return;

}

int main() {

ft = fact(n);

sum = summa(n);

perestanovka(0);

cout << endl << cnt << "/" << fact(n) << endl;

}

А на Java решение выглядит так:

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

class a1031 {

	static int n;
	static int cnt ; // Количество возможных перестановок
	static int a[]; // Массив чисел с которыми делаются перестановки 
	
	static void transposition(int k) { 
		boolean flag ; 
		boolean b[] = new boolean[n]; // Массив индикаторов повторов
		
		// Для элемента k перебираются все числа
		for ( a[k] = 1; a[k] <= n; a[k]++) { 
			if ( k == n-1) { //Если элемент последний
				flag = false;
				for ( int i = 0; i < n; i++) b[i] = false; // Массиву индикаторов повторов присваивается False
				for ( int i = 0; i < n; i++) { 
					if ( b[a[i]-1] == true ) { // Проверка на повторы
						flag= true ; // Если повтор то флаг = true
						break;
					}
					else b[a[i]-1] = true; 
				}
				if ( flag == false ) { // если повторов не было то печать
					for ( int i = 0; i < n; i++) System.out.print(a[i]);
					System.out.println();
					cnt++;
				} 
			} 
			else transposition(k+1); // если не последний элемент то перебирается для следующего k
		}
		return;
	}
	
	public static void main(String[] args) { 
		n = 6;
		cnt = 0;
		a = new int[n];
		transposition(0);
		System.out.println(cnt);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class a1031 {

static int n;

static int cnt ; // Количество возможных перестановок

static int a[]; // Массив чисел с которыми делаются перестановки

static void transposition(int k) {

boolean flag ;

boolean b[] = new boolean[n]; // Массив индикаторов повторов

// Для элемента k перебираются все числа

for ( a[k] = 1; a[k] <= n; a[k]++) {

if ( k == n-1) { //Если элемент последний

flag = false;

for ( int i = 0; i < n; i++) b[i] = false; // Массиву индикаторов повторов присваивается False

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

if ( b[a[i]-1] == true ) { // Проверка на повторы

flag= true ; // Если повтор то флаг = true

break;

}

else b[a[i]-1] = true;

}

if ( flag == false ) { // если повторов не было то печать

for ( int i = 0; i < n; i++) System.out.print(a[i]);

System.out.println();

cnt++;

}

else transposition(k+1); // если не последний элемент то перебирается для следующего k

}

return;

}

public static void main(String[] args) {

n = 6;

cnt = 0;

a = new int[n];

transposition(0);

System.out.println(cnt);

}

Related Images:

А1042

01/06/2015 by Швандт Максим Альбертович

Условие:

В данной последовательности действительных чисел [latex]a_{1},…,a_{20}[/latex] выбрать возрастающую подпоследовательность наибольшей длинны.

Тесты:

Число элементов в заданной последовательности	Заданная последовательность	Найденная подпоследовательность
20	1 44 3 66 2 6 55 2 4 9 50 3 4 12 45 8 15 5 18 48	3 6 9 12 15 18
20	1 9 17 25 90 91 92 13 18 23 28 100 75 50 45 44 43 42 41 40	1 9 17 25
20	155 100 80 83 86 89 -60 -40 -20 0 20 40 60 33 33 33 0 0 0 0	-60 -40 -20 0 20 40 60

Код:

#include <stdio.h>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <deque>

using namespace std;

// вспомогательные типы
typedef vector< double > tValues;
typedef map< double, bool > tSortedValues;
typedef vector< tValues > tSequences;

// возвращает true, если первый вектор (wheer) содержит второй (what)
bool containValues( tValues& where, tValues& what )
{
   if ( what.size() > 0 )
   {
      for( int i = 0; i < where.size(); i++ )
      {
         if ( where[ i ] == what[ 0 ] )
         {
            int k = i + 1;
            int j = 1;
            for(; j < what.size() && k < where.size() && where[ k ] == what[ j ]; j++, k++ );
            return ( j == what.size() );
         }
      }
   }
   
   return false;
}

// вспомогательная функция печати последовательности
void printSequence( tValues& seq )
{
   if ( seq.size() > 1 )
   {
      double diff = seq[ 1 ] - seq[ 0 ];
      cout << "sequence: size=" << seq.size() << ", diff=" << diff << ", values = { ";
      for( int i = 0; i < seq.size(); i++ )
      {
        cout << seq[ i ] << " ";
      }
      cout << "}\n";
   }
   else
   {
      cout << "NOT a sequence" << endl;
   }
}

int main(void)
{

   int n;
   cin >> n;
   if ( n <= 0 )
   {
      cout << "Input error: wrong length of the sequence" << endl;
      return 0;
   }   

   tValues sourceValues; // вектор для входных значений, в которых мы будем искать последовательность
   for( int i = 0; i < n; i++ ) // ввод входных значений
   {
      double val;
      cin >> val;
      sourceValues.push_back( val );
   }

   // нахождение всех возможные разностей между входными значениями
   tValues diffValues;// вектор для хранения всех возможные разностей между входными значениями
   for( int i = 0; i < sourceValues.size(); i++ )
   {
      tSortedValues sortedValues;
      for( int j = 0; j < sourceValues.size(); j++ )
      {
         if ( j != i )
         {
            double diff =
               ( i < j ) ?
                  sourceValues[ j ] - sourceValues[ i ] :
                  sourceValues[ i ] - sourceValues[ j ] ;
            if ( diff > 0 )
            {
               sortedValues[ diff ] = true;
            }
        }
      }
      for( tSortedValues::iterator it = sortedValues.begin(); it != sortedValues.end(); ++it )
      {
        diffValues.push_back( it->first );
      }
   }

   // главный цикл по входным значениям
   tSequences foundSequences;// вектор векторов, в котором будем помещать все найденные последовательности
   for( int srcValIdx = 0; srcValIdx < sourceValues.size(); srcValIdx++ )
   {
      double seedVal = sourceValues[ srcValIdx ]; // начальное значение для старта поиска последовательности
      // цикл по вектору разности
      for( int diffValIdx = 0; diffValIdx < diffValues.size(); diffValIdx++ )
      {
         double diffVal = diffValues[ diffValIdx ];
         double lastVal;
         tValues candidateSeq;
         candidateSeq.push_back( seedVal );

         // поиск последовательности влево от исходного значения
         lastVal = seedVal;
         for( int j = srcValIdx - 1; j >= 0; j-- )
         {
            double prevVal = sourceValues[ j ];
            if ( prevVal == lastVal - diffVal )
            {
               candidateSeq.insert( candidateSeq.begin(), prevVal );
               lastVal = prevVal;
            }
         }

         // поиск последовательности вправо от исходного значения
         lastVal = seedVal;
         for( int j = srcValIdx + 1; j < sourceValues.size(); j++ )
         {
            double nextVal = sourceValues[ j ];
            if ( nextVal == lastVal + diffVal )
            {
               candidateSeq.push_back( nextVal );
               lastVal = nextVal;
            }
         }
         
         if ( candidateSeq.size() > 2 ) // нейденную последовательность-кандидат помещаем в вектор найденных, если длинна больше двух
         {
            foundSequences.push_back( candidateSeq );
         }
      }
   }

   // удаляем последовательности, которые включают в себя другие
   //  Удалённые последовательности заменяются на пустышки
   for( int i = 0; i < foundSequences.size(); i++ )
   {
      if ( ! foundSequences[ i ].empty() )
      {
         for( int j = 0; j < foundSequences.size(); j++ )
         {
            if ( i != j
               && foundSequences[ i ].size() >= foundSequences[ j ].size() 
               && containValues( foundSequences[ i ], foundSequences[ j ] ) )
            {
               foundSequences[ j ].clear();
            }
         }
      }
   }

    // удаляем из вектора пустышки из прошлого шага
   {
      tSequences tmp;
      for( int i = 0; i < foundSequences.size(); i++ )
      {
         if ( ! foundSequences[ i ].empty() )
         {
            tmp.push_back( foundSequences[ i ] );
         }
      }
      foundSequences = tmp;
   }
   // ищем максимальную последовательность среди найденных
   int maxSize = -1;
   int maxIndex = -1;
   for( int i = 0; i < foundSequences.size(); i++ )
   {
      int size = foundSequences[ i ].size();
      if ( size > maxSize )
      {
         maxSize  = size;
         maxIndex = i;
      }
     // printSequence( foundSequences[ i ] ); // debug 
   }

   if ( maxIndex >= 0 )
   {
      cout << "max size sequence:\n";
      printSequence( foundSequences[ maxIndex ] ); 
   }

   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

#include <stdio.h>

#include <iostream>

#include <map>

#include <string>

#include <vector>

#include <deque>

using namespace std;

// вспомогательные типы

typedef vector< double > tValues;

typedef map< double, bool > tSortedValues;

typedef vector< tValues > tSequences;

// возвращает true, если первый вектор (wheer) содержит второй (what)

bool containValues( tValues& where, tValues& what )

{

if ( what.size() > 0 )

{

for( int i = 0; i < where.size(); i++ )

{

if ( where[ i ] == what[ 0 ] )

{

int k = i + 1;

int j = 1;

for(; j < what.size() && k < where.size() && where[ k ] == what[ j ]; j++, k++ );

return ( j == what.size() );

}

return false;

}

// вспомогательная функция печати последовательности

void printSequence( tValues& seq )

{

if ( seq.size() > 1 )

{

double diff = seq[ 1 ] - seq[ 0 ];

cout << "sequence: size=" << seq.size() << ", diff=" << diff << ", values = { ";

for( int i = 0; i < seq.size(); i++ )

{

cout << seq[ i ] << " ";

}

cout << "}\n";

}

else

{

cout << "NOT a sequence" << endl;

}

int main(void)

{

int n;

cin >> n;

if ( n <= 0 )

{

cout << "Input error: wrong length of the sequence" << endl;

return 0;

}

tValues sourceValues; // вектор для входных значений, в которых мы будем искать последовательность

for( int i = 0; i < n; i++ ) // ввод входных значений

{

double val;

cin >> val;

sourceValues.push_back( val );

}

// нахождение всех возможные разностей между входными значениями

tValues diffValues;// вектор для хранения всех возможные разностей между входными значениями

for( int i = 0; i < sourceValues.size(); i++ )

{

tSortedValues sortedValues;

for( int j = 0; j < sourceValues.size(); j++ )

{

if ( j != i )

{

double diff =

( i < j ) ?

sourceValues[ j ] - sourceValues[ i ] :

sourceValues[ i ] - sourceValues[ j ] ;

if ( diff > 0 )

{

sortedValues[ diff ] = true;

}

for( tSortedValues::iterator it = sortedValues.begin(); it != sortedValues.end(); ++it )

{

diffValues.push_back( it->first );

}

// главный цикл по входным значениям

tSequences foundSequences;// вектор векторов, в котором будем помещать все найденные последовательности

for( int srcValIdx = 0; srcValIdx < sourceValues.size(); srcValIdx++ )

{

double seedVal = sourceValues[ srcValIdx ]; // начальное значение для старта поиска последовательности

// цикл по вектору разности

for( int diffValIdx = 0; diffValIdx < diffValues.size(); diffValIdx++ )

{

double diffVal = diffValues[ diffValIdx ];

double lastVal;

tValues candidateSeq;

candidateSeq.push_back( seedVal );

// поиск последовательности влево от исходного значения

lastVal = seedVal;

for( int j = srcValIdx - 1; j >= 0; j-- )

{

double prevVal = sourceValues[ j ];

if ( prevVal == lastVal - diffVal )

{

candidateSeq.insert( candidateSeq.begin(), prevVal );

lastVal = prevVal;

}

// поиск последовательности вправо от исходного значения

lastVal = seedVal;

for( int j = srcValIdx + 1; j < sourceValues.size(); j++ )

{

double nextVal = sourceValues[ j ];

if ( nextVal == lastVal + diffVal )

{

candidateSeq.push_back( nextVal );

lastVal = nextVal;

}

if ( candidateSeq.size() > 2 ) // нейденную последовательность-кандидат помещаем в вектор найденных, если длинна больше двух

{

foundSequences.push_back( candidateSeq );

}

// удаляем последовательности, которые включают в себя другие

// Удалённые последовательности заменяются на пустышки

for( int i = 0; i < foundSequences.size(); i++ )

{

if ( ! foundSequences[ i ].empty() )

{

for( int j = 0; j < foundSequences.size(); j++ )

{

if ( i != j

&& foundSequences[ i ].size() >= foundSequences[ j ].size()

&& containValues( foundSequences[ i ], foundSequences[ j ] ) )

{

foundSequences[ j ].clear();

}

// удаляем из вектора пустышки из прошлого шага

{

tSequences tmp;

for( int i = 0; i < foundSequences.size(); i++ )

{

if ( ! foundSequences[ i ].empty() )

{

tmp.push_back( foundSequences[ i ] );

}

foundSequences = tmp;

}

// ищем максимальную последовательность среди найденных

int maxSize = -1;

int maxIndex = -1;

for( int i = 0; i < foundSequences.size(); i++ )

{

int size = foundSequences[ i ].size();

if ( size > maxSize )

{

maxSize = size;

maxIndex = i;

}

// printSequence( foundSequences[ i ] ); // debug

}

if ( maxIndex >= 0 )

{

cout << "max size sequence:\n";

printSequence( foundSequences[ maxIndex ] );

}

return 0;

}

План

План программы:

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

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

Программа реализована с использованием шаблонных классов стандартной библиотеки vector и map. Vector используется для хранения всех используемых последовательностей, включая разности. Map используется, как временный объект для сортировки и слияния приращений, которые в ходе поиска встречаются с часто повторяющимися значениями.

Программа тестировалась с учётом случаев когда могут встречаться убывающие последовательности, которые должны игнорироваться.

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

Программа позволяет работать не только с фиксированными 20-ю числами. Длинна входной последовательности задаётся. Ввод содржит первым элементом длину последовательности, а затем следуют числа самой последовательности.

Ссылка на ideone.com : http://ideone.com/kf13Zv

Related Images:

e-olimp 1098. Ходи ферзем!

01/05/2015 by Денисова Ольга

Задача о восьми ферзях

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

Входные данные. В одной строке задано сначала натуральное число T (T < 6) — количество тестов. Далее через пробел задано T блоков по 8 целых чисел от 1 до 8 – номера горизонталей, на которых находится ферзь с i-той вертикали. Вертикали пронумерованы подряд.

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

Тесты

Входные данные	Выходные данные	Комментарий
2 1 1 1 1 1 1 1 1 2 4 6 8 3 2 7 5	71	пройден

Решение

«Поиск с возвратом» в задаче о восьми ферзях.
Алгоритм.
При решении задачи используется два массива : массив расстановок из теста и массив правильной расстановки. Первоначально массив правильных расстановок — пустой (все значения элементов массива = -1).

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

Как только достигается одна из возможных правильных расстановок вызывается функция calc_min_strok(). Если элемент одного массива не равен элементу другого — это ход. Функция calc_min_strok() вычисляет количество ходов для данной расстановки и решает минимальное оно или нет для данного теста.

#include <iostream>
#include <stdio.h>
#include<fstream>
using namespace std;

const int n = 8;// Размер поля
int count_test = 0;// Количество тестов
int mincountstep = n + 1; //Количество ходов
int frtest[n]; //расстановка теста
int fr[n]; //правильная расстановка

bool check(int nf) 
// проверка битых полей
{ 
	if ( fr[nf] < 0 )  return false; //На всякий случай, чтобы не проверять поля где нет ферзей
    for (int i = 0; i < n && fr[i] >= 0; i++) {           
        if ( i == nf ) continue;
        if (fr[nf] == fr[i]  ) return false;  // (Горизонталь) 
        if ( (nf + fr[nf]) ==  (i + fr[i]) ) return false; // Нисходящая диагональ
        if ( (nf - fr[nf]) ==  (i - fr[i]) ) return false; // Восходящая диагональ
    }  
    return true; //если поле свободно
}

void calc_min_strok()
// Вычисление количества ходов и нахождение минимального
{
   int countstep = 0; // количество ходов
   for (int i = 0; i < n; i++){ 
      if ( frtest[i] != fr[i] ) countstep++;
   }
   if ( mincountstep > countstep ) mincountstep = countstep;

}

bool line_up(int i)
//рекурсивня функция установки ферзей (стек расстановок)
 {
    if ( i > n-1) return false ;
    for (int j = 0; j < n; j++) { 
        fr[i] = j;
        if ( check(i) == true ) {              
            if ( i == n-1) { //Если дошли до последней колонки и всё хорошо
            calc_min_strok();
            } else { 
                line_up(i+1);
            } 
        }
        fr[i] = -1 ;  
    } 
  return false ;
}

int main()
{
	cin >> count_test;
	//Обнуление начального массива
	for (int test = 0; test < count_test; test++ ){
	   mincountstep = n + 1;
       for (int i = 0; i < n; i++) fr[i] = -1; 
       //ввод данных теста
	   for (int i = 0; i < n; i++) {     
        	cin >> frtest[i];  
		    frtest[i]--;    
	   }
       line_up(0);    
       cout << mincountstep;
	}   
    
    return 0;
}

#include <iostream>

#include <stdio.h>

#include<fstream>

using namespace std;

const int n = 8;// Размер поля

int count_test = 0;// Количество тестов

int mincountstep = n + 1; //Количество ходов

int frtest[n]; //расстановка теста

int fr[n]; //правильная расстановка

bool check(int nf)

// проверка битых полей

{

if ( fr[nf] < 0 ) return false; //На всякий случай, чтобы не проверять поля где нет ферзей

for (int i = 0; i < n && fr[i] >= 0; i++) {

if ( i == nf ) continue;

if (fr[nf] == fr[i] ) return false; // (Горизонталь)

if ( (nf + fr[nf]) == (i + fr[i]) ) return false; // Нисходящая диагональ

if ( (nf - fr[nf]) == (i - fr[i]) ) return false; // Восходящая диагональ

}

return true; //если поле свободно

}

void calc_min_strok()

// Вычисление количества ходов и нахождение минимального

{

int countstep = 0; // количество ходов

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

if ( frtest[i] != fr[i] ) countstep++;

}

if ( mincountstep > countstep ) mincountstep = countstep;

}

bool line_up(int i)

//рекурсивня функция установки ферзей (стек расстановок)

{

if ( i > n-1) return false ;

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

fr[i] = j;

if ( check(i) == true ) {

if ( i == n-1) { //Если дошли до последней колонки и всё хорошо

calc_min_strok();

} else {

line_up(i+1);

}

fr[i] = -1 ;

}

return false ;

}

int main()

{

cin >> count_test;

//Обнуление начального массива

for (int test = 0; test < count_test; test++ ){

mincountstep = n + 1;

for (int i = 0; i < n; i++) fr[i] = -1;

//ввод данных теста

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

cin >> frtest[i];

frtest[i]--;

}

line_up(0);

cout << mincountstep;

}

return 0;

}

Решение на Java:

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

public class Main {
	static int n ;// Размер поля
	static int count_test ;// Количество тестов
	static int mincountstep ; //Количество ходов
	static int frtest[]; //расстановка теста
	static int fr[]; //правильная расстановка
	
	static boolean check(int nf) 
	// проверка битых полей
	{ 
		if ( fr[nf] < 0 ) return false; //На всякий случай, чтобы не проверять поля где нет ферзей
		for (int i = 0; i < n && fr[i] >= 0; i++) { 
			if ( i == nf ) continue;
			if (fr[nf] == fr[i] ) return false; // (Горизонталь) 
			if ( (nf + fr[nf]) == (i + fr[i]) ) return false; // Нисходящая диагональ
			if ( (nf - fr[nf]) == (i - fr[i]) ) return false; // Восходящая диагональ
		} 
		return true; //если поле свободно
	}
	
	static void calc_min_strok()
	// Вычисление количества ходов и нахождение минимального
	{
		int countstep = 0; // количество ходов
		for (int i = 0; i < n; i++){ 
			if ( frtest[i] != fr[i] ) countstep++;
		}
		if ( mincountstep > countstep ) mincountstep = countstep;
	}
	
	static boolean line_up(int i)
	//рекурсивная функция установки ферзей (стек расстановок)
	{
		if ( i > n-1) return false ;
		for (int j = 0; j < n; j++) { 
			fr[i] = j;
			if ( check(i) == true ) { 
			if ( i == n-1) { //Если дошли до последней колонки и всё хорошо
				calc_min_strok();
			} else { 
				line_up(i+1);
			} 
			}
			fr[i] = -1 ; 
		} 
		return false ;
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		count_test = in.nextInt();
		n = 8;// Размер поля
		mincountstep = n + 1; //Количество ходов
		frtest = new int [n]; //расстановка теста
		fr = new int [n]; //правильная расстановка
		
		//Обнуление начального массива
		for (int test = 0; test < count_test; test++ ){
			mincountstep = n + 1;
			for (int i = 0; i < n; i++) fr[i] = -1; 
			//ввод данных теста
			for (int i = 0; i < n; i++) { 
				frtest[i] = in.nextInt();
				frtest[i]--; 
			}
			line_up(0); 
			System.out.print(mincountstep);
		} 
		System.out.println();
	}
}