e-olymp 7239. «Все, Степан! Ти мене дістав!»

23/12/2020 by Жук Світлана

Задача

Степан нещодавно відпочивав у Японії і привіз звідти нову жувальну гумку. На першій парі в університеті він поділився гумкою зі своїм товаришем. Дочекавшись моменту, коли лектор повернувся до дошки, на рахунок «три — чотири» хлопці дружньо почали надувати бульбашки. Відомо, що Степан надуває бульбашку до максимально можливого розміру за час $t_1$, після чого бульбашка миттєво лопається, і Степан починає надувати бульбашку заново з тією ж швидкістю. Товариш Степана робить те ж саме за час $t_2$.

Весь цей час викладач настільки захоплений доведенням теореми, що взагалі нічого не чує. І тільки коли обидві бульбашки лопнуть одночасно, викладач почує шум і обернеться. І тоді вже точно студентам попаде на горіхи, а більше усього тому, хто приніс на пару жувальні гумки.

Визначте, скільки часу хлопці можуть насолоджуватись надуванням бульбашок, не замічені викладачем.

Наприклад, якщо $t_1 = 2$, $t_2 = 3$, то буде відбуватись наступне:

Степан надуває бульбашку з моменту часу $t = 0$ до моменту часу $t = 2$, потім бульбашка лопається, і він надуває бульбашку знову — з моменту часу $t = 2$ до моменту часу $t = 4$, а потім ще раз — з моменту часу $t = 4$ до $t = 6$.

Товариш Степана надуває бульбашку з $t = 0$ до $t = 3$ і ще раз з $t = 3$ до $t = 6$.

В момент часу $t = 6$ бульбашки лопаються одночасно в обох студентів, викладач повертається і каже: «Все, Степан! Ти мене дістав!».

Формат вхідних даних

Перший рядок вхідного файлу містить два цілих числа $t_1, t_2 (1 \leqslant t_1, t_2 \leqslant 10^9).$

Формат вихідних даних

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

Тести

№	Вхідні дані	Вихідні дані
1	2 3	6
2	1 16	16
3	10 10	10
4	100000000 150000000	300000000
5	17 41	697

Код

#include <iostream>

using namespace std;
 
long nod (int a, int b)  {
    return b == 0 ? a : nod (b, a % b);
}
 
int main() {
    int t1, t2;
    cin >> t1 >> t2;
    cout <<  t1 * (t2 / nod (t1, t2));
    return 0;
}

#include <iostream>

using namespace std;

long nod (int a, int b) {

return b == 0 ? a : nod (b, a % b);

}

int main() {

int t1, t2;

cin >> t1 >> t2;

cout << t1 * (t2 / nod (t1, t2));

return 0;

}

Розв’язання

алгоритмом Евкліда,

Посилання

Задача на e-olymp
Код на ideone
Зараховане розв’язання на e-olymp

Related Images:

e-olymp 6941. Сумма НОД

22/12/2020 by Натан Чачко

Задача

Для заданных $n$ натуральных чисел найдите сумму НОД (наибольших общих делителей) всех возможных пар этих чисел.

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

В первой строке задано количество тестов $n \ (1 < n < 100)$. Каждый тест состоит из одной строки и содержит количество входных чисел $m \ (1 < m < 100)$, за которым следуют $m$ натуральных чисел. Все входные числа натуральные, не превышающие $10^6.$

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

Для каждого теста в отдельной строке вывести сумму $НОД$ всех возможных пар.

Тесты

№	Входные данные	Выходные данные
1	3 4 10 20 30 40 3 7 5 12 3 125 15 25	70 3 35
2	2 3 12 7 8 4 5 14 25 11	6 10
3	4 4 5 6 7 8 4 8 6 2 9 3 2 15 6 5 12 25 29 19 11	7 11 6 10

Код

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

int main() {
    int n, m, sum;
    cin >> n;
    while(n-- > 0) {
        cin >> m; 
        int ns[m];
        for(int i = 0; i < m; i++) cin >> ns[i];
        sum = 0;
        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) sum += gcd(ns[i], ns[j]);
        }
        cout << sum << endl;
    }
}

#include <iostream>

using namespace std;

int gcd(int a, int b) {

return b == 0 ? a : gcd(b, a%b);

}

int main() {

int n, m, sum;

cin >> n;

while(n-- > 0) {

cin >> m;

int ns[m];

for(int i = 0; i < m; i++) cin >> ns[i];

sum = 0;

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

for(int j = i + 1; j < m; j++) sum += gcd(ns[i], ns[j]);

}

cout << sum << endl;

}

Решение

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

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 7233. Путешествия в космосе

03/12/2020 by Євген Константинов

Задача

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

Популярностью планеты [latex]k[/latex] будем считать количество пар различных планет [latex]i[/latex] и [latex]j[/latex], перелет между которыми возможен только при использовании планеты [latex]k[/latex] [latex] (i, j, k = 1..N)[/latex]. Для заданной системы космических сообщений найти значение максимальной популярности и количество планет, достигающих её.

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

В первой строке натуральные числа [latex]N[/latex] и [latex]M[/latex] ([latex]1 \leqslant N \leqslant 1000[/latex], [latex]1 \leqslant M \leqslant 5000[/latex]). В следующих [latex]M[/latex] строках по два натуральных числа, описывающие маршрут между планетами [latex]i[/latex] и [latex]j[/latex] [latex](i, j, k = 1..N)[/latex].

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

Ответ к задаче.

Тесты

№	Входные данные	Выходные данные	Схема
1	4 4 1 2 1 3 1 4 2 3	5 1
2	14 14 1 2 2 3 2 4 3 5 1 6 6 7 7 8 8 6 1 9 9 10 10 11 9 12 1 13 13 14	75 1
3	4 4 1 2 2 3 3 4 4 1	3 4

Код

#include <iostream>
#include <vector>

using namespace std;

int inspect(int vertice, vector<int> graph[], bool visited[]);
bool allVisited(bool visited[], int n);
int firstNotVisited(bool visited[], int n);

