OCPC-2021. Задача B. Палиндромонойя (код решения)

20/01/2024 by Александр Мармалюк

Условие

Студент Илья, постоялец палаты номер 101 заведения «Покосившийся Скворечник», попавший сюда во время сессии на почве экзамена по программированию, убеждён, что его повсюду преследуют затаившиеся палиндромы. «Они среди нас! Как же вы этого не замечаете?!» – то и дело слышат от него нянечки Алла и Анна. По убеждению Ильи, палиндром – это слово, читающееся одинаково, как слева направо, так и справа налево. Если же на первый взгляд слово таковым не является, то студент не опускает рук и переносит буквы по одной из начала слова в конец, пока оно не станет палиндромом. Если из слова таким образом удалось получить палиндром за 0 или более операций, Илья называет его затаившимся палиндромом, после чего студент начинает бегать по потолку с воплями отчаяния, чем доставляет неудобства окружающим. Например, Илью может довести до исступления слово «масса», ведь из него можно получить «самас», перенеся 3 буквы из начала в конец. Главврач хочет выкинуть из палаты номер 101 Илью, но вместо этого выкинет все предметы, названия которых являются затаившимися палиндромами. Осталось только проверить их все, а здесь без программы не обойтись!

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

Выведите одну строку: «yes» без кавычек, если предмет с этим названием стоит выбросить и «no» без кавычек, если его стоит оставить в палате номер 101.

Тесты

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

array	yes
iliya	no
anna	yes
cbaabcb	yes
arrya	no
anana	yes
bcdcbaa	yes

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

