OCPC2021. Задача F. Электрик наносит ответный удар (код решения)

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

Условие

В заведении «Покосившийся Скворечник» главврач экономит на зарплате системного администратора, поэтому эту должность в свободное от уколов время занимает электрик Геннадий из палаты номер 404. На сегодняшнем дежурстве одна из розеток внезапно заговорила с Геннадием и посулила тому суперспособности, если он её раскрутит. Результатом их общения, однако, стал лишь удар тока по нерадивому электрику, и теперь Геннадий задумал месть: он устроит лживой розетке Очень Длинное Замыкание!

Дата-центр «Покосившегося Скворечника» устроен следующим образом: помимо разной аппаратуры, из стены в ряд торчат 2∙n коннекторов: это n штепселей и n розеток. Геннадий планирует разбить их на пары розетка-штепсель и соединить каждую пару одним проводом таким образом, что штепсель всегда находится левее соответствующей розетки – эту идею ему навеяли правила средневекового этикета. Чтобы замыкание было Очень Длинным, Геннадий хочет, чтобы суммарная длина проводов, использованных для его коварного замысла, была максимально возможной. Помогите ему! Ну, или не мешайте хотя бы, и просто подскажите, провод какой длины он должен отрезать от соседней линии электропередач, чтобы распилить его на столь нужные ему провода.

Первая строка ввода содержит целое число $n$ $(2 \leqslant n \leqslant 1000).$ Вторая строка содержит n целых чисел – координаты штепселей слева направо. Третья строка содержит n чисел – координаты розеток слева направо. Все числа во второй и третьей строках различны и находятся в диапазоне от $0$ до $10^5$.

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

Тесты

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

2 1 4 6 8	9
2 1 4 2 5	2
4 2 5 6 9 3 7 12 22	22
3 2 3 4 12 13 17	33

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

#include <iostream>
using namespace std;
int main() {
    int n, res = 0;
    cin >> n;
    for (int tmp, i = 0; i < n; i++) {
        cin >> tmp;
        res -= tmp;
    }
    for (int tmp, i = 0; i < n; i++) {
        cin >> tmp;
        res += tmp;
    }
    cout << res;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, res = 0;

cin >> n;

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

cin >> tmp;

res -= tmp;

}

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

cin >> tmp;

res += tmp;

}

cout << res;

return 0;

}

Решение

Обратим внимание на то, что оптимальным будет решение подключать $i$-й штепсель к $i$-й розетке. В условии задачи сказано, что существует хотя бы один способ подключить все коннекторы так, чтобы соблюсти средневековое правило этикета. Значит, последовательно подключая самый левый свободный штепсель в самую левую свободную розетку (а поскольку коннекторы изначально упорядочены, это и значит $i$-й штепсель в $i$-й розетку), мы удовлетворим правило этикета. Теперь покажем, что суммарная длина проводов в любом другом подключении не меньше. Предположим, мы подключили $i$-й штепсель в $j$-ю розетку (и это первый случай подключения штепселя не на «свое» место). Поскольку все предыдущие розетки, если они есть, уже заняты, $j \gt i$. Если можно подключить $j$-й штепсель в $i$-ю розетку (т.е. $j$-й штепсель левее $i$-й розетки), то суммарная длина проводов не изменится. Если же $j$-й штепсель правее $i$-й розетки, то чтобы иметь возможность его подключить, надо переподключить штепсели между $i$-м и $j$-м (надо заметить, что такая возможность не гарантирована). В результате этого мы сэкономим провода на не более, чем расстояние между $i$-й розеткой и $j$-м штепселем. Но поскольку $k$-я розетка, в которую мы подключим $j$-й штепсель, обязательно правее самого штепселя, то суммарная длина проводов нового подключения будет больше исходной как минимум на расстояние между $k$-й розеткой и $j$-м штепселем, поскольку этот фрагмент провода «дублируется» подключением $i$-го штепселя в $j$-ю розетку.

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

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

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

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 7843. Больше предыдущего

27/06/2020 by Андрей Мартынюк

Задача

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

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

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

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

Выведите элементы массива, которые больше предыдущих.

Тесты

№	Входные данные	Выходные данные
1.	7 14 16 3 7 17 19 9	16 7 17 19
2.	5 3 5 2 4 1	5 4

Код

#include <iostream>
using namespace std;

int main() {
    int n, a, b;
    cin >> n;
    cin >> a;
    for(int i = 0; i < n; i++) {
       cin >> b;
       if(b > a) {
          cout << b << " ";
       }
       a = b;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a, b;

cin >> n;

cin >> a;

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

cin >> b;

if(b > a) {

cout << b << " ";

}

a = b;

}

return 0;

}

Решение

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

Ссылки

Related Images:

e-olymp 1462. Хитрая сортировка

26/02/2020 by Николай Жирко

Задача

Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих чисел.

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

Первая строка содержит число [latex] n [/latex] ([latex] 1 \leqslant n \leqslant 100 [/latex]), а вторая — сами натуральные числа, не превышающие [latex] 32000 [/latex].

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

Выведите последовательность чисел, упорядоченную согласно условию.

Тесты