int main() {
    int n, m, a, b;
    cin >> n >> m;
    
    vector<int> graph[n] = {};
    
    //Ввод данных, создание списка смежности графа
    
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    //Поиск наиболее популярного узла (планеты)
    //Осуществляется с помощью Depth-first search, поочередно убирая каждый узел
    //и перемножая кол-во планет в получившихся подграфах графа
    
    int maxPop = 0, maxPlanets = 0;
    for (int i = 0; i < n; i++) {
        bool visited[n] = {};
        //Отмечаем "убранный" узел как уже посещенный, чтобы не учитывать его при обходе
        visited[i] = true;
        vector<int> structures;
        //Рекурсивно проходим по всему графу, пока остаются не посещенные узлы
        //Кол-во итераций = кол-во подграфов
        while (!allVisited(visited, n))
            structures.push_back(inspect(firstNotVisited(visited, n), graph, visited));
        int pop = n - 1;
        //Изначальная популярность - кол-во других планет, т.к. перелет
        //между ними и убранной планетой уже не возможен
        for (int j = 0; j < structures.size() - 1; j++)
            for (int k = j + 1; k < structures.size(); k++)
                pop += structures[j] * structures[k];
                //Поочередно перемножаем кол-во планет из каждого подграфа
        if (pop > maxPop) {
            maxPlanets = 1;
            maxPop = pop;
        } else if (pop == maxPop)
            maxPlanets++;
    }
    cout << maxPop << " " << maxPlanets;
}

bool allVisited(bool visited[], int n) {
    for (int i = 0; i < n; i++)
        if (!visited[i]) return false;
    return true;
}

int firstNotVisited(bool visited[], int n) {
    for (int i = 0; i < n; i++)
        if (!visited[i]) return i;
    return -1;
}

int inspect(int vertice, vector<int> graph[], bool visited[]) {
    //Рекурсивный метод обхода графа
    //Проходится по всем смежным узлам из списка смежности, пока не наткнется
    //на уже посещенный узел
    int cnt = 1;
    visited[vertice] = true;
    for (auto e: graph[vertice])
        if (!visited[e])
            cnt += inspect(e, graph, visited);
    return cnt;
}

#include <iostream>

#include <vector>

using namespace std;

int inspect(int vertice, vector<int> graph[], bool visited[]);

bool allVisited(bool visited[], int n);

int firstNotVisited(bool visited[], int n);

int main() {

int n, m, a, b;

cin >> n >> m;

vector<int> graph[n] = {};

//Ввод данных, создание списка смежности графа

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

cin >> a >> b;

a--, b--;

graph[a].push_back(b);

graph[b].push_back(a);

}

//Поиск наиболее популярного узла (планеты)

//Осуществляется с помощью Depth-first search, поочередно убирая каждый узел

//и перемножая кол-во планет в получившихся подграфах графа

int maxPop = 0, maxPlanets = 0;

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

bool visited[n] = {};

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

visited[i] = true;

vector<int> structures;

//Рекурсивно проходим по всему графу, пока остаются не посещенные узлы

//Кол-во итераций = кол-во подграфов

while (!allVisited(visited, n))

structures.push_back(inspect(firstNotVisited(visited, n), graph, visited));

int pop = n - 1;

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

//между ними и убранной планетой уже не возможен

for (int j = 0; j < structures.size() - 1; j++)

for (int k = j + 1; k < structures.size(); k++)

pop += structures[j] * structures[k];

//Поочередно перемножаем кол-во планет из каждого подграфа

if (pop > maxPop) {

maxPlanets = 1;

maxPop = pop;

} else if (pop == maxPop)

maxPlanets++;

}

cout << maxPop << " " << maxPlanets;

}

bool allVisited(bool visited[], int n) {

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

if (!visited[i]) return false;

return true;

}

int firstNotVisited(bool visited[], int n) {

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

if (!visited[i]) return i;

return -1;

}

int inspect(int vertice, vector<int> graph[], bool visited[]) {

//Рекурсивный метод обхода графа

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

//на уже посещенный узел

int cnt = 1;

visited[vertice] = true;

for (auto e: graph[vertice])

if (!visited[e])

cnt += inspect(e, graph, visited);

return cnt;

}

Решение

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

Ссылки

Related Images:

e-olimp 8536. Заповнення смуги $3 \times n$

03/05/2020 by Анна Цивинская

Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані

Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

Вихідні дані

Вивести кількість способів, якими можна заповнити смугу.

Тести

Вхідні дані	Вихідні дані
1	1
5	4
12	60
50	122106097

Код № 1

#include <iostream>
using namespace std;
 
int main() {
   int n;
   cin >> n;
   int F[51] = {0, 1, 1, 2, 3};
   for(int i = 5; i <= n; i++) {
      F[i] = F[i-2] + F[i-3] + F[i-4];
   }
   cout << F[n];
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int F[51] = {0, 1, 1, 2, 3};

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

F[i] = F[i-2] + F[i-3] + F[i-4];

}

cout << F[n];

return 0;

}

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

#include <iostream>
using namespace std;
 
int F[51] = {0, 1, 1, 2, 3};
 
int numberOfWays(int n) {
   if(F[n]) {
      return F[n];
   } else {
      F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
   }
   return F[n];
}
 
int main() {
   int n;
   cin >> n;
   cout << numberOfWays(n);
   return 0;
}

#include <iostream>

using namespace std;

int F[51] = {0, 1, 1, 2, 3};