#include <iostream>
#include <string>
using namespace std;
bool palindrome (string const *s) {
    for (int i = 0; i < (*s).size() / 2; ++i) {
        if ((*s)[i] != (*s)[(*s).size() - i - 1]) return false;
    }
    return true;
}
int main() {
    string s;
    cin >> s;
    for (int i = 0; i <= s.length(); i++) {
        s += s[0];
        s.erase(s.begin());
        if (palindrome(&s)) {
            cout << "yes";
            return 0;
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

bool palindrome (string const *s) {

for (int i = 0; i < (*s).size() / 2; ++i) {

if ((*s)[i] != (*s)[(*s).size() - i - 1]) return false;

}

return true;

}

int main() {

string s;

cin >> s;

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

s += s[0];

s.erase(s.begin());

if (palindrome(&s)) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №1

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

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

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

int main() {
    string s;
    cin >> s;
    int n = s.length();
    //дублируем строку, чтобы иметь возможность просмотреть все циклические перестановки
    s += s;
    const int p = 31;
    vector <long long> p_pow (2*n); //вектор степеней числа p
    p_pow[0] = 1;
    for (int i = 1; i < 2*n; ++i) p_pow[i] = p * p_pow[i-1];
    long long P1 = 0, P2 = 0;
    for (int i = 0; i < n; ++i) {
        P1 += (s[i] - 'a' + 1) * p_pow[i];
        P2 += (s[n - i - 1] - 'a' + 1) * p_pow[i];
    }
    if (P1 == P2) {
        bool check = true;
        for (int i = 0; i < n; ++i)
            if (s[i] != s[n - i - 1]) check = false;
        if (check) {
            cout << "yes";
            return 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        P1 += (s[i+n] - 'a' + 1)*p_pow[i+n] - (s[i] - 'a' + 1)*p_pow[i];
        P2 = (P2 - (s[i] - 'a' + 1)*p_pow[n + i - 1]) * p_pow[2] + (s[i+n]-'a' + 1) * p_pow[i+1];
        if (P1 == P2) {
            bool check = true;
            for (int j = i + 1; j < i + 1 + n; ++j)
                if (s[j] != s[2*i + 1 + n - j]) check = false;
            if (check) {
                cout << "yes";
                return 0;
            }
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

string s;

cin >> s;

int n = s.length();

//дублируем строку, чтобы иметь возможность просмотреть все циклические перестановки

s += s;

const int p = 31;

vector <long long> p_pow (2*n); //вектор степеней числа p

p_pow[0] = 1;

for (int i = 1; i < 2*n; ++i) p_pow[i] = p * p_pow[i-1];

long long P1 = 0, P2 = 0;

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

P1 += (s[i] - 'a' + 1) * p_pow[i];

P2 += (s[n - i - 1] - 'a' + 1) * p_pow[i];

}

if (P1 == P2) {

bool check = true;

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

if (s[i] != s[n - i - 1]) check = false;

if (check) {

cout << "yes";

return 0;

}

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

P1 += (s[i+n] - 'a' + 1)*p_pow[i+n] - (s[i] - 'a' + 1)*p_pow[i];

P2 = (P2 - (s[i] - 'a' + 1)*p_pow[n + i - 1]) * p_pow[2] + (s[i+n]-'a' + 1) * p_pow[i+1];

if (P1 == P2) {

bool check = true;

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

if (s[j] != s[2*i + 1 + n - j]) check = false;

if (check) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №2

Для решения задачи можно воспользоваться техникой хеширования строк. Изначально продублируем строку, поскольку тогда все циклические перестановки исходной строки будут подстроками длины $n$ продублированной строки, где $n$ — длина исходной строки.
Можно сначала сравнить хеши исходного слова и «перевернутого» к нему. Далее будем строить значения полиномиальных хешей, умноженных на $p$ в соответствующей степени, всех следующих подстрок длины $n$ и «перевернутых» к ним.
Заметим, что вычислять значение хеша «перевернутой» строки можно без её копирования, поскольку отличается она от «прямой строки только тем, что степени числа $p$ умножаются на преобразованые коды соответствующих символов строки в обратном порядке. Поэтому для вычисления хеша следующей «перевернутой» подстроки надо вычесть из предыдущего значения элемент с наибольшей степенью числа $p$, домножить полученное значение на $ p^2 $, т.к. мы, с одной стороны, решили смещать края подстроки, для которой мы проверяем на палиндром, умножая её хеш на соответствующую степень числа $p$, а с другой — текущая предпоследняя степень должна стать последней (из-за того, что рассматривается перевёрнутая подстрока и новый символ к ней присоединяется «в начало»).

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

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

#include <iostream>
#include <vector>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.length();
    s += s;
    int len = s.length();
    vector <int> d (len);
    int l = 0, r = -1;
    if (n % 2) {
        for (int i = 0; i < len; ++i) {
            d[i] = (i > r)? 1 : min(d[l + r - i], r - i + 1);
            while (i - d[i] >= 0 and i + d[i] < len and s[i - d[i]] == s[i + d[i]])
                d[i]++;
            if (i + d[i] - 1 > r) {
                r = i + d[i] - 1;
                l = i - d[i] + 1;
            }
            if (r - l + 1 >= n) {
                cout << "yes";
                return 0;
            }
        }
    }
    else {
        for (int i = 0; i < len; ++i) {
            d[i] = (i > r)? 0 : min(d[l + r - i + 1], r - i + 1);
            while (i - d[i] - 1 >= 0 and i + d[i] < len and s[i - d[i] - 1] == s[i + d[i]])
                d[i]++;
                if (i + d[i] - 1 > r) {
                    r = i + d[i] - 1;
                    l = i - d[i];
                }
            if (r - l >= n) {
                cout << "yes";
                return 0;
            }
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

string s;

cin >> s;

int n = s.length();

s += s;

int len = s.length();

vector <int> d (len);

int l = 0, r = -1;

if (n % 2) {

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

d[i] = (i > r)? 1 : min(d[l + r - i], r - i + 1);

while (i - d[i] >= 0 and i + d[i] < len and s[i - d[i]] == s[i + d[i]])

d[i]++;

if (i + d[i] - 1 > r) {

r = i + d[i] - 1;

l = i - d[i] + 1;

}

if (r - l + 1 >= n) {

cout << "yes";

return 0;

}

else {

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

d[i] = (i > r)? 0 : min(d[l + r - i + 1], r - i + 1);

while (i - d[i] - 1 >= 0 and i + d[i] < len and s[i - d[i] - 1] == s[i + d[i]])

d[i]++;

if (i + d[i] - 1 > r) {

r = i + d[i] - 1;

l = i - d[i];

}

if (r - l >= n) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №3

Для решения задачи можно воспользоваться алгоритмом Манакера. Алгоритм позволяет находить все подпалиндромы строки, поэтому мы снова продублируем строку и будем искать в ней подпалиндром, длина которого равна длине $n$ исходной строки. Заметим, что нам достаточно проверять подпалиндомы, четность длины которых совпадает с четностью $n$. Далее будем сравнивать расстояние между концами $l$ и $r$ текущего палиндрома с $n$ (расстояние между концами может быть и больше $n$, т.к. мы уже определили, что четность этих величин будет совпадать, а если в строке найден подпалиндром длиной $s$, то существуют подпалиндромы и длиной $s-2$, $s-4$, … ).

Решение №1 задачи на ideone.com

Решение №2 задачи на ideone.com

Решение №3 задачи на ideone.com

Ссылка на контест

Related Images:

e-olymp 3835. Минимальный каркас

13/07/2021 by Yezhkova

Задача

В связном графе найдите остовное дерево минимального веса.

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

Первая строка содержит два натуральных числа $n$ и $m$ $($$1 \leqslant n \leqslant 20000$, $0 \leqslant m \leqslant 100000$$)$ — количество вершин и рёбер графа соответственно. Следующие $m$ строк содержат описания рёбер по одному в строке. Ребро номер $i$ описывается тремя натуральными числами $b_i$, $e_i$ и $w_i$ $($$1 \leqslant b_i$, $e_i \leqslant n$, $0 \leqslant w_i \leqslant 100000$$)$ — номера концов ребра и его вес соответственно.

Граф является связным.

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

Выведите единственное целое число — вес минимального остовного дерева.

Тесты

Входные данные	Выходные данные
4 4 1 2 1 2 3 2 3 4 5 4 1 4	7
10 10 1 3 1 1 4 5 1 2 6 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 6 4 2 6 5 6	15
7 12 1 2 20 1 7 1 1 6 23 6 7 36 2 7 4 2 3 15 7 3 9 6 5 28 7 5 25 3 4 3 4 5 17 4 7 16	57

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

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

int get(const int &n, int *&subtree) {
    if (subtree[n] == n) return n;
    return subtree[n] = get(subtree[n], subtree);  
}

void merge(const int &a, const int &b, int *&subtree, int *&vertex_rank) {
    int ra = get(a, subtree), rb = get(b, subtree);
    if (vertex_rank[ra] < vertex_rank[rb]) subtree[ra] = rb;
    else if (vertex_rank[rb] < vertex_rank[ra]) subtree[rb] = ra;
    else {
        subtree[ra] = rb;
        vertex_rank[rb]++;
    }
}

int main()
{
    int vertices, edges;
    scanf("%i%i", &vertices, &edges);
    vector <pair<int, pair<int, int>>> v(edges);
    for (int i = 0; i < edges; ++i) {
        scanf("%i%i%i", &v[i].second.first, &v[i].second.second, &v[i].first); 
    }
    sort(v.begin(), v.end());
    int *subtree = new int[vertices];
    int *vertex_rank = new int[vertices];
    for (int i = 0; i < vertices; i++) {
        subtree[i] = i;
        vertex_rank[i] = 1;
    }
    int spanning_tree_weight = 0;
    for (int i = 0; i < edges; ++i) {
        if (get(v[i].second.first - 1, subtree) != get(v[i].second.second - 1, subtree)) {
            spanning_tree_weight += v[i].first;
            merge(v[i].second.first - 1, v[i].second.second - 1, subtree, vertex_rank);
        }
    }
    printf("%i", spanning_tree_weight);
    delete[] subtree;
    delete[] vertex_rank;
    return 0;
}

#include <stdio.h>

#include <vector>

#include <algorithm>

#include <utility>

using namespace std;

int get(const int &n, int *&subtree) {

if (subtree[n] == n) return n;

return subtree[n] = get(subtree[n], subtree);

}

void merge(const int &a, const int &b, int *&subtree, int *&vertex_rank) {

int ra = get(a, subtree), rb = get(b, subtree);

if (vertex_rank[ra] < vertex_rank[rb]) subtree[ra] = rb;

else if (vertex_rank[rb] < vertex_rank[ra]) subtree[rb] = ra;

else {

subtree[ra] = rb;

vertex_rank[rb]++;

}

int main()

{

int vertices, edges;

scanf("%i%i", &vertices, &edges);

vector <pair<int, pair<int, int>>> v(edges);

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

scanf("%i%i%i", &v[i].second.first, &v[i].second.second, &v[i].first);

}

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

int *subtree = new int[vertices];

int *vertex_rank = new int[vertices];

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

subtree[i] = i;

vertex_rank[i] = 1;

}

int spanning_tree_weight = 0;

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

if (get(v[i].second.first - 1, subtree) != get(v[i].second.second - 1, subtree)) {

spanning_tree_weight += v[i].first;

merge(v[i].second.first - 1, v[i].second.second - 1, subtree, vertex_rank);

}

printf("%i", spanning_tree_weight);

delete[] subtree;

delete[] vertex_rank;

return 0;

}

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

Алгоритм

Задача решается алгоритмом Краскала. Для хранения данных удобно использовать вектор пар (одна пара = одна строка ввода). Пары в свою очередь состоят из двух элементов: пара вершин и вес ребра. Алгоритм Краскала предполагает сортировку рёбер по весу в порядке неубывания. Затем каждой вершине графа ставится в соответствие собственное поддерево. Удобно это сделать с помощью массива, элементов массива будет столько же, сколько и вершин. Далее нужно пройтись по всем рёбрам в порядке неубывания и определить, принадлежат ли вершины ребра $i$ одному и тому же поддереву. Если вершины находятся в разных поддеревьях, то эти поддеревья объединяются, а вес данного ребра дописывается в ответ.

Оптимизация

При помощи простого массива или вектора задача выполняется со сложностью $O(M log N + N^2)$, где $N$ — количество вершин, $M$ — количество рёбер. Система непересекающихся множеств (СНМ) позволяет добиться сложности $O(M log N)$. При поиске элемента в СНМ необходимо лишь подниматься вверх по деревьям, поэтому достаточно хранить для каждой вершины только номер её прямого предка. Для этого используется массив $subtree$. Для задания множества используется номер вершины — корня соответствующего дерева. Поэтому чтобы определить, принадлежат ли два элемента к одному и тому же множеству, для каждого элемента нужно найти корень соответствующего дерева (поднимаясь вверх пока это возможно) и сравнить эти корни. При поиске корня заданной вершины будем переподвешивать её за найденный корень при выходе из рекурсивной функции $get$. Пусть нам нужно объединить $(merge)$ множества с корнями $a$ и $b$. Присвоим $p[a]=b$, тем самым подвесив всё дерево $a$ к корню дерева $b$. Одна из самых простых и эффективных оптимизаций — поддерживать для всех деревьев текущую глубину, и при объединении подвешивать дерево с меньшей глубиной к корню дерева с большей глубиной. Глубина дерева данной вершины хранится в виде её ранга (массив $vertex$_$rank$).

Ссылки

Related Images:

e-olymp 1821. Comparing Answers

23/06/2021 by Yezhkova

Problem

In a place in Southwestern Europe, the name of which I do not wish to recall, not long ago there were $n$ cities connected by unidirectional roads, with possibly more than one road connecting a city to another one, or even to itself. As a homework assignment for your geography class, you need to calculate the number of paths of length exactly two that were between each pair of cities. However, you’ve been too busy celebrating the Spanish victory in the World Cup, so now you are copying the answers from your friend. You would like to make sure his answers are correct before handing in your homework.

Input

The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer $n$ $(1 \leqslant n \leqslant 1000)$. The following $n$ lines contain $n$ elements each, with element $j$ of line $i$ being the number of roads from city $i$ to city $j$ (a number between $0$ and $10$, inclusive). After that, there will be $n$ lines. Each will contain $n$ elements, with element $j$ of line $i$ being the answer from your friend for the number of length-$2$ paths from city $i$ to city $j$; it will be an integer between $0$ and $100000$ inclusive.

The test cases will finish with a line containing only the number zero (also preceded by a blank line).

Note: Large input file; use fast I/O routines.

Output

For each case, your program should output a line. The content of this line should be «YES» if your classmate’s solution to the assignment is right, and «NO» otherwise.

Tests

№	Input	Output
1	3 2 0 1 1 0 3 1 1 0 5 1 2 5 3 1 3 0 43 2 0 1 1 0 3 1 1 0 5 1 2 5 3 2 3 0 40	YES NO
2	5 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 54 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1435 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 4 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1430	YES NO
3	1 2 21 2 40	NO YES
4	9 1 5 7 9 10 6 3 3 6 10 2 0 5 10 4 3 3 5 7 10 4 1 4 0 4 4 2 5 4 0 1 7 0 5 3 2 7 0 6 1 7 5 2 2 2 7 4 0 1 1 8 6 6 3 0 4 9 2 1 8 0 3 7 8 7 7 3 5 0 10 8 2 1 0 5 8 8 8 3 3 1 287 178 173 129 293 196 195 180 134 182 123 203 174 287 214 150 143 144 202 143 163 158 261 150 126 128 148 125 78 153 108 182 137 82 89 109 156 141 157 108 183 149 120 120 105 166 145 166 147 192 199 157 161 147 207 159 98 105 176 141 159 149 81 243 232 270 182 300 197 184 192 201 213 152 128 61 176 142 160 147 1000	YES

Code

#define _CRT_SECURE_NO_WARNINGS // preprocessor property for Visual Studio
#include <stdio.h>
using namespace std;

inline void array_input(int **&arr, int &n) { // input function to avoid code repetition; it is optional
    for (int i = 0; i < n; ++i) {
        arr[i] = new int[n];
        for (int j = 0; j < n; ++j) {
            scanf("%d", &arr[i][j]);
        }
    }
}

inline void array_delete(int **&arr, int &n) { // array deletion to prevent memory leaks
    for (int i = 0; i < n; ++i) {
        delete[]arr[i];
    }
    delete[]arr;
}

int main()
{
    int n; // processing 1 testcase at a time
    while (scanf("%d", &n) && n) { // testcases are processed until the delimiter 0 occurs
        int **number_of_roads = new int *[n]; // array to square
        array_input(number_of_roads, n);
        int **friend_answers = new int *[n]; // array to compare calculated values to
        array_input(friend_answers, n);
        int correct_answer; // the actual number of length-2 routes isn't stored
        bool is_correct = true; // flag to stop calculation when error detected
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n && is_correct; ++j) { // if an error is detected the is_correct flag stops the cycle, if no error is detected j reaches n
                correct_answer = 0;
                for (int k = 0; k < n; ++k) {
                    correct_answer += number_of_roads[i][k] * number_of_roads[k][j]; // a single element of squared matrix 
                }
                if (friend_answers[i][j] != correct_answer) {
                    is_correct = false; // set the flag to stop calculation
                }
            }
        }
        printf(is_correct ? "YES\n" : "NO\n"); // output
        array_delete(number_of_roads, n);
        array_delete(friend_answers, n);
    }
    return 0;
}

#define _CRT_SECURE_NO_WARNINGS // preprocessor property for Visual Studio

#include <stdio.h>

using namespace std;

inline void array_input(int **&arr, int &n) { // input function to avoid code repetition; it is optional

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

arr[i] = new int[n];

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

scanf("%d", &arr[i][j]);

}

inline void array_delete(int **&arr, int &n) { // array deletion to prevent memory leaks

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

delete[]arr[i];

}

delete[]arr;

}

int main()

{

int n; // processing 1 testcase at a time

while (scanf("%d", &n) && n) { // testcases are processed until the delimiter 0 occurs

int **number_of_roads = new int *[n]; // array to square

array_input(number_of_roads, n);

int **friend_answers = new int *[n]; // array to compare calculated values to

array_input(friend_answers, n);

int correct_answer; // the actual number of length-2 routes isn't stored

bool is_correct = true; // flag to stop calculation when error detected

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

for (int j = 0; j < n && is_correct; ++j) { // if an error is detected the is_correct flag stops the cycle, if no error is detected j reaches n

correct_answer = 0;

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

correct_answer += number_of_roads[i][k] * number_of_roads[k][j]; // a single element of squared matrix

}

if (friend_answers[i][j] != correct_answer) {

is_correct = false; // set the flag to stop calculation

}

printf(is_correct ? "YES\n" : "NO\n"); // output

array_delete(number_of_roads, n);

array_delete(friend_answers, n);

}

return 0;

}

Solution

The problem statement says that element $j$ of line $i$ of the matrix corresponds to the number of unidirectional roads from city $i$ to city $j$. Thus, we have an adjacency matrix of a directed unweighted graph. We need to find the number of paths of fixed length $k = 2$ for each pair of cities and compare them to our friend’s answer from the output. Adjacency matrix $g_{n \times n}$ of a directed unweighted graph contains the number of routes of length $k = 1$ between each pair of vertices. The solution is iterative: adjacency matrix $g$ corresponds to paths of length $k = 1$. Let $g = d_k$. For $k + 1$ we have: $d_{k+1}[i][j] = \sum\limits_{p=1}^n d_k[i][p] \cdot g[p][j]$, i.e. the product of matrices $d_k$ and $g$. Conclusion: to count the routes of fixed length we have to raise the adjacence matrix to the correspondent power.

Testcases are processed one at a time and after each the answer is given. Firstly, two 2D arrays of size $n \times n$ are initialized and entered: one for storing the matrix with the amounts of paths and the other with our friend’s answers. There is a warning about a big input file in the problem statement. Thus we use C style for I/O operations. Secondly, the first matrix is squared and the results are compared to the friend’s answers one by one. Once an error is detected the loop ends and the answer «NO» is displayed. Otherwise the loop reaches its end and «YES» is displayed. It is necessary that both arrays are deleted before processing the next testcase to prevent memory leaks.

Links&References

Related Images:

e-olymp 1619. Ограбление домов

23/06/2021 by Oleksandr.Ivanov

Задача

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

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

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

Первая строка содержит количество домов $n (1 \leqslant n \leqslant 10^6)$. Вторая строка содержит n целых неотрицательных чисел $a_1, a_2, …, a_n$, где $a_i$ — количество денег, которое может быть вынесено из iго дома.

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

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

Тесты

№	Входные данные	Выходные данные
1	5 6 1 2 10 4	16
2	10 4 1 29 0 14 8 31 12 7 5	85
3	2 1 3	3

Код

#include <iostream>
 
using namespace std;
 
void houseRobbery(int houseCount, unsigned long *maxSum, unsigned long *initialHouses) {
    /*
    A function that, through dynamic programming, calculates the maximum production of houses not standing nearby.
    The function does not return anything, since it modifies arrays through pointers
    */
    
    // Initial state values from first two houses
    maxSum[0] = initialHouses[0];
    maxSum[1] = max(initialHouses[0], initialHouses[1]);
 
    // Since by condition it is given that we cannot rob two houses in a row, 
    // then we will take the maximum house of two: maxSum[i - 1] and maxSum[i - 2] + initialHouses[house] 
    // (where initialHouses[house] is the amount of money in the i-th house)
    for (int house = 2; house < houseCount; house += 1) {
        maxSum[house] = max(maxSum[house - 1], maxSum[house - 2] + initialHouses[house]);
    }
}
 
int main() {
    int houseCount;
    cin >> houseCount;

    // Initialize the arrays not containing negative values
    unsigned long initialHouses[houseCount], maxSum[houseCount];
 
    // Filling the initial array of houses with user input
    for (int element = 0; element < houseCount; element += 1) {
        cin >> initialHouses[element];
    }
    
    // Calling the function
    houseRobbery(houseCount, maxSum, initialHouses);
 
    cout << maxSum[houseCount - 1];
    return 0;
}

#include <iostream>

using namespace std;

void houseRobbery(int houseCount, unsigned long *maxSum, unsigned long *initialHouses) {

A function that, through dynamic programming, calculates the maximum production of houses not standing nearby.

The function does not return anything, since it modifies arrays through pointers

// Initial state values from first two houses

maxSum[0] = initialHouses[0];

maxSum[1] = max(initialHouses[0], initialHouses[1]);

// Since by condition it is given that we cannot rob two houses in a row,

// then we will take the maximum house of two: maxSum[i - 1] and maxSum[i - 2] + initialHouses[house]

// (where initialHouses[house] is the amount of money in the i-th house)

for (int house = 2; house < houseCount; house += 1) {

maxSum[house] = max(maxSum[house - 1], maxSum[house - 2] + initialHouses[house]);

}

int main() {

int houseCount;

cin >> houseCount;

// Initialize the arrays not containing negative values

unsigned long initialHouses[houseCount], maxSum[houseCount];

// Filling the initial array of houses with user input

for (int element = 0; element < houseCount; element += 1) {

cin >> initialHouses[element];

}

// Calling the function

houseRobbery(houseCount, maxSum, initialHouses);

cout << maxSum[houseCount - 1];

return 0;

}

Решение

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

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

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

Зная, что такое динамическое программирование и МПВ — можно описать алгоритм решения.
Пусть $a_i$ — количество денег в $i$-ом доме и houseRobbery(i) — максимальное количество денег, которое удалось унести грабителю.

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

Далее в цикле рассматривается $i$-й дом и определять для него $houseRobbery(i)$, где houseRobbery(i) — максимальное из houseRobbery(i - 1) и houseRobbery(i - 2) + initialHouses[i], так как нужно учитывать houseRobbery(i - 1), если $i$-й дом не был ограблен, а houseRobbery(i - 2) + initialHouses[i], если $i$-й дом — ограблен.

И так как используется МПВ, то последний элемент в заведенном массиве и будет решением этой задачи.

Ссылки

Related Images:

e-olymp 6975. Магический Множитель

19/06/2021 by Tychenko

Задача

Ельфійські раси Середзем’я вважали, що деякі числа є більш важливими, ніж інші. При використанні конкретного кількості $n$ металу для виплавки меча, вони вважають, що меч буде найбільш потужним, якщо його товщина $k$ обрана відповідно до наступного правила:

Визнач невід’ємне ціле число $n$. Знайти найменше $k$, для якого десяткове представлення чисел в послідовності

$n, 2n, 3n, 4n, 5n,\ldots, kn$

містить всі десять цифр (від $0$ до $9$) як мінімум один раз?

Лорд Елронд з Рівенделл доручив Вам розробити алгоритм, який знайде оптимальну товщину $k$ для будь-якого заданого кількості металу $n$.

Вхідні дані

Кожен рядок містить одне число $n$ $(1 \leqslant n \leqslant 200000000)$.

Вихідні дані

Для кожного тесту вивести в окремому рядку необхідне значення $k$ — таке що кожна цифра від $0$ до $9$ зустрічається хоча б один раз.

Тести

№	Вхідні дані	Вихідні дані
1	1 10 123456789 3141592	10 9 3 5
2	200000000	45

№

Вхідні дані

Вихідні дані

123456789

3141592

200000000

Код

#include <iostream>
using namespace std;
bool Cheking(bool arr[]) {
  bool q = true;
  for (int i = 0; i < 10; i++) if (arr[i] == false) q = false;
  if (q == false) return true;
  else return false;
}
void Filling(bool arr[], long a) {
  int b;
  while (a > 0) {
    b = a % 10;
    arr[b] = (bool)1;
    a = (a - b) / 10;
  }
}
int main() {
  long n, k;
  bool arr[10];
  while (cin >> n) {
    k = 0;
    for (int i = 0; i < 10; i++) arr[i] = 0;
    while (Cheking(arr)) {
      k++;
      Filling(arr, k * n);
    }
    cout << k << '\n';
  }
}

#include <iostream>

using namespace std;

bool Cheking(bool arr[]) {

bool q = true;

for (int i = 0; i < 10; i++) if (arr[i] == false) q = false;

if (q == false) return true;

else return false;

}

void Filling(bool arr[], long a) {

int b;

while (a > 0) {

b = a % 10;

arr[b] = (bool)1;

a = (a - b) / 10;

}

int main() {

long n, k;

bool arr[10];

while (cin >> n) {

k = 0;

for (int i = 0; i < 10; i++) arr[i] = 0;

while (Cheking(arr)) {

k++;

Filling(arr, k * n);

}

cout << k << '\n';

}

Рішення

Для знаходження числа $k$ треба всі отриманні цифри (від $0$ до $9$), які зустрічаються в числовій послідовності $n, 2n, 3n, 4n, 5n,\ldots, kn$, відзначати як знайдені. Для цього було використано масив з $10$ елементів, де поіндексово (відповідно до цифри) відзначалася знайденна цифра, яка зустрічалося в числовій послідовності хоча б один раз. Пошук числа $k$ здійнувався за допомогою циклу, де методом поступового збільшення $k$, здійснювалася перевірка числа. Перевірка рахувалося успішною і завершувала цикл, якщо в масиві було відзначено всі цифри. В разі неуспішної перевірки цикл продовжувався.

Посилання

Задача на e-olymp.
Код рішення на Replit.
Код рішення на Ideone.

Related Images:

e-olymp 7258. Числовые операции

12/04/2021 by Філіпенко Микита

Условие

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

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

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

Первая строка входного файла содержит число $T (1 \leqslant T < 10^4),$ которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих $T$ строках задано по одному натуральному числу $N_i$,$2\leqslant N_i < 10^9$, $1 \leqslant i \leqslant T$. Известно, что среди чисел $N_i, 1 \leqslant i \leqslant T$, нет одинаковых.

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

Выходной файл должен содержать $T$ чисел по одному в строке — в $i$-й строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число $N_i$.

Тесты

№

Ввод

Вывод

955

4

137

318

3028

300

39

40

71

50

Код

#include <iostream>

using namespace std;

int nonzero(int number) //функция, которая считает количество цифр, не равных нулю, кроме последней
{
  int count = 0;
  number /= 10;
  while (number != 0) {
    if (number % 10 != 0) count++;
    number /= 10;
  }
  return count;
}
int summa(int number) //функция, которая возвращает сумму цифр числа
{
  int sum = 0;
  while (number != 0) {
    sum += number % 10;
    number /= 10;
  }
  return sum;
}
bool edinica(int number) //функция, которая проверяет есть ли среди цифр числа, кроме последней, единица
{
  number /= 10;
  bool ok = false;
  while (number != 0) {
    if (number % 10 == 1) ok = true;
    number /= 10;
  }
  return ok;
}
int kol_vo(int number) //функция, вычисляющая кол-во цифр числа
{
  int count = 0;
  while (number != 0) {
    count++;
    number /= 10;
  }
  return count;
}
int formula(int number) //формула, по которой можно дойти от 1 до 10^(a-1),где a- кол-во цифр числа
{
  int a = kol_vo(number);
  return (5 * a - 1) * (a - 1);
}

int main() {
  //инициализируем переменную t и считываем ее с клавиатуры
  int t;
  cin >> t;
  //инициализируем переменную ni и задаем цикл, который будет работать пока мы вводим значения ni и t>0
  int ni;
  while (cin >> ni and t > 0) {
    //кладем в переменную kol_vo1 значение функции kol_vo от значения ni
    int kol_vo1 = kol_vo(ni);
    //появляется необходимость создать переменную, которая будет равна значению ni,так как с этим значением
    //в дальнейшем будут проводится операции, а в конце программы нам нужно будет обратиться к исходному значению ni 
    int a = ni;
    //задаем массив, размерность которого равна кол-ву цифр числа
    int b[kol_vo1];
    for (int i = 0; i < kol_vo1; i++) {
      b[i] = a % 10;
      a /= 10;
    }
    //далее производим проверку условия №2,которое описано в решении. Если число проходит условие, то 
    //выводим соответствующую формулу, указанную в условии №2
    bool ok = false;
    for (int i = 0; i < kol_vo1 - 1; i++) {
      if (b[i] == 0) ok = true;
      else {
        ok = false;
        break;
      }
    }
    if (b[kol_vo1 - 1] > 1 and ok == true) {
      cout << summa(--ni) + nonzero(--ni) - edinica(--ni) + formula(ni) << endl;
    }
    //далее производим проверку условия №1,которое описано в решении. Если число проходит условие, то 
    //выводим соответствующую формулу, указанную в условии №1
    bool ok2 = false;
    for (int i = 0; i < kol_vo1 - 1; i++) {
      if (b[i] != 0) ok2 = true;
    }
    if (ok2 == true) cout << summa(ni) + nonzero(ni) - edinica(ni) - 1 + formula(ni) << endl;
    //остались крайние случаи, когда число однозначное или кратное 10^n.Проверяем число на эти условия
    //и если оно является таковым, выводим соответствующие значения
    if (kol_vo1 == 1) cout << ni - 1 << endl;
    if (ni == 10 or ni == 100 or ni == 1000 or ni == 10000 or ni == 100000 or ni == 1000000 or ni == 10000000 or ni == 100000000 or ni == 1000000000) cout << formula(ni) << endl;
    //декрементируем переменную t
    t--;
  }
}

#include <iostream>

using namespace std;

int nonzero(int number) //функция, которая считает количество цифр, не равных нулю, кроме последней

{

int count = 0;

number /= 10;

while (number != 0) {

if (number % 10 != 0) count++;

number /= 10;

}

return count;

}

int summa(int number) //функция, которая возвращает сумму цифр числа

{

int sum = 0;

while (number != 0) {

sum += number % 10;

number /= 10;

}

return sum;

}

bool edinica(int number) //функция, которая проверяет есть ли среди цифр числа, кроме последней, единица

{

number /= 10;

bool ok = false;

while (number != 0) {

if (number % 10 == 1) ok = true;

number /= 10;

}

return ok;

}

int kol_vo(int number) //функция, вычисляющая кол-во цифр числа

{

int count = 0;

while (number != 0) {

count++;

number /= 10;

}

return count;

}

int formula(int number) //формула, по которой можно дойти от 1 до 10^(a-1),где a- кол-во цифр числа

{

int a = kol_vo(number);

return (5 * a - 1) * (a - 1);

}

int main() {

//инициализируем переменную t и считываем ее с клавиатуры

int t;

cin >> t;

//инициализируем переменную ni и задаем цикл, который будет работать пока мы вводим значения ni и t>0

int ni;

while (cin >> ni and t > 0) {

//кладем в переменную kol_vo1 значение функции kol_vo от значения ni

int kol_vo1 = kol_vo(ni);

//появляется необходимость создать переменную, которая будет равна значению ni,так как с этим значением

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

int a = ni;

//задаем массив, размерность которого равна кол-ву цифр числа

int b[kol_vo1];

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

b[i] = a % 10;

a /= 10;

}

//далее производим проверку условия №2,которое описано в решении. Если число проходит условие, то

//выводим соответствующую формулу, указанную в условии №2

bool ok = false;

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

if (b[i] == 0) ok = true;

else {

ok = false;

break;

}

if (b[kol_vo1 - 1] > 1 and ok == true) {

cout << summa(--ni) + nonzero(--ni) - edinica(--ni) + formula(ni) << endl;

}

//далее производим проверку условия №1,которое описано в решении. Если число проходит условие, то

//выводим соответствующую формулу, указанную в условии №1

bool ok2 = false;

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

if (b[i] != 0) ok2 = true;

}

if (ok2 == true) cout << summa(ni) + nonzero(ni) - edinica(ni) - 1 + formula(ni) << endl;

//остались крайние случаи, когда число однозначное или кратное 10^n.Проверяем число на эти условия

//и если оно является таковым, выводим соответствующие значения

if (kol_vo1 == 1) cout << ni - 1 << endl;

if (ni == 10 or ni == 100 or ni == 1000 or ni == 10000 or ni == 100000 or ni == 1000000 or ni == 10000000 or ni == 100000000 or ni == 1000000000) cout << formula(ni) << endl;

//декрементируем переменную t

t--;

}

Решение

Количество цифр в числе никогда не уменьшается, а может увеличиться только при добавлении к числу, состоящее только из девяток и единицы. Поэтому, для достижения числа $N$ сначала нужно дойти до числа $10$, потом до чисел $99$ и $100$ и так далее, пока количество цифр в числе не будет таким, какое требуется.
Наименьшее количество операций, необходимое для того, чтобы перейти от числа $10^{n-1}$ до заданного $n$ -значного числа $N$ можно посчитать следующим образом:
1. Если число $N$ содержит хотя бы одну цифру, отличную от нуля, кроме первой, то количество операций можно посчитать по формуле summa(N) + nonzero(N) – edinica(N) - 1, где summa(N) — сумма цифр числа, nonzero(N) — количество цифр, отличных от нуля, на всех позициях числа $N$, кроме последней, edinica(N) — число, которое равно единице, если хотя бы на одной позиции числа $N$, кроме последней, есть единица, или равна нулю, если единиц на этих позициях нет.
2. Если все цифры числа $N$, кроме первой, нулевые, а первая цифра больше единицы, то количество операций можно посчитать по формуле summa(N-1)+nonzero(N-1) – edinica(N-1).

Доказательство формул

Для дальнейшего удобства обозначим перестановку цифр числа через $\Rightarrow$.
Число $N$ -заданное число, число $n$ -количество цифр числа $N$. Если $n=1$, $N=7$, то для того, чтобы дойти от единицы до заданного числа, потребуется $N-1$ операций. В нашем случае $6$ операций
($1+1=2,
2+1=3,
…
6+1=7$)
Если $n\geq2$, то для этого достаточно привести пример цепочки, подсчитывающая количество операций, которая число $10^{n-1}$ превращает в $N$. Но вместо прямого порядка действий будем делать обратный эквивалентный. $N \Rightarrow 10^{n-1}$. За одну операцию мы можем или уменьшить число на единицу, или переставить в нем цифры так, чтобы на первом месте оказался не нуль. Могут возникнуть следующие случаи:
1. Если $N=10^{n-1}$, то количество операций равно summa(N) + nonzero(N) - edinica(N) - 1 $= $ $0$.
Например, возьмем число $1000$. Сумма цифр $= 1$, количество ненулевых цифр $= 1$, количество единиц $= 1$, соответственно значение $= 1+1-1-1 =0$.

2. Если $N!=10^{n-1}$ и первая цифра числа $N$ равна единице, то проводим следующие операции:
Сначала отнимаем от числа $N$ столько единиц, чтобы последняя цифра стала нулем, далее переставим местами последнюю цифру с какой-нибудь другой, отличной от нуля, кроме первой, и опять отнимем количество единиц, чтобы последняя цифра стала нулевой. Повторять будем до тех пор, пока все цифры, кроме первой, не станут нулями.
Например, возьмем число $137$.
$137-1=136$, $136-1=135$, $135-1=134$, $134-1=133$ ,$133-1=132$ ,$132-1=131$, $131-1=130$ ,$130 \Rightarrow 103$ , $103-1=102$, $102-1=101$, $101-1=100$
Количество операций $= 11$. Проверяем по формуле. summa(137)=11, nonzero(137)=2, edinica(137)=1. Итого получаем $11+2-1-1=11$

3. Если первая цифра числа $N$ больше единицы, но хотя бы на одной позиции числа, кроме последней, есть единица, то проводим следующие операции:
Сначала уменьшаем последнюю цифру, пока она не станет нулем, затем переставляем цифры: поставим на место первой цифры единицу, а первую цифру сделаем последней, а нуль, который стоял в конце числа, поставим на место бывшей первой цифры. После этого будем действовать согласно алгоритму пункта №2.
Например, число $318$.
$318-1=317$, $317-1=316$, $316-1=315$, $315-1=314$, $314-1=313$, $313-1=312$, $312-1=311$, $311-1=310$, $310 \Rightarrow 103$, $103-1=102$, $102-1=101$, $101-1=100$
Итого $12$ операций. Просчитываем по формуле summa(318)+nonzero(318)-edinica(318)-1.
Получаем $12+2-1-1=12$.

4. Если ни на одной из позиций числа $N$, кроме, возможно, последней, нет единиц, но в числе есть хотя бы одна ненулевая цифра, кроме первой, то проводим следующие операции:
Последнюю цифру делаем нулевой, переставляем последний нуль с любой ненулевой цифрой, кроме первой, пока на последнем месте не окажется последняя ненулевая цифра (не считая первую), последнюю ненулевую уменьшаем не до нуля, а до единицы, переставим единицу с первой цифрой, новую последнюю цифру сделаем нулевой.
Например, число $3028$.
$3028-1=3027$, $3027-1=3026$, $3026-1=3025$, $3025-1=3024$, $3024-1=3023$, $3023-1=3022$, $3022-1=3021$, $3021-1=3020$, $3020 \Rightarrow 3002$, $3002-1=3001$, $3001 \Rightarrow 1003$, $1003-1=1002$, $1002-1=1001$, $1001-1=1000$
Получаем $14$ операций. Проверяем по формуле summa(3028)+nonzero(3028)-edinica(3028)-1 $= 13+2-0-1=14$.

5. Если первая цифра числа $N$ больше единицы, а все другие цифры — нулевые, то проводим следующие операции:
Отнимем от числа $N$ единицу, а дальше будем использовать один из раннее написанных алгоритмов в пунктах 2-4.
Например, число $300$.
$300-1=299$, $299-1=298$, $298-1=297$, $297-1=296$, $296-1=295$ $=$ … $291-1=290$, $290 \Rightarrow 209$, $209-1=208$ $=$ … $202-1=201$, $201 \Rightarrow 102$, $102-1=101$, $101-1=100$
Итого $22$ операции. summa(300-1)+nonzero(300-1)-edinica(300-1) $= 20+2-0=22$.

6. Подсчет операций от $1$ до $10^{n-1}$.
Для того, чтобы перейти от числа $10^{n-1}$ к $10^n$, понадобится число $10^n – 1$,которое равно $k$. По предыдущим алгоритмам, понадобится:
summa(k)+ nonzero(k) – edinica(k) - 1 $=$ $9 \cdot n + (n-1) -0 -1=10 \cdot n – 2$ операций, где $n > 1$.
Если $n=1$, то количество операций $= 10 \cdot n – 2 =8$.

Количество операций можно посчитать по формуле $(5 \cdot n -1) \cdot (n – 1)$ ,где $n$- количество цифр заданного числа.

Ссылки

Related Images:

e-olymp 7254. Отрезки

13/03/2021 by Євген Константинов

Задача

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

Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер [latex]i[/latex] характеризуется двумя числами — длиной [latex]L_i[/latex] и ценой [latex]C_i[/latex]. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.

Задание

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

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

В первой строке входного файла записано единственное число [latex]N[/latex] — количество отрезков. В следующих [latex]N[/latex] строках записана информация о самих отрезках. Каждая такая строка содержит соответствующие [latex]L_i[/latex] [latex](1 \leqslant L_i \leqslant 10^9)[/latex] и [latex]C_i[/latex]. Цены образуют перестановку чисел от [latex]1[/latex] до [latex]N[/latex], то есть являются попарно различными натуральными числами, не превосходящими [latex]N[/latex].

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

Выходной файл должен содержать единственное число — минимальную стоимость трех отрезков, из которых можно сложить треугольник, либо «-1» (кавычки для наглядности) в том случае, если выбрать ровно три таких отрезка невозможно.

Тесты

№	Входные данные	Выходные данные
1	4 1 1 2 2 3 3 4 4	9

Код

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

//Структура для представления одного отрезка
struct Line {
    int price;
    int length;
};

//Функция сортировщик по цене в порядке возрастания
bool comparator_price (Line i, Line j) { 
    return i.price < j.price;
}

int main() {
    int n, price, length, cheapest = INT_MAX;
    cin >> n;
    Line lines_by_price[n];
    
    for (int i = 0; i < n; i++) {
        Line l;
        cin >> length >> price;
        l.price = price;
        l.length = length;
        lines_by_price[i] = l;
    }
    
    //Сортируем все отрезки по цене, чтобы была возможность "отсечь"
    //слишком дорогие отрезки, когда цена одного(или двух) будет 
    //больше текущей минимальной
    sort(&lines_by_price[0], &lines_by_price[n], comparator_price);
    
    for (int i = 0; i < n; i++) {
        Line first_side = lines_by_price[i];
        if (first_side.price > cheapest) break;
        vector<Line> sides = {};
        //Перебираем все возможные тройки отрезков, отсекая
        //слишком дорогие, основываясь на сортировке по цене
        //и текущей минимальной цене
        for (int j = 0; j < n; j++) {
            if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {
                sides.push_back(lines_by_price[j]);
                Line second_side = lines_by_price[j];
                if (first_side.price + second_side.price > cheapest) break;
                for (auto third_side: sides) {
                    if ((third_side.length != second_side.length && third_side.price != second_side.price) 
                    && first_side.length < second_side.length + third_side.length 
                    && second_side.length < first_side.length + third_side.length 
                    && third_side.length < second_side.length + first_side.length) {
                        if (first_side.price + second_side.price + third_side.price < cheapest) {
                            cheapest = first_side.price + second_side.price + third_side.price;
                        }
                        break;
                    }
                }
            }
        }
    }
    //Если ни одна тройка отрезков не подошла, значит составить
    //треугольник невозможно - выводим "-1"
    if (cheapest == INT_MAX) cheapest = -1;
    cout << cheapest;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <climits>

using namespace std;

//Структура для представления одного отрезка

struct Line {

int price;

int length;

};

//Функция сортировщик по цене в порядке возрастания

bool comparator_price (Line i, Line j) {

return i.price < j.price;

}

int main() {

int n, price, length, cheapest = INT_MAX;

cin >> n;

Line lines_by_price[n];

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

Line l;

cin >> length >> price;

l.price = price;

l.length = length;

lines_by_price[i] = l;

}

//Сортируем все отрезки по цене, чтобы была возможность "отсечь"

//слишком дорогие отрезки, когда цена одного(или двух) будет

//больше текущей минимальной

sort(&lines_by_price[0], &lines_by_price[n], comparator_price);

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

Line first_side = lines_by_price[i];

if (first_side.price > cheapest) break;

vector<Line> sides = {};

//Перебираем все возможные тройки отрезков, отсекая

//слишком дорогие, основываясь на сортировке по цене

//и текущей минимальной цене

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

if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {

sides.push_back(lines_by_price[j]);

Line second_side = lines_by_price[j];

if (first_side.price + second_side.price > cheapest) break;

for (auto third_side: sides) {

if ((third_side.length != second_side.length && third_side.price != second_side.price)

&& first_side.length < second_side.length + third_side.length

&& second_side.length < first_side.length + third_side.length

&& third_side.length < second_side.length + first_side.length) {

if (first_side.price + second_side.price + third_side.price < cheapest) {

cheapest = first_side.price + second_side.price + third_side.price;

}

break;

}

//Если ни одна тройка отрезков не подошла, значит составить

//треугольник невозможно - выводим "-1"

if (cheapest == INT_MAX) cheapest = -1;

cout << cheapest;

return 0;

}

Решение

Для начала запишем все отрезки в массив в виде структур. Отсортируем их по цене в порядке возрастания, чтобы позже иметь возможность «отсекать» слишком дорогие отрезки. Далее мы начинаем перебирать все возможные тройки отрезков. На первом уровне цикла ставим условный оператор. Если на [latex]n[/latex]-ой итерации цикла будет отрезок с ценой больше текущей наименьшей цены треугольника, то мы можем выходить из массива и выводить текущую минимальную стоимость, т.к. все последующие отрезки будут дороже (пользуемся сортировкой и тем, что цены отрезков образуют перестановку от [latex]1[/latex] до [latex]N[/latex]). Далее на втором и третьем уровнях цикла мы также перебираем все отрезки от дешевых к дорогим и при обнаружении тройки отрезков, цена которых меньше текущей минимальной, записываем их в переменную [latex]cheapest[/latex]. При этом на втором уровне цикла проверяем, не больше ли сумма цен двух отрезков текущей минимальной, чтобы не проверять лишние тройки.

Ссылки

Related Images:

e-olymp 7824. Без повторений

22/12/2020 by Максим Алексеев

Задача

В натуральном числе $A$ удалили некоторые цифры так, чтобы получить наибольшее натуральное число $B$ с разными цифрами. Какое это число?

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

Натуральное число $x \ (1 \leqslant x \leqslant 10^{100})$.

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

Натуральное число $B$.

Тесты

№	Входные данные	Выходные данные
1	575747	754
2	123231	321
3	314159265359	4192653
4	1092010	9210
5	112221332	213

Код

#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    string current_number;
    string ansver = "";
    cin >> current_number;
    set<char> digits_set;    // Инициализируем и заполняем множество со всеми цифрами начального числа
    for (int i = 0; i < current_number.size(); i++){
        char element = current_number[i];
        digits_set.insert(element);
    }
    std::vector<char> digits;
    for (char i : digits_set){
        digits.push_back(i);
    }
    std::reverse(digits.begin(), digits.end());    // Располагаем цифры в порядке убывания
    while (digits.size() != 1){    // Повторяем, пока не нашли все цифры кроме последней
        for (int i=0; i < digits.size(); i++){    // Перебираем цифры в порядке убывания
            char local_max = digits[i];
            int position = current_number.find(local_max);
            string new_number;
            for (int j = position; j < current_number.size(); j++){    // Делаем срез по элементу
                new_number += current_number[j];
            }
            set<char> digits_on_the_right;
            for (int j = 0; j < new_number.size(); j++){    // Находим цифры нового числа
                digits_on_the_right.insert(new_number[j]);
            }
            if (digits.size() == digits_on_the_right.size()){    // Проверяем, сохранится ли ранг ответа
                ansver += local_max;
                digits.erase(digits.begin() + i);
                string number_without_digit = "";
                for (int t = 0; t < new_number.size(); t++){    // Удаляем добавленную в ответ цифру из числа
                    if (new_number[t] != local_max){
                        number_without_digit += new_number[t];
                    }
                }
                current_number = number_without_digit;
                break;    // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена
            }
        }
    }
    cout << ansver + digits[0];    // Добавляем к ответу последнюю оставшуюся цифру
    return 0;
}

#include <iostream>

#include <cstring>

#include <set>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

string current_number;

string ansver = "";

cin >> current_number;

set<char> digits_set; // Инициализируем и заполняем множество со всеми цифрами начального числа

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

char element = current_number[i];

digits_set.insert(element);

}

std::vector<char> digits;

for (char i : digits_set){

digits.push_back(i);

}

std::reverse(digits.begin(), digits.end()); // Располагаем цифры в порядке убывания

while (digits.size() != 1){ // Повторяем, пока не нашли все цифры кроме последней

for (int i=0; i < digits.size(); i++){ // Перебираем цифры в порядке убывания

char local_max = digits[i];

int position = current_number.find(local_max);

string new_number;

for (int j = position; j < current_number.size(); j++){ // Делаем срез по элементу

new_number += current_number[j];

}

set<char> digits_on_the_right;

for (int j = 0; j < new_number.size(); j++){ // Находим цифры нового числа

digits_on_the_right.insert(new_number[j]);

}

if (digits.size() == digits_on_the_right.size()){ // Проверяем, сохранится ли ранг ответа

ansver += local_max;

digits.erase(digits.begin() + i);

string number_without_digit = "";

for (int t = 0; t < new_number.size(); t++){ // Удаляем добавленную в ответ цифру из числа

if (new_number[t] != local_max){

number_without_digit += new_number[t];

}

current_number = number_without_digit;

break; // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена

}

cout << ansver + digits[0]; // Добавляем к ответу последнюю оставшуюся цифру

return 0;

}

Нажмите здесь, чтобы выполнить этот код.

Решение

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

Рассмотрим пример: для числа $121323$ правильным ответом будет $213$.

Ход рассуждений следующий: поскольку в числе содержатся три цифры, ответ также будет трехзначным. Наибольшая цифра в числе — 3, следовательно, она должна быть первой цифрой ответа. Для выполнения этого условия придется «вычеркнуть» все предыдущие цифры, но тогда мы сможем получить лишь двухзначное число $32$. Следующим кандидатом является двойка, и этот выбор нас полностью устраивает, поскольку справа от нее есть остальные цифры «входного» числа. Записав в ответ $2$, рассмотрим число за ней: $1323$. Мы можем видеть, что двойка повторяется, однако в ответе ее быть уже не может по условию задачи. Отбросим ее за ненадобностью и рассмотрим получившееся число $133$. Для полученного числа нам необходимо выполнить те же операции, что и для предыдущего, а значит, мы столкнулись с задачей на динамическое программирование (о чем нам, правда, уже заботливо сообщил e-olymp прямо под условием). Рассуждения аналогичны: взять $3$ мы не можем, поскольку это вынудит нас отбросить $1$, что в результате даст нам число $23$, то есть даже меньшее, чем то, что мы получали в начале. Следовательно, добавляем к ответу $1$. Последнюю оставшуюся цифру можно сразу добавлять к ответу, поскольку сравнивать ее не с чем. Получаем искомый ответ — $213$.

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

Ссылки

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

Related Images:

e-olymp 1602. НОК двух натуральных чисел

22/12/2020 by Федяєва Євгенія

Задача

Найдите $НОК$ (наименьшее общее кратное) двух натуральных чисел.

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

Два натуральных числа $a$ и $b$ $(a, b < 2 \cdot 10^9)$.

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

Вывести $НОК$ чисел $a$ и $b$.

Тесты

№	Входные данные	Выходные данные
1	42 24	168
2	32 14	224
3	101 45	4545

Код

#include <iostream>
using namespace std;
 
long int GCD(int num1, int num2) 
{
    if(num1 == num2) return num1;
    while(num1 && num2)
    {
        if(num1 > num2) num1 %= num2;
        else num2 %= num1;
    }
    return num1+num2;
}
 
int main() {
    long int num1, num2, gcd;
    cin >> num1 >> num2;
    gcd = GCD(num1, num2);
    cout << num1*num2/gcd;
    return 0;
}

#include <iostream>

using namespace std;

long int GCD(int num1, int num2)

{

if(num1 == num2) return num1;

while(num1 && num2)

{

if(num1 > num2) num1 %= num2;

else num2 %= num1;

}

return num1+num2;

}

int main() {

long int num1, num2, gcd;

cin >> num1 >> num2;

gcd = GCD(num1, num2);

cout << num1*num2/gcd;

return 0;

}

Решение

Пусть есть два числа $n_1$ и $n_2$. $НОК$($n_1$, $n_2$) можно вычислить по формуле $НОК(n_1, n_2)={{n_1\cdot n_2}\over{НОД(n_1, n_2)}}$. Тогда задача сводится к нахождению $НОД$ двух чисел, который вычисляется алгоритмом Евклида:
$1$. Большее число делится на меньшее.
$2$. Если остаток от деления равен нулю, то меньшее число и есть $НОД$.
$3$. Если есть остаток, то большее число заменяется на остаток от деления и все действия повторяются.
После завершения цикла в одной переменной содержится ноль, а другая равна $НОД$, но поскольку неизвестно, которая из переменных равна $НОД$, то возвращается их сумма.

Ссылки

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

Related Images:

e-olymp 7095. Факторіали

13/12/2020 by Федяєва Євгенія

Задача

Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.

Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$. Наприклад:

при $N$ = $7$ кодом буде $504$, бо $7!$ = $5040$;
при $N$ = $17$ кодом буде $096$, бо $17!$ = $355687428096000$.

За даним натуральним числом $N$ знайти три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$.

Вхідні дані

Вхідний файл містить єдине ціле число $N$. $(7 \leqslant N \leqslant 1000000000)$.

Вихідні дані

Вихідний файл має містити рівно три цифри — шуканий код.

Тесты

№	Входные данные	Выходные данные
1	7	504
2	17	096
3	50	512
4	1000000000	144

Код

#include <iostream>

#define COEF 10000000
#define TEN 10

using namespace std;

unsigned int arr[] = { 1, 94194688,80754176,28792576,93638144,44194688,16269824,94550272,61946112,68933632,
                       68754176,19323648,22612992,36351232,57997312,66792576,2167808,95748096,88043776,
                       37690112,65638144,99247872,80831232,42968832,38960896,2194688,36401664,29433088,
                       21091328,35679232,40269824,3200512,39416576,62174976,23727104,49750272,52626176,
                       72337664,68916224,93513984,25146112,14722816,60257024,2170112,13989632,28933632,
                       91983872,29619968,23259904,52859904,2354176,61171456,14485248,81225984,93129472,
                       98123648,42294528,83940096,91339008,90945024,77812992,83786752,30308352,33122816,
                       709376,45551232,13495552,4053504,28486912,65094912,93197312,79194112,80894208,
                       48729344,89670656,26832576,59147776,51826688,14217984,72698112,10487808,29000448,
                       21455616,72560128,94383616,23588096,83462144,14917632,85698816,11810304,3083776,
                       84299264,11034368,6525952,27101696,68170112,92235008,45980416,15386112,44244224,
                       3398144 };
int main()
{
    int N;
    unsigned long long factorial = 1;
    cin >> N;
    int idx = N/COEF;
    factorial = arr[idx];
    int start = !N%COEF ? idx*COEF : idx*COEF + 1;
    if (N % COEF != 0)
    {
        for(int i = start; i <= N; i++)
        {
            factorial *= i;
            while(factorial % TEN == 0) factorial /= TEN;
            factorial %= COEF;
        }
    }
    factorial %= TEN*TEN*TEN;
    cout << factorial/(TEN*TEN) << (factorial/TEN)%TEN << factorial%TEN;
    return  0;
}

#include <iostream>

#define COEF 10000000

#define TEN 10

using namespace std;

unsigned int arr[] = { 1, 94194688,80754176,28792576,93638144,44194688,16269824,94550272,61946112,68933632,

68754176,19323648,22612992,36351232,57997312,66792576,2167808,95748096,88043776,

37690112,65638144,99247872,80831232,42968832,38960896,2194688,36401664,29433088,

21091328,35679232,40269824,3200512,39416576,62174976,23727104,49750272,52626176,

72337664,68916224,93513984,25146112,14722816,60257024,2170112,13989632,28933632,

91983872,29619968,23259904,52859904,2354176,61171456,14485248,81225984,93129472,

98123648,42294528,83940096,91339008,90945024,77812992,83786752,30308352,33122816,

709376,45551232,13495552,4053504,28486912,65094912,93197312,79194112,80894208,

48729344,89670656,26832576,59147776,51826688,14217984,72698112,10487808,29000448,

21455616,72560128,94383616,23588096,83462144,14917632,85698816,11810304,3083776,

84299264,11034368,6525952,27101696,68170112,92235008,45980416,15386112,44244224,

3398144 };

int main()

{

int N;

unsigned long long factorial = 1;

cin >> N;

int idx = N/COEF;

factorial = arr[idx];

int start = !N%COEF ? idx*COEF : idx*COEF + 1;

if (N % COEF != 0)

{

for(int i = start; i <= N; i++)

{

factorial *= i;

while(factorial % TEN == 0) factorial /= TEN;

factorial %= COEF;

}

factorial %= TEN*TEN*TEN;

cout << factorial/(TEN*TEN) << (factorial/TEN)%TEN << factorial%TEN;

return 0;

}

Решение

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

#include <iostream>
#define TEN 10
using namespace std;
int main()
{
    int N = 1000000000, count = 1;
    unsigned long long factorial = 1;
    for(int i = 1; i <= N; i++)
    {
        factorial *= i;
        while(factorial%TEN == 0) factorial /= TEN;
        factorial %= 100000000;
        if (i % 10000000 == 0) {cout << factorial << ","; count++;}
        if (count == TEN) {cout << endl; count = 1;}
    }
    return  0;
}

#include <iostream>

#define TEN 10

using namespace std;

int main()

{

int N = 1000000000, count = 1;

unsigned long long factorial = 1;

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

{

factorial *= i;

while(factorial%TEN == 0) factorial /= TEN;

factorial %= 100000000;

if (i % 10000000 == 0) {cout << factorial << ","; count++;}

if (count == TEN) {cout << endl; count = 1;}

}

return 0;

}

Если на входе — число $N$, меньшее $10000000$, его факториал рассчитывается обычным циклом, попутно отбрасывая ненужные цифры высших разрядов. В конце выводятся искомые последние три цифры факториала числа $N$. Если на входе — число $N$, большее $10000000$, выбирается соответствующее значение из массива по индексу $N/10000000$, и далее с помощью цикла считается произведение оставшихся чисел из $N!$. С уменьшением кратности чисел, факториалы которых содержатся в массиве, увеличивается скорость выполнения программы.

Ссылки

Код на 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-olymp 8946. Шаблон

28/05/2020 by Алина Зозуля

Условие

По заданному натуральному числу $n$ вывести изображение размером $n\times n$, образованное символами звездочка и пробел как показано в примере.

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

Одно натуральное число $n$.

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

Вывести изображение $n \times n$.

Тесты

№

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

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

* 
 *

* *

 *

* *

* *

* *

 * *

* *

* *

* * *

 * *

* * *

 * *

* * *

* * *

* *

* * *

* *

* * *

* * *

 * * *

* * *

 * * *

* * *

 * * *

* * *

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

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

int main() {
    long long n;
    string s1 = "", s2 = "";
    cin >> n;
    for (int i = 0; i < n; i++){//заполняем строки 
        if (i % 2 == 0){
            s1 += "*";
            s2 += " ";
        }
        else {
            s2 += "*";
            s1 += " ";
        }
    }
    for (int i = 0; i < n; i++){
        if (i % 2 == 0){//выводим s1, если строка имеет четный номер
            cout << s1 << endl;
        }
        else cout << s2 << endl;//выводим s2, если строка имеет нечетный номер
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

long long n;

string s1 = "", s2 = "";

cin >> n;

for (int i = 0; i < n; i++){//заполняем строки

if (i % 2 == 0){

s1 += "*";

s2 += " ";

}

else {

s2 += "*";

s1 += " ";

}

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

if (i % 2 == 0){//выводим s1, если строка имеет четный номер

cout << s1 << endl;

}

else cout << s2 << endl;//выводим s2, если строка имеет нечетный номер

}

return 0;

}

Решение

Для того, чтобы вывести изображение как на рисунке достаточно заметить, что выводятся строки только двух видов и то поочерёдно. Первый вид — первым символом строки является $\ast$ и затем чередуется $\ast$ и пробел. Второй вид — первым символом строки является пробелом и затем чередуется $\ast$ и пробел. Мы заполняем две строки, по одной каждого вида. Нам остается только выводить строку необходимого нам вида, сделаем это в цикле.

Ссылки

Условие задачи на e-olymp

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

Related Images:

e-olimp 9536. Сумма матриц

16/05/2020 by Елизавета Савицкая

Задача

Заданы две матрицы $A$ и $B$. Найдите их сумму $C$ = $A$ + $B$.

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

Первая строка содержит размеры матриц $n$ и $m$ $(1 \leqslant n, m \leqslant 100)$. Следующие $n$ строк содержат по $m$ целых чисел и описывают матрицу $A$. Далее следует пустая строка, после чего в таком же формате задается матрица $B$.

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

Выведите матрицу $С$: $n$ строк по $m$ целых чисел.

Тесты

Входные данные	Выходные данные
1 1 2 3	5
1 5 4 3 7 2 1 3 2 2 1 6	7 5 9 3 7
2 2 0 4 2 3 5 4 1 6	5 8 3 9
3 4 3 4 5 6 1 2 3 4 7 6 5 4 0 0 -3 -2 -1 3 4 5 5 6 1 2	3 4 2 4 0 5 7 9 12 12 6 6
3 3 2 -128 47 -365 5 56 243 42 12 678 43 76 4 345 -23 97 -453 18	680 -85 123 -361 350 33 340 -411 30

Код

#include <iostream>
using namespace std;

int main() {
   int n, m;
   cin >> n >> m;
   int matrix1[n][m];
   int matrix2[n][m];
   int matrix_sum[n][m] = {0};
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         cin >> matrix1[i][j];
      }
   }
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         cin >> matrix2[i][j];
      }
   }
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         matrix_sum[i][j] = matrix1[i][j] + matrix2[i][j];
         cout << matrix_sum[i][j] << " ";
      }
      cout << endl;
   }
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

int matrix1[n][m];

int matrix2[n][m];

int matrix_sum[n][m] = {0};

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

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

cin >> matrix1[i][j];

}

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

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

cin >> matrix2[i][j];

}

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

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

matrix_sum[i][j] = matrix1[i][j] + matrix2[i][j];

cout << matrix_sum[i][j] << " ";

}

cout << endl;

}

return 0;

}

Решение

Чтобы найти сумму двух матриц, необходимо сложить их соответствующие элементы.

Ссылки

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

Related Images:

e-olymp 9066. Кружок стрельбы

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

Задача

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

На занятие кружка пришли $n$ учеников. Фэй пронумеровала их целыми числами от $1$ до $n$. В начале занятия ученики встали вдоль координатной прямой, заблаговременно нарисованной на полу, причем i-й ученик стоял в точке с координатой $x_i$. Получилось так, что координаты учеников строго возрастали, то есть $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

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

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

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

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

Первая строка содержит количество учеников $n$ $(1 \leqslant n \leqslant 1000)$ на кружке Фэй.

Каждая из следуюших $n$ строк содержит три целых числа $x_i$, $r_i$ и $c_i$ ($1 \leqslant x_i \leqslant 10^9$, $1 \leqslant r_i$, $c_i \leqslant 100$) — координату очередного ученика, а также дальность и силу его лука соответственно. Гарантируется, что $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

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

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 1 3 3 5 1 2 8 2 3 10 1 2 11 3 2	2
2	6 1 3 5 4 2 2 7 4 3 10 1 2 11 3 2 13 4 3	1

Код

#include <iostream>
using namespace std;
struct archerProfile {
  unsigned long x;
  unsigned long r;
  unsigned int c;
}archer[1000];
int main(){ 
  int n;
  int commands = 1;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> archer[i].x >> archer[i].r >> archer[i].c;
  }
  for (int i = 0; i < n - 1; i++) {
    unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;
    if (distanceBetweenArchers > archer[i].c * archer[i].r) {
      commands += 1;
    }
  }
  cout << commands;
  return 0;
}

#include <iostream>

using namespace std;

struct archerProfile {

unsigned long x;

unsigned long r;

unsigned int c;

}archer[1000];

int main(){

int n;

int commands = 1;

cin >> n;

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

cin >> archer[i].x >> archer[i].r >> archer[i].c;

}

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

unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;

if (distanceBetweenArchers > archer[i].c * archer[i].r) {

commands += 1;

}

cout << commands;

return 0;

}

Решение

Для решения задачи, мы должны найти расстояние между лучниками, то есть $x_{i+1}-x_i$, после чего найти максимальное расстояние, которое пролетит стрела у $x_{i}$ лучника умножив силу его лука $c_i$ и расстояние $r_i$, после чего сделать проверку, если расстояние между лучниками больше чем максимальное расстояние которое пролетит стрела, то мы дадим команду совершить ещё один выстрел.

Ссылки

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

Related Images:

e-olymp 8956. Вывести массив 4

25/02/2020 by Кирилл Колесник

Задача

Задан массив из [latex]n[/latex] целых чисел. Выведите только его отрицательные элементы, изменив первоначальный порядок на противоположный.

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

Первая строка содержит число [latex]n (1 \leqslant n \leqslant 100)[/latex]. Во второй строке записаны [latex]n[/latex] целых чисел, каждое из которых не превышает по модулю [latex]100[/latex].

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

В первой строке выведите количество отрицательных элементов массива. Во второй строке выведите сами отрицательные элементы в обратном порядке. Если отрицательных элементов в массиве нет, то выведите [latex]«NO»[/latex].

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	7 -2 5 4 -3 7 -1 0	3 -1 -3 -2
2	5 2 1 0 1 5	NO
3	3 -1 -2 -3	3 -3 -2 -1

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

#include <iostream>
using namespace std;

int main() {
    int n, count = 0;
    cin >> n; 
    int arr[n];
    for (int i = 0; i < n; i++){
        cin >> arr[i];
        if (arr[i] < 0){
            count++;
        }
    }
    if(count == 0){
        cout << "NO";
    } else {
        cout << count << endl;
        for (int c = n - 1; c >= 0; c--){
            if (arr[c] < 0){
                cout << arr[c] << " "; 
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, count = 0;

cin >> n;

int arr[n];

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

cin >> arr[i];

if (arr[i] < 0){

count++;

}

if(count == 0){

cout << "NO";

} else {

cout << count << endl;

for (int c = n - 1; c >= 0; c--){

if (arr[c] < 0){

cout << arr[c] << " ";

}

return 0;

}

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

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

С помощью цикла for задаем массив, начиная с нулевого элемента и заканчивая [latex]n[/latex]-ым элементом (не включительно!). Внутри цикла размещаем условный оператор if, который прибавляет единицу к переменной count каждый раз, когда элемент массива отрицателен. После окончания цикла важно не забыть о еще одном условном операторе, который будет выводить [latex]«NO»[/latex] и заканчивать работу программы, если значение [latex]count[/latex] равно нулю (то есть именно в том случае, если в массиве не будет ни одного отрицательного элемента). Но если в массиве всё же есть отрицательные элементы, то программа должна продолжить работу, что мы и предусматриваем, выполняя все остальные операции в рамках оператора else. Отлично! Теперь полученное значение переменной [latex]count[/latex] (если оно больше нуля) можно вывести, однако это еще не конец, ведь также необходимо вывести все отрицательные элементы в обратном порядке, так что переходим на новую строку с помощью endl и продолжаем.

Реализация подобной процедуры не так сложна, как кажется. Для этого необходимо создать еще один цикл for, перебирающий массив с конца (то есть от [latex]n-1[/latex] до [latex]0[/latex] включительно). Внутри цикла вновь создаем условный оператор if, который каждый раз выводит элемент массива (с пробелом), если он оказывается отрицательным. Не забываем закрыть скобку оператора else, ведь эта процедура также выполняется внутри условного оператора.

Готово!

Related Images:

e-olymp 8963. Наименьшие влево

19/01/2020 by Даниил Кадочников

Условие

Задан массив из [latex]n[/latex] целых чисел. Переместить все минимальные элементы в начало массива, не меняя порядок других.

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

В первой строке записано натуральное число [latex]n[/latex]. В следующей строке записаны [latex]n[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].

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

Выведите элементы обновленного массива.

Тесты

№	Ввод	Вывод
1	7 6 -3 -7 4 -7 -4 5	-7 -7 6 -3 4 -4 5
2	2 100 -100	-100 100
3	6 -2 -2 7 3 99 -2	-2 -2 -2 7 3 99
4	5 1 1 1 1 1	1 1 1 1 1

Решение

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

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

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

int main()
{
    int n;
    cin >> n;
    vector <int> v, v2;
    int x;
    while(cin>>x) v.push_back(x);
    int min = v[0];
    for(int q=1; q<n; q++) {
        if(v[q]<min) min = v[q];
    }

    int min_counter = 0;
    for(int w=0; w<n; w++) {
        if(v[w] == min) min_counter++;
    }

    for(int e=0; e<min_counter; e++) v2.push_back(min);
    for(int r=0; r<n; r++) {
        if(v[r]!=min) v2.push_back(v[r]);
    }
    for(int t=0; t<n; t++) cout << v2[t] << " ";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int n;

cin >> n;

vector <int> v, v2;

int x;

while(cin>>x) v.push_back(x);

int min = v[0];

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

if(v[q]<min) min = v[q];

}

int min_counter = 0;

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

if(v[w] == min) min_counter++;

}

for(int e=0; e<min_counter; e++) v2.push_back(min);

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

if(v[r]!=min) v2.push_back(v[r]);

}

for(int t=0; t<n; t++) cout << v2[t] << " ";

return 0;

}

Ссылки

решение на E-olymp
код на ideone

Related Images:

e-olymp 8666. Коровий котильон

18/01/2020 by Нина Хоробрых

Задача

В коровьем котильоне — причудливом танце весны — участвуют коровы (обозначаются $ «\gt»$) и быки (обозначаются $ «\lt»$), они кланяются друг другу во время танца. Схематически обозначим пару кланяющихся животных следующим образом: $ «\gt \lt»$. Иногда вторая пара скота может находиться между кланяющейся парой: $ «\gt \gt \lt \lt»$.

Иногда и большее количество коров и быков встречается на танцевальной площадке: $ «\gt \gt \lt \lt \gt \lt»$ (имеется вторая пара кланяющихся коров справа). Сложные аранжировки могут быть совершенно легальными танцевальными образованиями:

Фермер Джон замечает, что бездомная корова иногда пробирается в группу и разбалансирует ее: $ «\gt \gt \lt \lt \lt \lt»$. Это строго запрещено; Фермер Джон хочет наказать нарушителей.

Фермер Джон скопировал данные о том, как $500$ коров участвуют в танцевальной линии, и задался вопросом, правильно ли уравновешена танцевальная линия (то есть весь скот может быть спарен как минимум одним способом чтобы правильно кланяться друг другу). Он скопировал только направление, в котором кланялась каждая корова, без каких-либо лишних пробелов, чтобы можно было определить, какая корова какому быку кланяется. Строки похожи на пример из предыдущего абзаца: «>><&lt». Фермер Джон хочет чтобы Вы написали программу, определяющую правильность танцевальной линии.

Фермер Джон имеет $n$ записей танца $P_{i}$ состоящих из символов $ «\gt»$ и $ «\lt»$;’ различной длины $K_{i} (1 \leqslant K_{i} \leqslant 200)$. Выведите «legal» для тех строк, которые содержат правильные пары кланяющихся коров и «illegal» иначе.

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

Первая строка содержит одно число $n$ $(1 \leqslant n \leqslant 1000)$. Каждая из следующих $n$ строк содержит число и строку из $K$ символов $ «\gt»$ и $ «\lt»$: $K_{i}$и $P_{i}$.

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

Выведите в каждой строке «legal» или «illegal» в зависимости от того, содержит ли соответствующая входная строка допустимую конфигурацию.

Тесты

№	Входные данные	Выходные данные
1	2 6 >><<>< 4 ><<>	legal illegal
2	3 8 <>><><>< 6 ><>><< 9 >><>><<><	illegal legal illegal
3	5 4 ><>< 10 >>><<>><<< 8 >><<<>>< 3 >>< 12 ><>><>>><<<<	legal legal illegal illegal legal

Код

#include <iostream>
using namespace std;

int main() {
  int n, q, count;
  char ungulate;
  bool b;
  cin >> n;
 
  for ( int i = 0; i < n; i++ ) {
    int count = 0;
    b = true;
    cin >> q;
   
    for ( int j = 0; j < q; j++ ) {
      cin >> ungulate;
      if ( ungulate == '>' ) {
        count++;
      }
      else {
        count--;
      }
      if ( count < 0 ) {
        b = false;
      }
    }
    
    if ( count != 0 ) {
        b = false;
    }
    
    if ( b ) {
        cout << "legal" << endl; 
      } 
    else {
        cout << "illegal" << endl;
      }
  }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, q, count;

char ungulate;

bool b;

cin >> n;

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

int count = 0;

b = true;

cin >> q;

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

cin >> ungulate;

if ( ungulate == '>' ) {

count++;

}

else {

count--;

}

if ( count < 0 ) {

b = false;

}

if ( count != 0 ) {

b = false;

}

if ( b ) {

cout << "legal" << endl;

}

else {

cout << "illegal" << endl;

}

return 0;

}

Решение

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

Ссылки

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

Related Images:

e-olimp 7848. Переставить соседние

14/01/2020 by Елизавета Савицкая

Задача

Задан массив из $n$ целых чисел. Переставьте соседние элементы массива ($a_{0}$ с $a_{1}$, $a_{2}$ с $a_{3}$ и так далее). Если элементов нечетное количество, то последний элемент следует оставить на своем месте.

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

В первой строке записано число $n$. В следующей строке записано $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Вывести обновленный массив.

Тесты

Входные данные	Выходные данные
7 3 5 -7 7 5 -9 -4	5 3 7 -7 -9 5 -4
8 -9 81 27 -38 2 6 -56 -21	81 -9 -38 27 6 2 -21 -56
2 25 -76	-76 25
3 55 44 33	44 55 33
1 99	99

Код

#include <iostream>
using namespace std;

int main() {
   int n;
   cin >> n;
   int arr[n];
   for(int i = 0; i < n; i++){
      cin >> arr[i];
   } 
   for(int i = 1; i < n; i+=2){
      int q = arr[i];
      arr[i] = arr[i-1];
      arr[i-1] = q;
   }
   for(int i = 0; i < n; i++){
      cout << arr[i] << " ";
   }
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int arr[n];

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

cin >> arr[i];

}

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

int q = arr[i];

arr[i] = arr[i-1];

arr[i-1] = q;

}

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

cout << arr[i] << " ";

}

return 0;

}

Решение

Будем переставлять соседние элементы массива следующим образом: arr[1] с arr[0], arr[3] с arr[2] и так далее до конца массива (т.е. каждый нечетный по счету элемент меняем местами с предыдущим). При этом совершенно неважно, четное кол-во элементов или нечетное.

Ссылки

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

Related Images:

e-olymp 7847. Кількість різних елементів

12/01/2020 by Андрей Мартынюк

Задача

Дано масив з [latex]N[/latex] цілих чисел. Визначте, скільки в цьому масиві різних елементів.

Вхідні дані

В першому рядку записано число [latex]N[/latex]. В наступному рядку записано [latex]N[/latex] цілих чисел. Всі числа за модулем не перевищують [latex]100[/latex].

Вихідні дані

Кількість різних елементів в масиві.

Тести

№	Вхідні дані	Вихідні дані
1.	7 3 5 -7 7 5 -9 -4	6
2.	5 1 25 59 75 100	5
3.	6 1 2 3 1 2 4	4

Код 1

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int diffNum = 0;
    for (int i = 0; i < n; i++)
    {
        bool newNum = true;
        for (int j = 0; j < i; j++)
        {
            if (a[j] == a[i])
            {
                newNum = false;
                break;
            }
        }
        if (newNum == true)
        {
            diffNum++;
        }
    }
    cout << diffNum;
    
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* a = new int[n];

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

{

cin >> a[i];

}

int diffNum = 0;

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

{

bool newNum = true;

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

{

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

{

newNum = false;

break;

}

if (newNum == true)

{

diffNum++;

}

cout << diffNum;

return 0;

}

Код 1(without break)

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++) { cin >> a[i];
    }
    int diffNum = 0;
    for (int i = 0; i < n; i++)
    {
        bool newNum = true;
        for (int j = 0; j < i && a[i-1] != a[j]; j++)
        {
            if (a[j] == a[i])
            {
                newNum = false;
            }
        }
        if (newNum == true)
        {
            diffNum++;
        }
    }
    cout << diffNum;
    
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* a = new int[n];

for (int i = 0; i < n; i++) { cin >> a[i];

}

int diffNum = 0;

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

{

bool newNum = true;

for (int j = 0; j < i && a[i-1] != a[j]; j++)

{

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

{

newNum = false;

}

if (newNum == true)

{

diffNum++;

}

cout << diffNum;

return 0;

}

Решение

Ставим отметку числу как будто видим его впервые.
Далее задача пройти по всем предыдущим числам и проверить не встретится ли такое же число.
Если встретится, то отметку снимаем, а пройдя по всем предыдущим числам так и не встретив числа равного текущему, значит «видим его впервые» и отметка поставлена справедливо.
Считаем количество отметок.

Ссылки

Код 2

#include <iostream>
using namespace std;
#include 
int main() {
    vector a(202, false);
    int n, diffNum, curVal;
    cin >> n;
    diffNum = n;
    for(int i = 0; i < n; i++)
    {
        cin >> curVal;
        if(a[curVal + 100]) 
        {
            diffNum--;
        }
        else 
        {
            a[curVal + 100] = true;
        }
    }
    cout << diffNum << endl;
    return 0;
}

#include <iostream>

using namespace std;

#include

int main() {

vector a(202, false);

int n, diffNum, curVal;

cin >> n;

diffNum = n;

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

{

cin >> curVal;

if(a[curVal + 100])

{

diffNum--;

}

else

{

a[curVal + 100] = true;

}

cout << diffNum << endl;

return 0;

}

Решение

Сначала, предположим, что все числа разные. Т.е. количество различных чисел равно [latex]n.[/latex] Далее в цикле for отметим читаем числа из потока и отмечаем в векторе vector<bool> a, что число встретилось. Встретив число ранее уже отмеченное уменьшаем счетчик различных чисел.

Ссылки

Related Images:

e-olymp 2098. Переворачиватель

30/12/2019 by Даниил Кадочников

Условие

Заданы [latex]n[/latex] чисел. Выведите их в обратном порядке.

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

Сначала задано число [latex]n[/latex] ([latex]0 \lt n \lt 100[/latex]), за ним идут [latex]n[/latex] целых чисел.

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

Выведите заданные [latex]n[/latex] чисел в обратном порядке.

Тесты

№	Ввод	Вывод
1	7 2 4 1 3 5 3 1	1 3 5 3 1 4 2
2	1 5	5
3	10 1 1 1 9999 5 -1 7 3 0 9	9 0 3 7 -1 5 9999 1 1 1

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i=0; i<n; i++) cin >> arr[i];
    for(int u=n-1; u>-1; u--) cout << arr[u] << " ";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int arr[n];

for(int i=0; i<n; i++) cin >> arr[i];

for(int u=n-1; u>-1; u--) cout << arr[u] << " ";

return 0;

}

Решение

Введём переменную [latex]n[/latex], затем создадим массив из [latex]n[/latex] элементов. С помощью цикла for от [latex]0[/latex] до [latex]n[/latex] запишем в него числа. Теперь с помощью другого цикла от [latex]n-1[/latex] до [latex]-1[/latex] выводим их в обратном порядке.