№	Входные данные	Выходные данные
1	7 12 15 43 13 20 1 15	20 1 12 13 43 15 15
2	10 82 22 19 90 34 17 588 921 200 121	90 200 121 921 22 82 34 17 588 19
3	4 162 9801 37 14	9801 162 14 37

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

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

bool comp (const int& a, const int& b) {
    if (a % 10 == b % 10) return (a < b);
    else return a % 10 < b % 10;
}

int main() {
    int n, a;
    vector<int> array;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        array.push_back(a);
    }
    
    sort (array.begin(), array.end(), comp);
    
    for (int a = 0; a < n; a++) {
        cout << array[a] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool comp (const int& a, const int& b) {

if (a % 10 == b % 10) return (a < b);

else return a % 10 < b % 10;

}

int main() {

int n, a;

vector<int> array;

cin >> n;

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

cin >> a;

array.push_back(a);

}

sort (array.begin(), array.end(), comp);

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

cout << array[a] << " ";

}

return 0;

}

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

Для решения этой задачи необходимо объявить вектор, который будет хранить все числа, введенные пользователем, например, array.
Сортировку будем проводить с помощью функции sort. Для правильного упорядочивания чисел, напишем функцию компаратор comp, для сравнения чисел и решения, стоит ли их менять местами.
В конце выводим вектор array.

Ссылки

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

Решение на e-olymp

Решение на ideone.com

Related Images:

e-olymp 8851. Число навпаки

15/02/2020 by Нина Хоробрых

Умова задачі

Записати чотиризначне натуральне число в зворотному порядку.

Вхідні дані

Задане чотиризначне натуральне число.

Вихідні дані

Відповідь до задачі.

Тести

№	Входные данные	Выходные данные
1	1234	4321
2	1984	4891

Розвязок №1

#include <iostream>
using namespace std;

int main() {
    int num, a, b, c, d;
    cin >> num;
    a = num % 10;
    b = num / 10 % 10;
    c = num / 100 % 10;
    d = num / 1000;
    cout << a << b << c << d;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int num, a, b, c, d;

cin >> num;

a = num % 10;

b = num / 10 % 10;

c = num / 100 % 10;

d = num / 1000;

cout << a << b << c << d;

return 0;

}

Для отримання потрібного числа, відділимо кожну цифру та привласнемо до неї змінну. Виводимо у потрібному порядку.

Розвязок №2

#include <iostream>
using namespace std;
 
int main() {
    string num;
    cin >> num;
    for (int i = 3; i >= 0; i-- )  {
        cout << num[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string num;

cin >> num;

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

cout << num[i];

}

return 0;

}

Представимо вводиме число як строку. Виводимо у циклі від третього до останньго елемента.

Посилання

Задача на e-olymp
Зарахований розв’язок №1
Зарахований розв’язок №2
Код на ideone №1
Код на ideone №2

Related Images:

e-olymp 4020. Культ-орки на лестнице

10/02/2020 by Мария Жаркая

Задача

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

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

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

В первой строке вводятся два числа $n$ и $k$ $(1 \leqslant n \leqslant 10000, 0 \leqslant k \leqslant 20)$, $n$ — количество ступенек на лестнице, $k$ — максимальное количество ступенек, через которые Коля может перепрыгнуть за один прыжок (то есть, например, на первом шаге Коля может прыгнуть на $(k + 1)$-ую или более низкие ступеньки). Во второй строке вводятся $n$ чисел: $i$-ое число указывает на длительность в минутах того мероприятия, которое проведёт культ-орк, стоящий на $i$-ой ступеньке. Каждое мероприятие не может длиться более $24$ часов. Ступеньки нумеруются снизу вверх, ступенькой номер $n$ считается весь этаж столовой.

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

Выведите одно число — минимальное количество минут, которое Коле придётся распланировать.

Тесты

№	Входные данные	Выходные данные
1	5 2 7 3 9 2 11	14
2	6 1 59 32 4 21 5 1	42
3	10 3 40 55 85 29 158 105 115 281 320 10	144
4	15 4 67 20 85 12 345 9 234 115 190 47 5 17 23 89 130	156
5	4 0 100 20 31 49	200

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

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int stairs[n + 1]; int time[n + 1]; // массивы для времени каждого мероприятия и потраченного времени;
    for(int i = 1; i < n + 1; ++i) {
        cin >> stairs[i]; 
        if (i <= k + 1) time[i] = stairs[i];
    }
    time[0] = 0; 
    for(int i = 2; i <= n; ++i) {
        if (i > k + 1) time[i] = time[i - 1] + stairs[i]; // начальный минимум;
        for(int j = 2; j <= k+1; ++j) {
            if (i - j >= 0) time[i] =  min(time[i - j] + stairs[i], time[i]); // выбор минимально затраченного времени;
        }
    }
    cout << time[n];
}

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

int stairs[n + 1]; int time[n + 1]; // массивы для времени каждого мероприятия и потраченного времени;

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

cin >> stairs[i];

if (i <= k + 1) time[i] = stairs[i];

}

time[0] = 0;

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

if (i > k + 1) time[i] = time[i - 1] + stairs[i]; // начальный минимум;