int numberOfWays(int n) {

if(F[n]) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

int main() {

int n;

cin >> n;

cout << numberOfWays(n);

return 0;

}

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Посилання

Умова задачі на E-Olymp
Зараховане рішення № 1 на E-Olymp
Зараховане рішення № 2 на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

Related Images:

e-olymp 1206. f91

29/01/2020 by Владислав Гринькив

Задача

МакКарти — известный теоретик компьютерных наук. В одной из своих работ он определил рекурсивную функцию $f_{91}$, которая определена для всякого натурального числа $n$ следующим образом:

Если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;

Если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.

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

Натуральное число $n$, не большее $1000000$.

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

Значение $f_{91}\left(n\right)$.

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5	91
2	27	91
3	91	91
4	100	91
5	102	92
6	180	170

Код

#include <iostream>
using namespace std;
long f91(long n) {
  if(n <= 100){
    return 91;
  }
  else {
    return n - 10;
  }
}
int main() {
  long n;
  cin >> n;
  cout << f91(n);
  return 0;
}

#include <iostream>

using namespace std;

long f91(long n) {

if(n <= 100){

return 91;

}

else {

return n - 10;

}

int main() {

long n;

cin >> n;

cout << f91(n);

return 0;

}

Решение

Для решения задачи создадим функцию $f_{91}\left(n\right)$ которая в зависимости от значения $n$ будет выдавать нам разные значение, а имеено:
если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;
если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.
Так же, мы можем проследить законномерность того, что если $n\leqslant100$ функция $f_{91}\left(n\right)$ будет выдавть $91$, заметив это можно будет заменить сложную, но при этом красивую рекурсивную функцию на более простое и практичное решение и получить следущие соотношение:
$f_{91}\left(n\right) = \begin{cases} 91, & n\leqslant100;\\ n-10, & n\geqslant101; \end{cases}$

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

Related Images:

e-olymp 9414. Убить всех термитов

21/12/2019 by Андрей Метасов

Условие задачи

На дереве живут термиты. Ваша задача убить их всех. Дерево является неориентированным связным графом с $n$ вершинами и $n — 1$ ребрами. Чтобы убить термитов, Вам следует отравить некоторые вершины. Если термит попадает на вершину с ядом, то он немедленно умирает. Вы не знаете, где изначально находятся термиты. Но Вы знаете, что термиты каждый раз попадают в случайную соседнюю вершину. Однако если термит прошел ребро $(u, v)$, то следующее ребро должно отличаться от $(v, u)$ за исключением случая, когда термит попадает в лист (в этом случае термит поворачивается и возвращается назад). Вам следует отравить минимальное количество вершин так, чтобы термиты попали в отравленные вершины после конечного числа шагов.

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

Первая строка содержит одно целое число $n$ $(1 \leqslant n \leqslant 100000)$. Следующая строка содержит $n — 1$ целое число $p_{i} (2 \leqslant i \leqslant n)$, означающее что ребро соединяет $p_{i}$ и $i$.

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

Выведите минимальное количество отравленных вершин.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	2 1	1
3	8 1 1 2 1 2 3 2	2
4	5 1 2 1 4	1
5	16 1 2 3 4 5 3 7 1 9 9 11 11 13 13 15	3
6	10 1 2 3 3 1 2 3 7 9	2
7	8 1 1 3 3 1 6 6	2

Код

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

const int NMAX = 100001;
vector<int> tree [NMAX]; 
vector<int> killed (NMAX, 0);
vector<bool> used (NMAX, 0);
vector<int> dist (NMAX, 0);
int ans = 0;

void kills(int v, int p)
{
    if (v == p) kills(tree[v][0], v);
    if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) kills(to, v);
    if (tree[v].size() >= 3) killed[v]++;
    return;
}

void goup(int v, int p)
{
    if (v == p)
    {
        for (auto to : tree[v]) if (dist[to] < dist[v]) goup(to, v);
        killed[v] = 0;
        return;
    }
    if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) goup(to, v);
    if (tree[v].size() >= 3)
    {
        killed[v]++;
        return;
    }
}