for(int j = 2; j <= k+1; ++j) {

if (i - j >= 0) time[i] = min(time[i - j] + stairs[i], time[i]); // выбор минимально затраченного времени;

}

cout << time[n];

}

Решение

Для каждой ступеньки будем считать минимальное время, которое она отнимет у эльфа, учитывая сколько ступенек можно пропустить (от $0$ до $k + 1$). То есть будем прыгать со ступенек пониже (если это возможно) и сравнивать значения на каждой. Под значением подразумевается сумма уже найденного значения на более низкой ступеньке и времени, которое отнимет мероприятие $i$-ой ступеньки. Таким образом мы узнаем, какие ступеньки выгодно перепрыгнуть. $0$-я ступенька займет $0$ минут, так как эльф не потратит время. Изначально за минимум на ступеньках до $k + 1$ включительно можно взять время мероприятия соответствующей ступеньки, для остальных — сумму значения предыдущей ступеньки и времени мероприятия данной ступеньки. В случае, если эти значения не минимальные, они заменятся на подходящие.
Ответом будет значение на последней ступеньке, так как к ней будет проложен путь, который «займет» минимум времени эльфа на развлечения.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

Related Images:

e-olymp 123. Количество нулей у факториала

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

Задача

Найти количество нулей в конце записи факториала числа $n$.

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

Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$

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

Количество нулей в конце записи $n!$

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	0
2	7	1
3	12	2
4	100	24
5	306	75
6	5000	1249

Код

#include <iostream> 
using namespace std;
int main() { 
    long long n, m = 5, s = 0; 
    cin >> n; 
    while(n >= m){
        s = s + (n / m); 
        m = m * 5;
    }
    cout << s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, m = 5, s = 0;

cin >> n;

while(n >= m){

s = s + (n / m);

m = m * 5;

}

cout << s;

return 0;

}

Решение

Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:

$\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$

Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.

Ссылки

Формула разложения на простые множители

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

Код на Ideone

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

Related Images:

e-olymp 8916. Первые парные

14/01/2020 by Николай Жирко

Первые парные

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

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

Натуральное число [latex] n [/latex].

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

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

Тесты

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

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n + 1; i++) { 
        cout << i * 2 << " "; 
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

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

cout << i * 2 << " ";

}

return 0;

}

Решение

Решением этой задачи является вывод через пробел удвоенных чисел от 1 до [latex] n [/latex].

Ссылки

Условие на e-olymp
Решение на e-olymp
Решение на ideone.com

Related Images:

e-olymp 7841. Нечетные элементы

21/12/2019 by Алексей Богач

Условие

Задана последовательность из $n$ целых чисел. Выведите все ее нечетные элементы.

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

Первая строка содержит число $n$. Следующая строка содержит $n$ ($n$ $⩽$ $100$) целых чисел, которые по модулю не превосходят $100$.

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

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

Тесты

№	Входные данные	Выходные данные
1	7 14 17 16 3 7 19 9	17 3 7 19 9
2	5 2 4 3 11 5	3 11 5

Код

#include <iostream>
using namespace std;

int main() {
    int n, a;
    cin >> n;
    for (int i = 0; i < n; ++i) { 
        cin >> a;
        if (a % 2) cout << a << " ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a;

cin >> n;

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

cin >> a;

if (a % 2) cout << a << " ";

}

return 0;

}

Решение

Для решения задачи, проверим каждое число последовательности на четность.

Ссылки

Задача на e-olymp
Код программы на Ideone

Related Images:

e-olymp 8680. Чётные соседи

20/12/2019 by Алина Малыхина

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

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

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

В первой строке задано количество элементов последовательности $n$ $(n \leqslant 100)$. Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100$.

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

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

Тесты

№	Входные данные	Выходные данные
1	6 1 2 3 4 5 6	2
2	9 3 6 3 5 2 9 1 2 5	0
3	3 2 1 2	1
4	6 13 24 54 66 44 77	2
5	4 100 224 666 222	2

Программный код

#include <iostream>
using namespace std;

int main(){
    int i=1, n, prev, pres, fut, count = 0;
    cin >> n;
    cin >> prev; //вводим предыдущий элемент
    cin >> pres; //вводим текущий элемент
    while ((cin >> fut) && (i<n)) {
        if (prev % 2 == 0 && fut % 2 == 0) 
            count++;
        prev = pres; //приравниваем предыдущий к текущему
        pres = fut; //приравниваем текущий к будущему
        i++;
    }
    cout << count;
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int i=1, n, prev, pres, fut, count = 0;

cin >> n;

cin >> prev; //вводим предыдущий элемент

cin >> pres; //вводим текущий элемент

while ((cin >> fut) && (i<n)) {

if (prev % 2 == 0 && fut % 2 == 0)

count++;

prev = pres; //приравниваем предыдущий к текущему

pres = fut; //приравниваем текущий к будущему

i++;

}

cout << count;

return 0;

}

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

Задача на e-olymp
Код программы на Ideone
Засчитанное решение

Related Images:

e-olymp 8544. Квадраты чисел

19/12/2019 by Кирилл Избаш

Задача

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

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

Одно натуральное число [latex]n[/latex] [latex](n \leqslant 10^9)[/latex]

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

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

Тесты

Входные данные	Выходные данные
1	1
16	1 4 9 16
93	1 4 9 16 25 36 49 64 81
100	1 4 9 16 25 36 49 64 81 100

Код

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

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

for(int i = 1; i * i <= n; i++) cout << i * i << ' ';

return 0;

}

Решение

Воспользуемся циклом, в котором заведем переменную [latex]i[/latex] и будем перечислять числа [latex]1, 4, 9, …, i^2[/latex], пока [latex]i^2[/latex] не будет больше [latex]n[/latex]. Выводим последовательно квадраты натуральных чисел в одной строке.

Ссылки

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

Related Images:

e-olymp 8283. Музыка

14/12/2019 by Евгений Радчин

Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

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

Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

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

Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

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

Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

Тесты

№	Входные данные	Выходные данные
1	11 3	5
2	6 2	0
3	13 13	3
4	9 8	0
5	5 5	5

Код

#include <iostream>  
using namespace std;

int main() {
    int quantity, instrument, counter = 1;
    cin >> quantity >> instrument;
    if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {
        cout << 0;
    } else if (quantity == instrument) {
        for (int num = 1; num % quantity != 0; num += 6) {
            if (num != 1 && num % quantity == 1) {
                cout << 0;
                return 0;
            } else {
                counter++;
            }   
        }
        cout << counter;
    } else {
        for (int num = 1; num % quantity != instrument; num += 6) {
            if (num != 1 && num % quantity == 1) {
                cout << 0;
                return 0;
            } else {
                counter++;
            }   
        }
        cout << counter;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int quantity, instrument, counter = 1;

cin >> quantity >> instrument;

if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {

cout << 0;

} else if (quantity == instrument) {

for (int num = 1; num % quantity != 0; num += 6) {

if (num != 1 && num % quantity == 1) {

cout << 0;

return 0;

} else {

counter++;

}

cout << counter;

} else {

for (int num = 1; num % quantity != instrument; num += 6) {

if (num != 1 && num % quantity == 1) {

cout << 0;

return 0;

} else {

counter++;

}

cout << counter;

}

return 0;

}

Решение

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

Если пользователь вводит разные числа.
Если пользователь вводит одинаковые числа.

В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

Related Images:

e-olymp 5041. Синтаксический анализ вещественных чисел

14/12/2019 by Илья Балицкий

Задача

Напишите программу, которая считывает строку и проверяет, содержит ли она действительное число. Действительное число может содержать десятичную точку или показатель степени (начинающийся с $ e $ или $ E $), или и то и то одновременно. Также число может содержать обыкновенный набор десятичных цифр. Если число содержит десятичную точку, то должна присутствовать хотя бы одна цифра с каждой стороны точки. Перед числом или экспонентой может находиться плюс или минус (или одновременно и там и там) (без пробелов после знака). Экспонентой является целое число (не содержит десятичной запятой). Пробелы могут присутствовать до или после числа, но не внутри него. Обратите внимание, что границ диапазона входных чисел не существует, но для простоты будем предполагать, что входные строки содержат не более $ 1000 $ символов.

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

Первая строка содержит количество тестов $ t $. Дальше следует $ t $ строк, каждая из которых содержит одно число.

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

Вывести $ t $ строк, каждая из которых содержит слово $ LEGAL $ или $ ILLEGAL $.

Тесты

№	Входные данные	Выходные данные
1.	2 1.5e+2 3.	LEGAL ILLEGAL
2.	4 752.45e+24 0.762e. -0.355.6432e	LEGAL ILLEGAL ILLEGAL
3.	1 -652.32e+45	LEGAL
4.	3 542.512e+3 123.456E+42 123.456.789	LEGAL LEGAL ILLEGAL

Код

#include <iostream>
using namespace std;
 
bool isdigit(char x) { // проверка, является ли символ числом
    return (x >= '0' && x <= '9'? 1: 0);
}
 
bool isreal(char* x) { // сама функция синтаксического анализа
    if ((!isdigit(*x))||(*x == '+' || *x == '-' && !isdigit(*++x))) return 0;
    while (isdigit(*x)) ++x; // счетчик сдвигает указатель до символа, отличного от числа
    if (*x == '.' && !isdigit(*++x)) return 0;
    while (isdigit(*x))++x;
    if ((*x == 'e' || *x == 'E')&&((*++x == '+' || *x == '-')&&(!isdigit(*++x)))) return 0;
    while (isdigit(*x)) ++x;
    return *x == 0; // закончилось ли число
}
 
int main() {
    char x[1001];
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) { // сама проверка
        cin >> x; // ввод игнорирует пробелы, которые по условию могут быть до и после числа
        cout << (isreal(x) ? "LEGAL" : "ILLEGAL") << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

bool isdigit(char x) { // проверка, является ли символ числом

return (x >= '0' && x <= '9'? 1: 0);

}

bool isreal(char* x) { // сама функция синтаксического анализа

if ((!isdigit(*x))||(*x == '+' || *x == '-' && !isdigit(*++x))) return 0;

while (isdigit(*x)) ++x; // счетчик сдвигает указатель до символа, отличного от числа

if (*x == '.' && !isdigit(*++x)) return 0;

while (isdigit(*x))++x;

if ((*x == 'e' || *x == 'E')&&((*++x == '+' || *x == '-')&&(!isdigit(*++x)))) return 0;

while (isdigit(*x)) ++x;

return *x == 0; // закончилось ли число

}

int main() {

char x[1001];

int n;

cin >> n;

for (int i = 0;i < n;i++) { // сама проверка

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

cout << (isreal(x) ? "LEGAL" : "ILLEGAL") << "\n";

}

return 0;

}

Решение

Для решения задачи нам понадобится функция idigit() проверки того, является ли символ цифрой. В STL существует одноименная функция, которая выполняет ту же самую задачу, однако для практики, я написал свою. В функции анализа вещественных чисел isreal() нужно указать условия, при которых синтаксис будет нарушен. Т.е. не будут выполнены условия, описанные в задаче. Затем, если в символьном массиве не было замечено ошибок — возвратить trueв основную функцию. Важно то, что в числе не должно по условию быть других символов кроме «e», «E», «.», «+», «-» и цифр. Что касается окаймляющих пробелов, то при вводе строки через cin они игнорируются.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

Related Images:

e-olymp 566. Письмо почтальона Печкина

05/12/2019 by Артем Рогулин

Задача

Дорогие ребята!
Наблюдая за тем, как Шарик распиливал нестандартную шахматную доску, я также решил задать для вас задачку: “А сколько разных квадратных и прямоугольных (не считая квадратных) досок мог бы получить при распиливании Шарик из найденной им нестандартной прямоугольной шахматной доски размером $M\times N$?”

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

В первой строке количество заданий Печкина $K$, в последующих $K$ строках по два целых числа $M$ и $N$ $(1 \leqslant K, M, N \leqslant 100)$, разделённых пробелом.

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

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

Тесты

№	Входные данные	Выходные данные
1.	1 3 2	8 10
2.	2 4 4 2 2	30 70 5 4
3.	4 3 3 25 46 100 100 1 1	14 22 12350 338975 338350 25164150 1 0

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

#include <iostream>
using namespace std;

int main() {
    int k; // Количество заданий
    cin >> k;
    for(int l = 0; l < k; l++)
    {
        int m, n; // Размер шахматной доски
        cin >> m >> n;
        int res = 0; // Количество кусков, на которые мы можем разделить доску
        for(int i = min(m, n); i >= 0; i--) // Находим количество квадратов
        {
            res += (m - i) * (n - i);
        }
        cout << res; // Вывод количества квадратных досок
        res = res * - 1; // Чтобы не учитывать квадратные доски, сразу вычитаем их
        for(int i = m - 1; i >= 0; i--) // Находим количество прямоугольников
        {
            for(int j = n - 1; j >= 0; j--) 
            {
                res += (m - i) * (n - j);
            }
        }
        cout << ' ' << res << endl; // Вывод количества прямоугольников
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k; // Количество заданий

cin >> k;

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

{

int m, n; // Размер шахматной доски

cin >> m >> n;

int res = 0; // Количество кусков, на которые мы можем разделить доску

for(int i = min(m, n); i >= 0; i--) // Находим количество квадратов

{

res += (m - i) * (n - i);

}

cout << res; // Вывод количества квадратных досок

res = res * - 1; // Чтобы не учитывать квадратные доски, сразу вычитаем их

for(int i = m - 1; i >= 0; i--) // Находим количество прямоугольников

{

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

{

res += (m - i) * (n - j);

}

cout << ' ' << res << endl; // Вывод количества прямоугольников

}

return 0;

}

Объяснение

Ответом на каждый запрос будет количество квадратов и прямоугольников которые можно получить из нашей шахматной доски размера $M\times N$. Для вычисления количества квадратов нам надо посчитать, сколько квадратов каждого возможного размера поместится в нашей шахматной доске. Аналогично для прямоугольников. Пример с доской $3\times 2$ разобран на картинке.

Пояснение к первому тесту

Для подсчёта квадратов, нам следует отдельно считать их количество для каждого возможного размера. Таким образом сначала идут квадраты $1\times 1$, то есть $M\cdot N$ квадратов. Далее, квадратов $2\times 2$ помещаются ровно на $1$ меньше горизонтально и на $1$ меньше вертикально, значит получаем $(M-1)\times (N-1)$. Соответственно, $(M — 2)\times (N — 2)$ для квадратов $3\times 3$. И так продолжаем пока квадрат помещается в нашу доску.

Аналогично мы поступаем и с прямоугольниками. Однако считая количество прямоугольников каждого размера, нам нужно считать сколько поместится прямоугольников размера $(1\times 1), (1\times 2)\dots (1\times N)$. Также $(2\times 1), (2\times 2)\dots (2\times N)$. И так до $(M\times 1), (M\times 2)\dots (M\times N)$. Это довольно просто реализовать используя вложенный цикл.

Не стоит забывать, что квадрат — тот же прямоугольник, но с равными сторонами и в нашем цикле мы считаем все прямоугольники. А так как квадраты мы не должны учитывать, то после нахождения числа прямоугольников, нам нужно вычесть из него количество квадратов. В коде после нахождения и вывода числа квадратов, мы домножили это число на $(-1)$ и и уже после прибавили к нему количество прямоугольников, таким образом не учитывая квадраты.

Ссылки

Условие на e-olymp.

Код на ideone.

Related Images:

e-olymp 4142. Большой XOR

03/12/2019 by Никита Репнин

Задача

Для заданного целого $x$ найти количество таких $a$, удовлетворяющих условию:

$ a $ xor $x > x $
$ 0 < a < x $

где $a$ и $x$ — целые, xor — битовый XOR оператор.

Имеются $q$ запросов, каждый из которых содержит целое число $x$. Для каждого запроса выведите общее количество значений $a$, удовлетворяющих условиям выше.

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

Первая строка содержит число запросов $q$ $(1 \leqslant q \leqslant 10^5)$. Каждая из следующих $q$ строк содержит значение $x$ $(1 \leqslant x \leqslant 10^{10})$.

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

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

Тесты

№	Входные данные	Выходные данные
1	2 2 10	1 5
2	3 13 3 16	2 0 15
3	5 1 7 4294967295 42 451	0 0 0 21 60

Код

#include <iostream>
using namespace std;
int main() {
    long q, x, res, two; 
    cin >> q;
    for(long i = 0; i < q; ++ i){
        cin >> x;
        res = 0;
        two = 1; // two = 2^0
        while(x > 0){
            if(x % 2 == 0) // проверяем равен ли бит нулю
                res += two;
            x >>= 1;  // двигаемся к следующему биту
            two <<= 1; // увеличиваем степень двойки
        }
        cout << res << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long q, x, res, two;

cin >> q;

for(long i = 0; i < q; ++ i){

cin >> x;

res = 0;

two = 1; // two = 2^0

while(x > 0){

if(x % 2 == 0) // проверяем равен ли бит нулю

res += two;

x >>= 1; // двигаемся к следующему биту

two <<= 1; // увеличиваем степень двойки

}

cout << res << endl;

}

return 0;

}

Решение

XOR выдаёт число, биты которого равны $1$, когда лишь у одного из чисел соответствующий бит равен $1$. Числа большие чем $x$ получаем лишь тогда, когда $2^{k}\leqslant a<2^{k+1}$, где $k$- номер бита числа $x$, который равен нулю. Таких $a$ существует $2^k$ штук для каждого такого бита.

Задача на e-olymp

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

Засчитанное решение

Related Images:

e-olymp 6264. Энергетический магнат

01/02/2019 by Виктор Иванов

Задача

Маленький Вася играет в новую компьютерную игру — пошаговую стратегию «Энергетический магнат».

Правила игры достаточно просты:

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

Пример №1.

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

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

Первая строка содержит число [latex]n \left(1\leqslant n\leqslant 1000 \right)[/latex] — количество слотов на доске. Вторая строка содержит строку [latex]s[/latex]. [latex]i[/latex]-ый символ строки равен [latex]1[/latex], если Вы можете построить однослотовую электростанцию в [latex]i[/latex]-ом раунде, и символ [latex]2[/latex], если Вы можете построить двуслотовую электростанцию в [latex]i[/latex]-ом раунде. Количество раундов в игре не превосходит [latex]100000[/latex].

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

Вывести одно число — наибольшее количество очков, которое можно достичь.

Тесты

№	Вхлодные данные	Выходные данные
1	3 21121	10
2	2 12	2
3	2 211	4

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

#include <iostream>
using namespace std;

int main() {
    long n, c, res = 0, num = 0; //num - количество двуслотовых электростанций.
    long temp;  //temp - количество свободных слотов.
    cin >> n;
    temp = n;
    char s;
    while(cin >> s) {
        c = (s - '0');
        num += (c == 2) ? 1 : 0;
        if (temp - c < 0 && num >= 1) {
            temp += (2 - c);
            num -= 1;
        }
        else if (temp - c >= 0) {
            temp -= c;
        }
        res += (num < 1) ? (n - temp) : (n - temp - num);
    }
    cout << res;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long n, c, res = 0, num = 0; //num - количество двуслотовых электростанций.

long temp; //temp - количество свободных слотов.

cin >> n;

temp = n;

char s;

while(cin >> s) {

c = (s - '0');

num += (c == 2) ? 1 : 0;

if (temp - c < 0 && num >= 1) {

temp += (2 - c);

num -= 1;

}

else if (temp - c >= 0) {

temp -= c;

}

res += (num < 1) ? (n - temp) : (n - temp - num);

}

cout << res;

return 0;

}

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

Будем увеличивать num на 1, если встречается двуслотовая электростанция. Если нет свободных слотов [latex]temp — c\lt0[/latex] и [latex]num\geqslant1[/latex], то вместо двуслотовой ставим станцию, которая в этом ходе должна быть [latex]temp += (2 — c)[/latex] и вычитаем одно очко. В итоге смотрим, если двуслотовых электростанций нет [latex]num\gt 1[/latex], то считаем однослотовые: [latex]n — temp[/latex], а если они есть, то: [latex]n — temp — num[/latex].

Ссылки

Условие задачи на e-olymp
Код программы ideone

Related Images:

e-olymp 2507. Граница

08/01/2019 by Михаил Бутник

Задача

В международной политике важным понятием является граница между государствами. Нечеткое понимание сторонами того, где проходит граница, может привести к международным конфликтам и даже войнам. В этой задаче ситуация обстоит несколько проще, так как у двух рассматриваемых в задаче государств есть четкое понимание, какая территория принадлежит какому из них. Территория, занимаемая этими двумя государствами, представляет собой прямоугольник размером [latex]h[/latex] на [latex]w[/latex] километров, разбитый на квадраты со стороной в один километр. Каждый из этих квадратов полностью принадлежит либо первому государству, либо второму. Необходимо определить длину границы между двумя государствами. Сторона единичного квадрата считается принадлежащей границе, если по одну сторону от нее лежит квадрат, принадлежащий первому государству, а по другую — принадлежащий второму.

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

Первая строка содержит два целых числа: [latex]w[/latex] и [latex]h \left(1 \leqslant w, h \leqslant 100\right)[/latex] — размеры прямоугольника в километрах. Далее следуют [latex]h[/latex] строк, описывающих территорию. Каждая из них содержит [latex]w[/latex] символов. Если символ равен [latex]A[/latex], то соответствующий единичный квадрат принадлежит первому государству, а если он равен [latex]B[/latex], то второму. Гарантируется, что каждому государству принадлежит хотя бы один квадрат. Территории каждого из государств представляют собой связные области.

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

Выведите одно целое число — длину границы между государствами в километрах.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 6 AAABB ABBBB AAABB AAAAB AAAAB AABBB	13
2	4 3 AAAA AAAA AAAB	2
3	5 9 BBBBB ABBBB AABBB AAABB AAAAB AAABB AABBB ABBBB BBBBB	15
4	2 1 AB	1
5	6 5 AABBBB BBBBBB BBBAAA AAAAAA AAAAAA	10

Код

#include <iostream>
using namespace std;

int main() {
    int w, h, res = 0;
    cin >> w >> h;
    char **x = new char *[h];
    for (int i = 0; i < h; i++) x[i] = new char[w];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> x[i][j];
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w - 1; j++) {
            if (x[i][j] != x[i][j + 1]) res++;
        }
    }
    for (int i = 0; i < h - 1; i++) {
        for (int j = 0; j < w; j++) {
            if (x[i][j] != x[i + 1][j]) res++;
        }
    }
    cout << res << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int w, h, res = 0;

cin >> w >> h;

char **x = new char *[h];

for (int i = 0; i < h; i++) x[i] = new char[w];

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

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

cin >> x[i][j];

}

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

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

if (x[i][j] != x[i][j + 1]) res++;

}

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

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

if (x[i][j] != x[i + 1][j]) res++;

}

cout << res << endl;

return 0;

}

Решение

Занесем прямоугольную область в многомерный массив символов. Рассмотрим символ x[i][j]. Если он не совпадает с x[i + 1][j], то между ними имеется граница длины 1 (снизу от x[i][j] проходит граница). Аналогично, если x[i][j] не совпадает с x[i][j + 1], то между ними имеется граница длины 1 (справа от x[i][j] проходит граница). Остается перебрать все символы и подсчитать для них количество нижних и правых границ.

Запустить код (ideone) можно здесь
Задача на E-olymp

Related Images:

e-olymp 1215. Камень, ножницы или бумага?

27/12/2018 by Лиза Севастьянова

Задача

Условие

Камень > ножницы > бумага > камень > ножницы > …

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

Камень всегда побеждает Ножницы (Камень раздавливает Ножницы)
Ножницы всегда побеждают Бумагу (Ножницы режут Бумагу)
Бумага всегда бьет Камень (Бумага покрывает Камень)

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

Первая строка содержит количество тестов $t$ ($0 < t < 1000$). Первая строка каждого теста содержит количество раундов $n$ ($0 < n < 100$), сыгранных в игру Камень, Ножницы, Бумага. Каждая из следующих $n$ строк содержит одну из заглавных букв $R$ (Камень), $P$ (Бумага) или $S$ (Ножницы), пробел и снова заглавную букву $R$, $P$ или $S$. Первая буква обозначает выбор первого игрока, вторая буква — выбор второго игрока.

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

Для каждого теста в отдельной строке вывести имя победителя (Player 1 или Player 2). Если игра заканчивается вничью, вывести TIE.

Тесты

№	Входные данные	Выходные данные
1	3 2 R P S R 3 P P R S S R 1 P R	Player 2 TIE Player 1
2	1 1 S P	Player 1
3	2 3 S P P S R R 2 P R S R	TIE TIE
4	4 1 R P 2 R P S R 3 R P S R P S 4 P R R S P S S S	Player 2 Player 2 Player 2 Player 1

Решение

Для решения задачи необходимо сравнить выбор первого и второго игрока в каждом раунде каждого теста.
Подсчитываем количество побед для игроков во всех раундах теста. Получаем победителя для каждого теста.
В данной реализации используем вложенные циклы. Вводим переменную $t$ — количество тестов. Затем задаём цикл, в котором вводим новую переменную $n$ — количество раундов для каждого теста. Этот цикл будет работать, пока не проверим все тесты. Так же заводим два счётчика sum1 и sum2, которые будут подсчитывать победы первого и второго игрока. Задаём ещё один цикл, который будет выполняться, пока не проверим все раунды для каждого теста. В нём вводим выбор первого игрока и выбор второго игрока. Сравниваем данные значения согласно правилам победы, которые описаны в условии. В случае победы первого игрока увеличиваем переменную sum1 на единицу, в случае победы второго — sum2 на единицу. После завершения циклов сравниваем переменные sum1 и sum2, выводим соответствующие результаты.

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

#include <iostream>
using namespace std;

int main() {
    int t; // количество тестов
    cin >> t;
    for (int i = 0; i < t; i++) { // цикл для тестов
        int n; // количество раундов
        cin >> n;
        int sum1 = 0, sum2 = 0; // счётчики побед первого и второго игроков
        for (int j = 0; j < n; j++) { // цикл для раундов
            char p1, p2; // выбор первого и второго игроков
            cin >> p1 >> p2;
            if ((p2 == 'R' and p1 == 'S') or (p2 == 'S' and p1 == 'P') or (p2 == 'P' and p1 == 'R')) {
                sum2++;
            } else if (p1 != p2) {
                sum1++;
            }
        }
        if (sum1 > sum2) {
            cout << "Player 1" << endl;
        } else if (sum2 > sum1) {
            cout << "Player 2" << endl;
        } else cout << "TIE" << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int t; // количество тестов

cin >> t;

for (int i = 0; i < t; i++) { // цикл для тестов

int n; // количество раундов

cin >> n;

int sum1 = 0, sum2 = 0; // счётчики побед первого и второго игроков

for (int j = 0; j < n; j++) { // цикл для раундов

char p1, p2; // выбор первого и второго игроков

cin >> p1 >> p2;

if ((p2 == 'R' and p1 == 'S') or (p2 == 'S' and p1 == 'P') or (p2 == 'P' and p1 == 'R')) {

sum2++;

} else if (p1 != p2) {

sum1++;

}

if (sum1 > sum2) {

cout << "Player 1" << endl;

} else if (sum2 > sum1) {

cout << "Player 2" << endl;

} else cout << "TIE" << endl;

}

return 0;

}

Ссылки

Related Images:

e-olymp 137. НОД

25/12/2018 by Михаил Бутник

Задача

Найти НОД (наибольший общий делитель) [latex]n[/latex] чисел.

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

Первая строка содержит количество чисел [latex]n \left(1 \lt n \lt 101\right).[/latex] Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает 30000.

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

НОД заданных чисел.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 15 25	5
2	3 99 358 2	1
3	5 81 99 72 108 36	9
4	2 25 50	25
5	4 132 36 66 18	6

Код

#include <iostream>
using namespace std;
int gcd(int a, int b) {
    return (a == 0) ? b: gcd(b % a, a);
}

int main() {
    int n, m = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        m = gcd(m, a);
    }
    cout << m;
    return 0;
}

#include <iostream>

using namespace std;

int gcd(int a, int b) {

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

}

int main() {

int n, m = 0;

cin >> n;

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

int a;

cin >> a;

m = gcd(m, a);

}

cout << m;

return 0;

}

Решение

Для решения этой задачи я воспользовался функцией gcd — рекурсивной функцией нахождения НОД 2-x чисел. В цикле читаем [latex]n[/latex] чисел и применяем к ним функцию gcd для нахождения их НОД. При первом проходе цикла находим НОД первого числа и нуля, так как это и будет само число.

Запустить код (ideone) можно здесь
Задача на E-olymp

Related Images:

e-olymp 8653. Прибавить вычесть и умножить

22/12/2018 by Николь Метри

Задача

Пусть x — переменная, изначально равная 0. Промоделируйте выполнение следующих операций над ней:

add a: прибавить значение a к x;
subtract a: вычесть значение a из x;
multiply a: умножить x на a;

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

Каждая строка содержит операцию и значение. Промоделируйте все операции. Значение переменной x при выполнении каждой операции не превышает по модулю $10^9$.

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

Выведите результирующее значение переменной x.

Тесты

№	Ввод	Вывод
1	add 2 subtract 5 subtract 1 multiply -3	12
2	subtract 5 multiply -5 add 5	30
3	add 6 add 543 multiply 23	12627
4	multiply 45678 add 3	3
5	subtract 58 add 38 multiply -1 add 100	120

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

#include <iostream>
using namespace std;

int main() {
    int x = 0, a;
    string s;
    while (cin >> s){
        cin >> a;
        if (s == "multiply") {
            x*=a;
        }
        else if (s == "subtract") {
            x-=a;
        }
        else {
            x+=a;
        }
    }
    cout << x;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x = 0, a;

string s;

while (cin >> s){

cin >> a;

if (s == "multiply") {

x*=a;

}

else if (s == "subtract") {

x-=a;

}

else {

x+=a;

}

cout << x;

return 0;

}

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

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