int main()
{
    int n,v; cin>>n;
    if (n <= 5) {cout<<1; return 0;} // Частный случай
    tree[1].push_back(0); // Корень тоже должен быть "развилкой"
    vector<int> leaves;
    for (int i = 1; i < n; i++)
    {
        cin>>v;
        tree[v].push_back(i+1);
        tree[i+1].push_back(v); //Заполнение графа в том виде, в котором его дают
    }

    for (int i = 1; i <= n; i++)
    {
        if (tree[i].size() == 1 || (i == 1 && tree[i].size() == 2)) leaves.push_back(i); //Запоминаем все листья
    }

    queue<int> q; dist[1] = 0;
    q.push(1); used[1] = true;
    while (!q.empty())
    {
        int qv = q.front(); q.pop();
        used[qv] = 1;
        for (auto to : tree[qv])                //BFS заполняющий вектор dist
        {
            if (!used[to])
            {
                q.push(to);
                dist[to] = dist[qv]+1;
            }
        }
    }

    for (auto l : leaves)
    {
        kills(l, l);        // Первый этап - запросы от каждого листа
    }

    int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = max(maxdist, dist[i]); // Определение максимального "уровня" дерева
    int wentup = 1;
    while (wentup)
    {
        wentup = 0;
        for (int l = maxdist; l > 0; l--)
        {
            for (int i = 2; i <= n; i++)
            {
                if (killed[i] == 1 && dist[i] == l)
                {
                    goup(i, i);                    //Этап 2 - поднятие "недошедших" запросов
                    wentup++;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) if (killed[i] >= 2) ans++; //Финальный подсчет "отравленных" развилок
    cout<<ans;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100001;

vector<int> tree [NMAX];

vector<int> killed (NMAX, 0);

vector<bool> used (NMAX, 0);

vector<int> dist (NMAX, 0);

int ans = 0;

void kills(int v, int p)

{

if (v == p) kills(tree[v][0], v);

if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) kills(to, v);

if (tree[v].size() >= 3) killed[v]++;

return;

}

void goup(int v, int p)

{

if (v == p)

{

for (auto to : tree[v]) if (dist[to] < dist[v]) goup(to, v);

killed[v] = 0;

return;

}

if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) goup(to, v);

if (tree[v].size() >= 3)

{

killed[v]++;

return;

}

int main()

{

int n,v; cin>>n;

if (n <= 5) {cout<<1; return 0;} // Частный случай

tree[1].push_back(0); // Корень тоже должен быть "развилкой"

vector<int> leaves;

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

{

cin>>v;

tree[v].push_back(i+1);

tree[i+1].push_back(v); //Заполнение графа в том виде, в котором его дают

}

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

{

if (tree[i].size() == 1 || (i == 1 && tree[i].size() == 2)) leaves.push_back(i); //Запоминаем все листья

}

queue<int> q; dist[1] = 0;

q.push(1); used[1] = true;

while (!q.empty())

{

int qv = q.front(); q.pop();

used[qv] = 1;

for (auto to : tree[qv]) //BFS заполняющий вектор dist

{

if (!used[to])

{

q.push(to);

dist[to] = dist[qv]+1;

}

for (auto l : leaves)

{

kills(l, l); // Первый этап - запросы от каждого листа

}

int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = max(maxdist, dist[i]); // Определение максимального "уровня" дерева

int wentup = 1;

while (wentup)

{

wentup = 0;

for (int l = maxdist; l > 0; l--)

{

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

{

if (killed[i] == 1 && dist[i] == l)

{

goup(i, i); //Этап 2 - поднятие "недошедших" запросов

wentup++;

}

for (int i = 1; i <= n; i++) if (killed[i] >= 2) ans++; //Финальный подсчет "отравленных" развилок

cout<<ans;

return 0;

}

Решение задачи

Поскольку в задаче речь идет о дереве, циклов в нем нет по определению. Значит, единственным способом для термита ходить «вечно» будет путь между двумя листами, в которых он сможет разворачиваться. Фактически, задача сводится к вопросу «Какое минимальное количество вершин в дереве нужно отравить, чтобы нельзя было добраться из любого листа в другой лист не пройдя через отравленные?».

Определим для этого $3$ типа вершин: лист, развилка и обычная вершина. Листом назовем вершину, у которой нет детей (всего $1$ связь с другой вершиной). Обычные вершины — те, у которых ровно $2$ связи (для нашего термита это пути вниз или вверх). Развилкой назовем вершину, у которой $3$ или больше связей с другими. Будем считать корень тоже развилкой, даже если у него всего $2$ связи, или листом, если одна. Через развилки можно ходить из одного листа в другой, либо «вверх» — в сторону корня.

$1$ — корень; $5,6,3$ — листья; $4$ — развилка; $2$ — обычная;

Первый этап

Очевидно, выгоднее всего «закрывать» развилки. А среди них — те, которые соединяют несколько листов напрямую. Пусть каждый лист отправляет «запрос» вверх по дереву на закрытие ближайшей к нему развилки. Когда «запрос» доходит до развилки, он тут же записывается на её счёт. Таким образом, в дереве выше вершина $4$ будет иметь $2$ запроса — от листов $5$ и $6$, а корень — $1$ запрос от листа $3$.

Теперь, просто считаем количество вершин с количеством запросов $\geqslant2$ и «закрываем» их.

Второй этап

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

Дерево, в котором необходим второй этап

Вершина $2$ и корень получают по $1$ запросу и остаются открытыми, а у термита остается путь между листами $10$ и $6$.

Для предотвращения таких случаев, пробежимся по дереву «снизу вверх» — от самого нижнего уровня до верхнего и для каждой развилки, у которой ровно $1$ запрос, сместим его вверх аналогично первому этапу — до ближайшей развилки. Будем выполнять этот шаг, пока есть такие вершины (с $1$ запросом).

В итоге, все запросы «соединятся» в нужных развилках, значение в них станет $\geqslant2$ и эти развилки нужно будет тоже закрыть. Для дерева выше, будет закрыт корень.

Осталось посчитать кол-во закрытых.

Описание алгоритма

Дерево будем хранить в массиве векторов tree. Количество запросов для вершины $i$ хранится в killed[i]. Стандартный вектор used для поиска в ширину и dist- вектор расстояний от корня до вершин, которые и будут определяться с помощью BFS.

Функция kills предназначена для того, чтобы донести запрос от листа до развилки. Она рассматривает $3$ случая:

v == p — текущая вершина совпадает с той, из которой пришли. Это крайний случай, говорящий о том, что мы только начали и находимся в листе. Тогда, идем в единственно возможном направлении — tree[v][0].
tree[v].size == 2 — вершина обычного типа, просто идем «вверх», выбирая из двух путей тот, что не совпадает с предыдущей вершиной.
tree[v].size >= 3 — попали в развилку. Увеличиваем ее значение killed[v] и выходим из рекурсии.

Функция goup отличается от kills лишь тем, что при v == p выбирает из всех направлений то, которое ближе к корню, используя dist.

Подготовка

Можно заметить, что для всех деревьев из $5$ или менее вершин ответ будет $1$. Проверим это сразу при вводе n. Далее, осторожно считываем дерево в массив векторов (см. Входные данные). В следующем цикле, определяем листья и запоминаем их в вектор leaves. Нужно учесть то, что корень может быть листом, если у него всего $2$ связи — одна с деревом, а другая — искусственно созданная нами в $0$ вершину. Последний шаг — запустить поиск в ширину из корня, который заполнит вектор dist расстояниями от корня до вершин.

Первый этап

Просто запускаем kills (l, l) из каждого листа l для «отправки» запросов в ближайшие развилки.

Второй этап

Определяем максимальную «глубину» дерева — максимальное расстояние вершины от корня. Далее, для каждого уровня от самого нижнего до корня, при определении вершины со значением killed[i] == 1 запускаем goup (i, i), а в переменной wentup считаем количество таких случаев. Как только их не останется — while выйдет из цикла.

Наконец, осталось просто посчитать количество вершин, у которых значение killed[i] >= 2.
Задача на e-olymp
Код решения на ideone
Засчитанное решение на e-olymp

Related Images:

e-olimp 1658. Факториал

04/12/2019 by Елизавета Савицкая

Задача

Вычислите факториал числа.

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

Одно целое число [latex]n[/latex] ([latex] 0 \leqslant n \leqslant 20[/latex]).

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

Выведите значение [latex]n! = 1 · 2 · 3 · … · n.[/latex]

Тесты

Входные данные	Выходные данные
3	6
0	1
20	2432902008176640000

Код № 1

#include <iostream>
using namespace std;
     
int main() {
    int n;
    long factorial = 1;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        factorial *= i;
    }
    cout << factorial;
}

#include <iostream>

using namespace std;

int main() {

int n;

long factorial = 1;

cin >> n;

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

factorial *= i;

}

cout << factorial;

}

Решение № 1

Факториал натурального числа [latex]n[/latex] определяется как произведение всех натуральных чисел от [latex]1[/latex] до [latex]n[/latex] включительно.

Код № 2

#include <iostream>
using namespace std;

long factorial (int a) {
   if (a == 0)
      return 1;
   else
      return a*factorial(a - 1);
}

int main() {
   int a, n;
   cin >> n;
   cout << factorial(n);
   return 0;
}

#include <iostream>

using namespace std;

long factorial (int a) {

if (a == 0)

return 1;

else

return a*factorial(a - 1);

}

int main() {

int a, n;

cin >> n;

cout << factorial(n);

return 0;

}

Решение № 2

Также факториал числа можно найти при помощи рекурсивной функции (функции, которая вызывает сама себя).

Ссылки

Условие задачи на E-Olymp
Код задачи № 1 на Ideone
Код задачи № 2 на Ideone

Related Images:

e-olymp 657. Игра с монетами

22/06/2019 by Богдан Подгорный

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

Условие

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более $ K$ стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

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

В первой строке находится сначала число стопок $ N,$ за ним идут $ N$ чисел, задающих количество монет в стопках слева направо, а затем число $ K.$ Все числа в строке разделены пробелами.
$ 1 \leqslant N \leqslant 180, 1 \leqslant K \leqslant 80,$ количество монет в стопке — не менее $ 1$ и не более $ 20 000$.

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

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

Тесты

№	Inputs	Outputs
1	3 4 9 1 3	14
2	4 1 2 2 7 3	5
3	5 3 4 8 1 7 2	18
4	12 67 8 6 12 6 90 54 89 145 32 45 65 4	357
5	14 32 53 5 52 9 8 17 5 87 44 51 12 15 56 10	312
6	14 76 112 3 1 98 4 172 33 65 90 2 71 18 32 14	777

Код

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

int sum[190][90][3];

int solution(vector<int>&arr, int l, int k, int p){
    if(sum[l][k][p]){
        return sum[l][k][p];
    }
    int ans = 0;
    if(arr.size() - l <= k){
        for(int i = l; i < arr.size(); i++){
            ans += arr[i];
        }
        if(p == 2){
            sum[l][k][p] = 0;
            return sum[l][k][p];
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
    if(p == 1){
        int temp = 0;
        for(int i = 1; i <= k; i++){
            temp += arr[(l-1) + i];
            ans = max(ans, temp + solution(arr, l+i, i, 3-p));
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
    else{
        int ans = INT_MAX;
        for(int i = 1; i <= k; i++){
            ans = min(ans, solution(arr, l+i, i, 3-p));
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
}

int main() {
    int n, k, a;
    vector<int> coins;
    cin >> n;
    for(int i = 0; i > a;
        coins.push_back(a);
    }
    cin >> k;
    cout << solution(coins, 0, k, 1);
    return 0;
}

#include <iostream>

#include <vector>

#include <limits.h>

using namespace std;

int sum[190][90][3];

int solution(vector<int>&arr, int l, int k, int p){

if(sum[l][k][p]){

return sum[l][k][p];

}

int ans = 0;

if(arr.size() - l <= k){

for(int i = l; i < arr.size(); i++){

ans += arr[i];

}

if(p == 2){

sum[l][k][p] = 0;

return sum[l][k][p];

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

if(p == 1){

int temp = 0;

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

temp += arr[(l-1) + i];

ans = max(ans, temp + solution(arr, l+i, i, 3-p));

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

else{

int ans = INT_MAX;

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

ans = min(ans, solution(arr, l+i, i, 3-p));

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

int main() {

int n, k, a;

vector<int> coins;

cin >> n;

for(int i = 0; i > a;

coins.push_back(a);

}

cin >> k;

cout << solution(coins, 0, k, 1);

return 0;

}

Решение

Анализируя задачу, становится понятно, что ее можно решить методами динамического программирования, а именно трехмерная динамика по параметрам: количество уже взятых стопок — l, количество стопок, которые можно взять kи какой игрок сейчас ходит p. Каждый игрок старается ходить оптимально, тогда для первого игрока задача взять максимальное количество монет, а для второго игрока задача оставить наименьшее количество монет оппоненту. Решение исполнено с помощью рекурсии, где терминальный случай-когда в массиве осталось количество стопок, меньшее или равное тому, сколько игрок может взять. Также стоит проверять высчитывалась ли раньше данная позиция, иначе задача не зайдет по времени.

Ссылки

Related Images:

e-olymp 1519. Коды Грея

23/12/2018 by Дарья Найденова

Задача

Френк Грей. Bell Lab 1930

Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность
0
1
Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди 0, а ко второй отображенной половине 1. Получим последовательность:
00
01
11
10
Продолжая процесс, на следующем шаге получим последовательность из 8 чисел. Справа от кода находится его десятичное значение
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Приведенные последовательности называются кодами Грея длины $n = 1, 2, 3$. Всего существует $2n$ разных кодов длины $n$. Каждые два соседних кода отличаются одним битом.

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

Первая строка содержит количество тестов $n$ (не более 250000). Каждая следующая строка содержит два числа: $n$ $(1 ≤ n ≤ 30)$ и $k$ $(0 ≤ k < 2^n)$.

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

Для каждого теста в отдельной строке вывести число, которое находится в $k$ — ой позиции последовательности кодов Грея длины $n$.

Тесты

№	Входные данные	Выходные данные
1	14 1 0 1 1 2 0 2 1 2 2 2 3 3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7	0 1 0 1 3 2 0 1 3 2 6 7 5 4
2	3 2 1 1 2 3 3	1 1 2
3	1 0 0	0
4	2 2 3 1 3	2 1

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

#include <iostream>
using namespace std;
 
int f(int n, int k) {
    if (!n) return 0;
    int tmp = 1 << (n - 1);
    if (k < tmp) return f(n - 1, k);
    return tmp + f(n - 1, (1 << n) - 1 - k);
}
 
int main() {
    int N, n, k;
    cin >> N;
    for (int i = N; i > 0; i--)  {
        cin >> n >> k;
        cout << f(n,k) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int f(int n, int k) {

if (!n) return 0;

int tmp = 1 << (n - 1);

if (k < tmp) return f(n - 1, k);

return tmp + f(n - 1, (1 << n) - 1 - k);

}

int main() {

int N, n, k;

cin >> N;

for (int i = N; i > 0; i--) {

cin >> n >> k;

cout << f(n,k) << endl;

}

return 0;

}

Решение

В случае, если значение бинарного кода находится в первой части последовательности, т.е. $x$ < $2^{n-1}$, то ищем число, стоящее в позиции $k$ кода Грея длины $n-1$. В другом же случае ищем число, прибавив к
$2^{n-1}$ число в позиции $2^n-k-1$ длины $n-1$. Оформим данный алгоритм в виде рекурсивной функции.

e-olymp

ideone

Related Images:

e-olymp 1452. Кролики

14/10/2018 by Владимир Дроздин

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

Задача

Как-то наконец земляне нашли обитаемую планету, назвали ее ТТВ, и отправили вместе с кораблем туда одного кролика. Кролику понравился климат новой планеты и через месяц он произвел на свет еще одного кролика. Известно, что каждый месяц каждый кролик, присутствующий на планете, производил на свет еще одного кролика. На планете откуда-то взялся монстр, который в начале месяца съедал [latex] k [/latex] кроликов, если только их становилось строго больше [latex] k [/latex]. В задаче необходимо определить количество кроликов, которое будет на планете через [latex] n [/latex]месяцев после прибытия туда космического корабля с первым кроликом.

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

Первая строка содержит количество месяцев [latex] n [/latex] [latex] (0 ≤ n ≤ 100) [/latex], вторая — число кроликов [latex] k [/latex] [latex] (0 ≤ k ≤ 10000) [/latex], которое съедал монстр.

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

Определить количество кроликов, которое будет находиться на планете ТТВ через [latex] n [/latex] месяцев после поселения туда первого кролика. Известно, что результат для любого теста всегда не больше [latex] 2 \cdot 10^9 [/latex].

Тесты

#	Входные данные	Выходные данные
1	0 10	1
2	1 10	2
3	10 7	128
4	7 128	12
5	30 0	1073741824
6	29 29	2
7	20 20	16
8	90 90	64

Cпособ 1 (с циклом)

Код

#include <iostream>
using namespace std;
 
int main() {
    long int r = 1, n, k;
    cin >> n >> k;
    for (int i = n; i > 0; i--){
        if (r > k) r -= k;
        r *= 2;
    }
    cout << r;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int r = 1, n, k;

cin >> n >> k;

for (int i = n; i > 0; i--){

if (r > k) r -= k;

r *= 2;

}

cout << r;

return 0;

}

Решение

Известно, что изначально на планете был один кролик. Создадим цикл, который будет высчитывать популяцию кроликов на планете через [latex] n [/latex] месяцев после прибытия. Цикл будет работать до тех пор, пока количество месяцев будет больше нуля. В нем будем высчитывать популяцию кроликов по простой формуле [latex] r = r \cdot 2 [/latex], где [latex] r [/latex] — количество кроликов. Если же количество кроликов, съедаемых монстром в начале месяца строго больше того количества, которое уже есть на планете, то от этой популяции отнимем [latex] k [/latex]кроликов : [latex] r = r[/latex] $-$ [latex] k [/latex]. Внутри цикла также не забываем от данного количества [latex] n [/latex] месяцев отнимать по одному каждый раз.

Способ 2 (без цикла)

Код

#include <iostream>
using namespace std;

int f2(long int r, long int n, long int k){
    if (n == 0) return r;
    if (r <= k) return f2(r * 2, n - 1, k);
    return f2(2 * (r-k), n - 1, k);
}   

int main() {
    long int n, k, r = 1;
    cin >> n >> k;
    cout << f2(r, n, k);
    return 0;
}

#include <iostream>

using namespace std;

int f2(long int r, long int n, long int k){

if (n == 0) return r;

if (r <= k) return f2(r * 2, n - 1, k);

return f2(2 * (r-k), n - 1, k);

}

int main() {

long int n, k, r = 1;

cin >> n >> k;

cout << f2(r, n, k);

return 0;

}

Решение

Сам алгоритм похож на 1 способ, однако здесь мы будем использовать рекурсивную функцию, а не цикл. Функция int f2(); будет вызывать сама себя до тех пор, пока количество месяцев [latex] n [/latex] не станет равным нулю.

Ссылки

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

1 Код в ideone.

2 Код в ideone.

Related Images:

e-olymp 1868. Функция

25/12/2017 by Иван Василевский

Условие задачи
Вычислите функцию:

[latex]f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}[/latex]

Входные данные
Одно натуральное число [latex] n \; [/latex] [latex](1 \leq n \leq 10^{12}) [/latex].

Выходные данные
Значение [latex] f(n) [/latex], взятое по модулю [latex] 2^{32} [/latex].
Continue reading →

Related Images:

e-olymp 2214. Функция 9

23/12/2017 by Андрей Лисовой

Задача

Дана функция, аргументы которой — произвольные натуральные числа

[latex]f(M,N)=\begin{cases} f(M-N,N), & \text{ npu } M>N \\ N, & \text{ npu } M=N \\ f(N-M,M) & \text{ npu } N>M \end{cases}[/latex]

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

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

Два натуральных числа [latex]n[/latex] и [latex]m[/latex] [latex](1 \le n, m \le 10^{18})[/latex].

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

Искомое значение функции.

Тесты

Входные данные	Выходные данные
[latex]6[/latex] [latex]3[/latex]	[latex]3[/latex]
[latex]12[/latex] [latex]12[/latex]	[latex]12[/latex]
[latex]126[/latex] [latex]98[/latex]	[latex]98[/latex]
[latex]10329[/latex] [latex]1501[/latex]	[latex]1501[/latex]
[latex]1008359[/latex] [latex]15113[/latex]	[latex]15113[/latex]

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

#include <iostream>
using namespace std;
 
unsigned long long f(unsigned long long n, unsigned long long m) {
    if (n % m == 0) return m;
    if (m % n == 0) return n;
    if (m > n) f(m % n, n);
    else  f(n % m , m);
}
 
int main() {
    unsigned long long n, m, t;
    cin >> m >> n;
    t = f(m, n);
    cout << t;
    return 0;
}

#include <iostream>

using namespace std;

unsigned long long f(unsigned long long n, unsigned long long m) {

if (n % m == 0) return m;

if (m % n == 0) return n;

if (m > n) f(m % n, n);

else f(n % m , m);

}

int main() {

unsigned long long n, m, t;

cin >> m >> n;

t = f(m, n);

cout << t;

return 0;

}

Решение задачи

Для решения задачи напишем функцию [latex]f[/latex]. Именно эта функция и будет считать искомое значение. Из условия задачи видим, что для решения потребуется рекурсия. Для этого, если остаток от деления одного натурального числа на другое не равен нулю, то мы снова возращаемся в функцию (в зависимости от того,
что больше [latex]m[/latex] или [latex]n[/latex]). Это будет продолжаться до тех пор, пока остаток от деления одного натурального числа на другое не будет равен нулю (как только $n\mod m = 0$ или $m\mod n = 0$, то функция возращает в переменную [latex]t[/latex] искомое значение). Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images:

e-olymp 1521. Оптимальное умножение матриц

07/05/2017 by Тимур Фирсов

Задача

Имея два двумерных массива [latex]A[/latex] и [latex]B[/latex], мы можем вычислить [latex]C = AB[/latex] используя стандартные правила умножения матриц. Число колонок в массиве [latex]A[/latex] должно совпадать с числом строк массива [latex]B[/latex]. Обозначим через [latex]rows(A)[/latex] и [latex]columns(A)[/latex] соответственно количество строк и колонок в массиве [latex]A[/latex]. Количество умножений, необходимых для вычисления матрицы [latex]C[/latex] (ее количество строк совпадает с [latex]A[/latex], а количество столбцов с [latex]B[/latex]) равно [latex]rows(A) columns(B) columns(A)[/latex]. По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.

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

Каждый тест состоит из количества [latex]n (n ≤ 10)[/latex] перемножаемых матриц, за которым следуют [latex]n[/latex] пар целых чисел, описывающих размеры матриц (количество строк и столбцов). Размеры матриц задаются в порядке их перемножения. Последний тест содержит [latex]n = 0[/latex] и не обрабатывается.

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

Пусть матрицы пронумерованы [latex]A_{1}[/latex], [latex]A_{2}[/latex],…, [latex]A_{n}[/latex]. Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с [latex]1[/latex]. Вывод должен строго соответствовать формату, приведенному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.

Тесты

№	Входные данные	Выходные данные
1	3 1 5 5 20 20 1 3 5 10 10 20 20 35 6 30 35 35 15 15 5 5 10 10 20 20 25 0	Case 1: (A1 x (A2 x A3)) Case 2: ((A1 x A2) x A3) Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
2	10 653 273 273 692 692 851 851 691 691 532 532 770 770 690 690 582 582 519 519 633 0	Case 1: (A1 x ((((((((A2 x A3) x A4) x A5) x A6) x A7) x A8) x A9) x A10))
3	2 11 12 12 33 7 1 5 5 28 28 19 19 2 2 10 10 1 1 12 4 10 29 29 133 133 8 8 15 0	Case 1: (A1 x A2) Case 2: (((((A1 x A2) x A3) x A4) x (A5 x A6)) x A7) Case 3: ((A1 x (A2 x A3)) x A4)

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

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

int n;
vector <int> v;
void f(long long **a, long long i, long long j ){
    if(a[j][i]>0){
        v.push_back(a[j][i]);
        if((a[j][i]<=n)&&(i<=n)&&(j<=n)){
            f(a,i,a[j][i]);
            f(a,a[j][i],j);
        }
    }
}
string answer(long long x, long long si, long long sj, long long el){
     long long z1=el,z2=el;
     if(sj!=si){
        if(si!=x){
            while((v[v.size()-z1]<si)||(v[v.size()-z1]>=x))z1++;
        }
        if(sj!=(x+1)){
            while((v[v.size()-z2]<(x+1))||(v[v.size()-z2]>=sj))z2++; 
        }
     }
    return si==sj? "A"+to_string(si):"("+answer(v[v.size()-z1],si,x,z1+1)+" x "+answer(v[v.size()-z2],x+1,sj,z2+1)+")";
}
int main() {
    long long i,j,useless,number=1,**dp;
    cin>>n;
    while(n){
        n++;
        dp = new long long* [n];
        for(i=0;i<n;i++)dp[i]=new long long [n];
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                dp[i][j]=0;
            }
        }
        cin>>dp[0][0];
        for(i=1;i<n;i++){
            cin>>dp[i][i];
            if(i<(n-1))cin>>useless;//лишние для нас значения
        }
        i=2;
        for(i=2;i<n;i++){        
            for(j=0;j<=(i-2);j++){
                dp[i][j]=2e10;
            }
        }
        long long t;
        for(i=2;i<n;i++){
            for(j=0;j<(n-i);j++){
                long long k=j+i;
                for(t=1;(j+t)<(n-1);t++){
                    if(dp[k][j]>(dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t])){
                        dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t];
                        dp[j][k]=j+t;//запоминаем последнее умножение
                    }
                }
            }
        }
        f(dp,n-1,0);//восстанавливаем порядок умножений (от последнего к первому)
        reverse(v.begin(),v.end());
        cout<<"Case "<<number<<": "<<answer(v[v.size()-1],1,n-1,1)<<'\n';
        number++;
        delete [] dp;//очищаем память для следующего теста
        v.clear();
        cin>>n;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

int n;

vector <int> v;

void f(long long **a, long long i, long long j ){

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

v.push_back(a[j][i]);

if((a[j][i]<=n)&&(i<=n)&&(j<=n)){

f(a,i,a[j][i]);

f(a,a[j][i],j);

}

string answer(long long x, long long si, long long sj, long long el){

long long z1=el,z2=el;

if(sj!=si){

if(si!=x){

while((v[v.size()-z1]<si)||(v[v.size()-z1]>=x))z1++;

}

if(sj!=(x+1)){

while((v[v.size()-z2]<(x+1))||(v[v.size()-z2]>=sj))z2++;

}

return si==sj? "A"+to_string(si):"("+answer(v[v.size()-z1],si,x,z1+1)+" x "+answer(v[v.size()-z2],x+1,sj,z2+1)+")";

}

int main() {

long long i,j,useless,number=1,**dp;

cin>>n;

while(n){

n++;

dp = new long long* [n];

for(i=0;i<n;i++)dp[i]=new long long [n];

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

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

dp[i][j]=0;

}

cin>>dp[0][0];

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

cin>>dp[i][i];

if(i<(n-1))cin>>useless;//лишние для нас значения

}

i=2;

for(i=2;i<n;i++){

for(j=0;j<=(i-2);j++){

dp[i][j]=2e10;

}

long long t;

for(i=2;i<n;i++){

for(j=0;j<(n-i);j++){

long long k=j+i;

for(t=1;(j+t)<(n-1);t++){

if(dp[k][j]>(dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t])){

dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t];

dp[j][k]=j+t;//запоминаем последнее умножение

}

f(dp,n-1,0);//восстанавливаем порядок умножений (от последнего к первому)

reverse(v.begin(),v.end());

cout<<"Case "<<number<<": "<<answer(v[v.size()-1],1,n-1,1)<<'\n';

number++;

delete [] dp;//очищаем память для следующего теста

v.clear();

cin>>n;

}

return 0;

}

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

Решение

Пусть [latex]A[/latex]- любая не последняя матрица заданной последовательности, [latex]B[/latex] — матрица, что следует за [latex]A[/latex] в данной последовательности перемножаемых матриц. Заведём двумерный массив [latex]dp[/latex] размером [latex] {(n+1)}\times {(n+1)}[/latex]. По главной диагонали массива запишем размеры матриц, причём [latex]rows(B)[/latex] не будем записывать, так как [latex]rows(B)=columns(A)[/latex]. В dp[k][j] [latex]\left( j<k \right) [/latex] будем хранить минимальное количество операций необходимое для получения матрицы [latex]C_{kj}[/latex] такой, что [latex]columns(C_{kj})[/latex] равно элементу dp[k][k], а [latex]rows(C_{kj})[/latex] соответственно dp[j][j]. Для получения матрицы [latex]C_{kj}[/latex] нужно умножить матрицу [latex]C_{k(j+t)}[/latex] на [latex]C_{(j+t)j}[/latex] [latex](\left( k-j \right) >t>0)[/latex], для этого нам понадобиться [latex]rows(C_{k(j+t)}) columns(C_{(j+t)j}) columns(C_{k(j+t)}) [/latex], что равно dp[k][k]*dp[j][j]*dp[j+t][j+t], операций непосредственно на перемножение этих матриц, а также dp[k][j+t] и dp[j+t][j] операций для получения матриц [latex]C_{k(j+t)}[/latex] и [latex]C_{(j+t)j}[/latex] соответственно.
Тогда dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t]. При помощи цикла подберём [latex] t [/latex], при котором значение dp[k][j] выходит минимальным. Для получения матриц, которые даны изначально, не требуется ни одной операции, поэтому диагональ массива прилегающую к главной диагонали оставим заполненной нулями. Далее, при помощи вложенных циклов на каждом шаге внешнего цикла будем заполнять диагональ массива, что расположена ниже предыдущей. Параллельно будем запоминать номер последнего умножения, который будет равен [latex]j+t[/latex], в элемент массива, который расположен симметрично dp[k][j] относительно главной диагонали (то есть в dp[j][k]). Таким образом от умножения двух исходных матриц поэтапно перейдём к оптимальному произведению [latex]n[/latex] матриц. Затем, рекурсивно восстановим оптимальный порядок умножения матриц. Для вывода ответа в соответствующем формате также воспользуемся рекурсией.

Ссылки

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:

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:

А98

03/11/2014 by Янішевська Альона Русланівна

Задача. Пусть [latex]a_{1}=b_{1}=1; a_{k}=3b_{k-1}+2a_{k-1}; b_{k}=2a_{k-1}+b_{k-1}[/latex], [latex]k=\overline{2, \infty }[/latex]. Дано натуральное [latex]n[/latex]. Найти [latex]\sum_{i=1}^{n}\frac{2^{k}}{(1+a_{k}^{2}+b_{k}^{2})k!}[/latex].

Тесты:

n	[latex]\sum_{i=1}^{n}\frac{2^{k}}{(1+a_{k}^{2}+b_{k}^{2})k!}[/latex]	Комментарий
2	0.0596538	Пройден
4	0.0597339	Пройден
20	0.059734	Пройден

Код:

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

int main() {
      int n, a=1, as=a, b=1;
      double S=0.0, u=2.0;
      cin >> n;
      for(int i=1, k=2; i<=n; i++, k++)
      {
          a=3*b+2*a;
          b=2*as+b;
          u*=(2.0/k);
          S+=u*(1.0/(1+a*a+b*b));
          as=a; //запоминание переменной а
      }
       printf("%7lf", S);
       return 0;
 }

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int n, a=1, as=a, b=1;

double S=0.0, u=2.0;

cin >> n;

for(int i=1, k=2; i<=n; i++, k++)

{

a=3*b+2*a;

b=2*as+b;

u*=(2.0/k);

S+=u*(1.0/(1+a*a+b*b));

as=a; //запоминание переменной а

}

printf("%7lf", S);

return 0;

}

Для решения данной задачи понадобилось ввести переменную [latex]n[/latex], которая показывает какое количество раз нужно повторить операцию сложения. В цикле for вычисляется сумма, по заданной формуле. Далее последовательность можно задать рекурентно: чтобы каждый раз не считать [latex]\frac{2^{k}}{k!}[/latex], мы заводим переменную u, равную изначально двум, потому что k начинается с 2, и u каждый раз мы будем домножать на [latex]\frac{2}{k}[/latex]. Далее остается лишь посчитать a и b (переменная [latex]as[/latex] запоминает переменную [latex]a[/latex] для последующего вычисления переменной [latex]b[/latex]) и поставить в формулу. Для проверки выполнения программы можно воспользоваться ссылкой.

Решение на Java:

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner  in = new Scanner(System.in);
		int n, a=1, as=a, b=1;
		double sum=0.0, u=2.0;
		n = in.nextInt();
		for(int i=1, k=2; i<=n; i++, k++)
      	{
      		a=3*b+2*a;
      		b=2*as+b;
      		u*=(2.0/k);
      		sum+=u*(1.0/(1+a*a+b*b));
      		as=a;
      	}
       System.out.printf(Locale.US, "%.8f", sum); 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int n, a=1, as=a, b=1;

double sum=0.0, u=2.0;

n = in.nextInt();

for(int i=1, k=2; i<=n; i++, k++)

{

a=3*b+2*a;

b=2*as+b;

u*=(2.0/k);

sum+=u*(1.0/(1+a*a+b*b));

as=a;

}

System.out.printf(Locale.US, "%.8f", sum);

}

Ссылка на решение.