Category Archives: 5. Массивы

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

[su_posts template=»templates/default-loop.php» id=»3191″ post_type=»page»]

В классе и дома решаются следующие тренировочные задачи (1 балл):

Санта Клаус
Кубики — 3 — используйте массив bool для хранения предположений о потери кубика для каждой из 26+26=52 букв.
Прямоугольник — используйте массив точек.

Опубликованные решения

e-olymp 806. Платформы — 3

08/12/2019 by Мария Жаркая

Задача

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю, у героя уходит $|y_{2} — y_{1}|^2$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3|y_{3} -y_{1}|^2$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-й платформы до $n$-й (последней).

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

Первая строка содержит количество платформ $n$ $(2 \leqslant n \leqslant 10^5)$, вторая — $n$ целых чисел, значения которых не превышают по модулю $4000$ — высоты платформ.

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

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

Тесты

№	Входные данные	Выходные данные
1	4 1 2 3 30	731
2	4 0 1 6 8	40
3	8 1 15 16 23 42 10 84 5	828
4	7 57 54 -55 -34 21 88 -100	55189
5	7 -4000 4000 -4000 4000 -4000 4000 -4000	0

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

#include <iostream>

using namespace std;

int main() {

int n; long long j, sj, bj; // "цены" прыжка, суперприёма и 3-го типа прыжка

cin >> n;

int platforms[n]; long long energy[n]; // создаём массивы для платформ и энергии

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

cin >> platforms[i]; //считываем высоты платформ

}

energy[0] = 0;

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

// обычный прыжок

j = (platforms[i] - platforms[i - 1]) * (platforms[i] - platforms[i - 1]);

// 3-й тип прыжка

bj = (platforms[i] - platforms[i + 1]) * (platforms[i] - platforms[i + 1]) +

3 * (platforms[i + 1] - platforms[i - 1])*(platforms[i + 1] - platforms[i - 1]);

// суперприём

if (i == 1) sj = max(j, bj);

else sj = 3 * (platforms[i] - platforms[i - 2]) * (platforms[i] - platforms[i - 2]);

if (i == n - 1) bj = max(j, sj);

//количество энергии на i-й платформе

energy[i] = min(energy[i - 1] + bj, min(energy[i - 1] + j, energy[i - 2] + sj));

}

cout << energy[n - 1];

}

Решение

Чтобы решить задачу, мы создадим массив $energy$, где будем хранить минимальную энергию, которую герой потратит для прыжка на очередную $i$-ю платформу. Для этого необходимо для каждой платформы, начиная со второй, рассмотреть три вида прыжка:

прыжок с предыдущей $i — 1$ платформы.
суперприём, то есть прыжок c $i — 2$ платформы.
3-й вид: суперприём с $i — 1$ платформы на $i + 1$ и прыжок назад на $i$.

«Цены» за обычный прыжок и суперприём мы можем найти из формул данных в условии, с 3-м же сложнее — результатом будет сумма «цены» суперприёма $3(y_{i+1} — y_{i-1})^2$ и «цены» прыжка назад $(y_{i} — y_{i+1})^2$.

Для понимания схемы можно рассмотреть в качестве примера второй тест.
Синим обозначен 3-ий тип. Красными цифрами — весь путь.

второй тест

Каждый из 3-х путей даст своё значение энергии, равное сумме «цены» прыжка на $i$-ю платформу и значения в той, из которой герой совершил прыжок. Наименьшей энергией для этой платформы будет минимум из этих трех значений.
На второй платформе $(i = 1)$ в случае суперприёма мы выходим за границы массива и получаем независимое значение, поэтому эффективнее будет в качестве «цены» выбирать максимум из двух других уже найденных значений. Аналогично на последней $(i = n — 1)$ и 3-м типе прыжка, максимум будет невыгодным и соответственно не будет выбран как минимум в $energy_{i}$.

Ссылки

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

Мария Жаркая

Студентка с пристрастием к сладкому.

e-olymp 841. Спираль

05/12/2019 by Валентин Цушко

Условие

Вывести квадрат, состоящий из $N \times N$ клеток, заполненных числами от $1$ до $N^{2}$ по спирали.

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

В первой строке находится единственное число $N (2 \leq N \leq 100)$.

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

Выводится $N$ строк по $N$ чисел, разделённых пробелами. Не допускается начинать спираль в ином, кроме верхнего левого, углу, закручивать спираль против часовой стрелки или изнутри наружу.

Тесты

№1	Входные данные	Выходные данные
1	3	1 2 3 8 9 4 7 6 5
2	4	1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7
3	5	1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
4	10	1 2 3 4 5 6 7 8 9 10 36 37 38 39 40 41 42 43 44 11 35 64 65 66 67 68 69 70 45 12 34 63 84 85 86 87 88 71 46 13 33 62 83 96 97 98 89 72 47 14 32 61 82 95 100 99 90 73 48 15 31 60 81 94 93 92 91 74 49 16 30 59 80 79 78 77 76 75 50 17 29 58 57 56 55 54 53 52 51 18 28 27 26 25 24 23 22 21 20 19

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

#include <iostream>

using namespace std;

int main()

{

int n, m = 1;

cin >> n;

int a[n][n];

if(n % 2 != 0){

a[(n / 2)][(n / 2)] = (n * n); // если N - нечетное то находим центр матрицы и заполняем его числом N * N

}

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

for(int j = i; j < (n - i); j++){ // (n - i) - чтоб с каждым разом сторона становилась меньше

a[i][j] = m;

m++;

}

for(int j = 1; j < (n - i - i); j++){ // начинаем с первого эл. так-как нулевой уже записан

a[(j + i)][(n - i) - 1] = m; // (n - i) - 1 - отнимаем 1 чтоб не выходило за рамки массива

m++;

}

for(int j = (n - 2) - i; j >= i; j--){ // (n - 2) - i - отнимаем 1 чтоб не выходило за рамки массива и еще одну 1

a[(n - i) - 1][(j)] = m; // потому-что предыдущий эл. уже заполнен.

m++;

}

for(int j = ((n - i) - 2); j > i; j--){

a[j][i] = m;

m++;

}

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

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

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

}

cout << a[i][n - 1] << endl;

}

return 0;

}

Решение

Для того чтобы решить эту задачу нам нужно определить способ заполнения. Первым делом, если $N$ — нечетное, то находим центр матрицы и заполняем его числом $N \times N $ a[(n / 2)][(n / 2)] = (n * n);. В условии написано, что “Не допускается начинать спираль в ином, кроме верхнего левого углу, закручивать спираль против часовой стрелки или изнутри наружу.”, то есть начинать мы будем с верхнего левого угла. Для этого мы сделаем цикл for(int i = 0; i < (n / 2); i++);, в котором сделаем 4 такта. Каждый такт заполняет определенную часть матрицы:

- 1 такт – заполняет верхнюю грань слева направо;
- 2 такт – заполняет правую грань сверху вниз;
- 3 такт – заполняет нижнюю грань справа налево;
- 4 такт – заполняет левую грань снизу вверх (как показано на картинке (1.1));

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

картинка (1.1)

ссылки:
Задача на e-olymp
Код на OnlineGDB
Код на Ideone
Засчитанное решение на e-olymp

Валентин Цушко

Всё идёт по плану

e-olymp 9410. Студенческая любовь

01/12/2019 by Дмитрий Воротов

Задача

Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношения. Коэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?

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

Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.

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

Выведите одно число — ответ на задачу.

Тесты

№	Входные данные	Выходные данные
1	2 -3 -5 3 5	0
2	1 5 -2	0
3	5 -5 -2 -1 0 4 5 4 0 0 -1	4
4	9 1000 -22 333 -56 1 2 -77 -650 10 -7 166 -333 90 -565 12 788 -800 111	523

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

#include <iostream>

#include

using namespace std;

int main() {

int n;

cin >> n;

int *a = new int[n], *b = new int[n];

for (int i = 0; i < n; i ++) cin >> a[i]; // Считываем массивы

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

sort(a, a + n); // Сортируем массивы

sort(b, b + n); // Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке

for (int i = 0; i < n; i ++) a[i] += b[n - i - 1]; // Суммируем элементы

int maxa = a[0], mina = a[0];

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

maxa = max(maxa, a[i]); // Находим минимальный и максимальный элементы

mina = min(mina, a[i]);

}

cout << maxa - mina; // Разность минимального и максимального и будет самым маленьким индексом любви

return 0;

}

Решение

Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.

Ссылки

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

Код решения ideone

Дмитрий Воротов

e-olymp 972. Сортировка времени

26/06/2019 by Максим Евчук

Задача

Отсортируйте время согласно заданному критерию

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

Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)

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

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

Тесты

№	Входные данные	Выходные данные
1	[latex]\begin{matrix} 4 & & \\ 10 &20 &30 \\ 7 &30 &00 \\ 23&59 &59 \\ 13&30 &30 \end{matrix}[/latex]	[latex]\begin{matrix} 7 & 30 &00 \\ 10&20 &30 \\ 13&30 &30 \\ 23& 59 & 59 \end{matrix}[/latex]
2	$\begin{matrix} 6\\ 12 &55 &59 \\ 8 &33 &34 \\ 6 &56 &46 \\ 10 &23 &52 \\ 3 &20 &00 \\ 19 &31 &0\\ 10&23&52 \end{matrix}$	$\begin{matrix} 3 &20 &0 \\ 6 &56 &46 \\ 8 &33 &34 \\ 10 &23 &52 \\ 12 &55 &59 \\ 19 &31 &0 \end{matrix}$

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int hours[100];

int mins[100];

int secs[100];

int all_time[100];

int n;

cin >> n;

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

cin >> hours[i] >> mins[i] >> secs[i];

all_time[i] = hours[i] * 3600 + mins[i] * 60 + secs[i];

}

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

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

if (all_time[i] > all_time[j]) {

swap(hours[i], hours[j]); swap(mins[i], mins[j]);

swap(secs[i], secs[j]); swap(all_time[i], all_time[j]);

}

for (int i = 0; i < n; i++) cout << hours[i] << " " << mins[i] << " " << secs[i] << endl;

}

Решение

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

Ссылки

e-olymp
ideone

Максим Евчук

e-olymp 2667. Змейка

26/06/2019 by Дмитрий Калинин

Задача

Напишите программу, которая выводит элемент из строки $x$ и столбца $y$ матрицы размера $n × m$, которая заполнена змейкой:

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

Даны натуральные числа $n, m, x, y (1 \leqslant x \leqslant n \leqslant 50, 1 \leqslant y \leqslant m\leqslant 50)$. Здесь $n$- количество строк матрицы, $m$ — количество столбцов матрицы, $x$ и $y$ — номера строки и столбца искомого элемента.

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

Вывести элемент из строки $x$ и столбца $y$.

Решение

Для решения создаётся матрица в представлении массива размера $n* m$, который заполняется следующим образом: если текущая строка матрицы нечётная, то элемент массива принимает значение номера строки, умноженного на количество $m$ столбцов матрицы плюс номер текущего столбца, а если текущая строка — чётная, то текущему элементу массива присваивается значение, равное произведению увеличенного на единицу номера $n$ строки на количество $m$ столбцов матрицы минус увеличенный на единицу номер текущего столбца. Для вывода значения матрицы по двум координатам мы используем элемент массива с индексом равным сумме координаты $y$ на произведение координаты $x$ на количество столбцов $m$, которое используется для «прыжка» через необходимое количество строк.

Тесты

№	Ввод	Вывод
1	5 2 3 1	4
2	4 5 3 1	10
3	50 48 45 20	2131

Код

#include <iostream>

using namespace std;

int main() {

int n, m, x, y;

cin >> n >> m >> x >> y;

x--, y--;

int *arr = new int[n * m];

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

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

arr[i * m + j] = (i % 2 == 0 ? i * m + j : (i + 1) * m - (j + 1));

}

cout << arr[x * m + y];

return 0;

}

Ссылки

Дмитрий Калинин

e-olymp 4749. Выручка театра

25/06/2019 by Никита Семерня

Задача

В театре $n$ рядов по $m$ мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ($1$ — соответствующий билет продан, $0$ — не продан).
Определите общую выручку от спектакля.

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

Сначала записано число $n$, затем число $m$ $(n, m \le 500)$. После задана матрица стоимостей билетов ($n$ строк по $m$ чисел, каждое из чисел от $0$ до $10000$). Далее задана матрица проданных билетов — снова $n$ строк по $m$ чисел.

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

Выведите общую выручку от продажи билетов.

Тесты

Входные данные	Выходные данные
3 3 1 2 3 4 5 6 7 8 9 1 0 1 0 1 0 1 0 1	25
1 1 1 0	0
1 1 1 1	1

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

#include <iostream>

using namespace std;

int main() {

int n, m, totalRevenue = 0;

cin >> n >> m;

int* tickets = new int[n * m];

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

cin >> tickets[i];

}

for (int i = 0, isSold; i < n * m; i++) {

cin >> isSold;

totalRevenue += tickets[i] * isSold;

}

cout << totalRevenue;

return 0;

}

Решение

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

Ссылки

Ideone
e-olymp

Никита Семерня

e-olymp-8577. Супер платформи

25/06/2019 by Евгений Рудницкий

Условие

У багатьох старих іграх з двовимірною графікою можна зіткнутися з такою ситуацією. Який-небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. При цьому, при стрибку з однієї платформи на сусідню, у героя витрачається $\left|y_2–y_1\right|$енергії, де $y_2$ та $y_1$ – висоти, на яких розміщені ці платформи. Крім того у героя є суперприйом, який дозволяє перестрибнути через платформу, причому на це витрачається $3·|y_2–y_1|$ одиниць енергії. Кількість використань суперприйому обмежена й повинна перебувати в межах від $k_{min}$ до $k_{max}$ разів (обидві межі включно). Звичайно ж, енергію потрібно витрачати максимально економно.

Припустимо, що вам відомі координати усіх платформ у порядку від лівого краю до правого та обмеження на кількість використань суперприйому $k_{min}$ та $k_{max}$. Чи зможете ви знайти, яку мінімальну кількість енергії потрібно герою, щоб дістатись від першої платформи до останньої?

Вхідні дані

У першому рядку записана кількість платформ $n (1 \leq n ≤ 10000)$. Другий рядок містить n натуральних чисел, які не перевищують 30000 – висоти, на яких розміщено платформи. Третій рядок містить два цілі невід’ємні числа $k_{min}$ та $k_{max}$ $\left(0 ≤ k_{min} ≤ k_{max} ≤ \frac{n–1}{2}\right)$.

Вихідні дані

Виведіть єдине число – мінімальну кількість енергії, яку повинен витратити гравець на подолання платформ (звісно ж у припущенні, що cheat-коди використовувати не можна).

Тесты

№	Ввод	Вывод
1	3 1 5 10 0 1	9
2	9 1 3 2 3 8 10 25 17 25 2 4	24

Код

#include <iostream>

using namespace std;

#define ll long long

int main() {

ll n, i, j, minjumps, maxjumps, me = 1000000000;

cin >> n;

ll p[n];

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

cin >> p[i];

}

cin >> minjumps >> maxjumps;

ll a[2][n + 1];

a[0][0] = 0;

for (i = 1; i < n; i++)a[0][i] = a[0][i - 1] + abs(p[i] - p[i - 1]);

if (minjumps == 0)me = a[0][n - 1];

for (j = 1; j <= maxjumps; j++) {

a[j % 2][j * 2] = a[(j - 1) % 2][j * 2 - 2] + 3 * abs(p[j * 2] - p[j * 2 - 2]);

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

a[j % 2][i] = min(a[j % 2][i - 1] + abs(p[i - 1] - p[i]), a[(j - 1) % 2][i - 2] + 3 * abs(p[i - 2] - p[i]));

}

if ((j >= minjumps) and (me > a[j % 2][n - 1])) { me = a[j % 2][n - 1]; }

}

cout << me << endl;

return 0;

}

Решение

В решении суперприёмы из условия для удобства буду называть суперпрыжками.
Решим эту задачу динамически. На каждом шаге будем искать масив, где записано сколько минимально надо потратить энергии что б добраться до каждой платформы, сделав ровно $j$ суперпрыжков. Легко получить рекурсивную зависимость: для того, что бы попасть на $i$ платформу нам надо либо прыгнуть с предыдущей $(a_{j (i-1)}+|p_i-p_{i-1}|)$ либо сделать суперпрыжок с платформы под номером $i-2$ $( a_{(j — 1)(i — 2)} + 3|p_{i — 2} — p_i| )$. Не забудем про то, что не всегда можно прыгнуть с предыдущей так как мы могли бы и не попасть на нее за $j$ суперпрыжков. Таким образом для некоторых платформ( а именно первых в каждом масиве) мы будем делать суперпрыжок с платформы под номером $i-2$. На каждом шаге если нам разрешено сделать столько суперпрыжком сколько мы сделали обновляем общее минимальное количество затраченной энергии если оно больше чем результат, полученный нами на последней платформе. Таким образом на каждом шаге мы будем получать минимальные затраты для определенного количества прыжков. Таким образом минимальное из этих самых ответов и будет тем что требуется в задаче.

Оптимизация

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

Ссылки

Евгений Рудницкий

e-olymp 972. Сортировка времени

20/06/2019 by Виктор Иванов

Задача

Отсортируйте время согласно заданному критерию.

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

Сначала задано число $n$ $\left(1 \leqslant n \leqslant 100 \right),$ а затем $n$ моментов времени. Каждый момент времени задается $3$ целыми числами — часы (от $0$ до $23$), минуты (от $0$ до $60$), и секунды (от $0$ до $60$).

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

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

Тесты

№	Входные данные	Выходные данные
1	4 10 20 30 7 30 00 23 59 59 13 30 30	7 30 0 10 20 30 13 30 30 23 59 59
2	5 12 40 45 23 56 12 7 45 34 8 23 34 2 56 45	2 56 45 7 45 34 8 23 34 12 40 45 23 56 12
3	3 23 56 45 21 45 54 6 45 23	6 45 23 21 45 54 23 56 45

Код 1

#include <iostream>

using namespace std;

int a[101], b[101], c[101], d[101];

int main() {

int n;

cin >> n;

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

cin >> a[i] >> b[i] >> c[i];

d[i] = a[i] * 3600 + b[i] * 60 + c[i];

}

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

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

if (d[i] > d[j]) {

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

swap(b[i], b[j]);

swap(c[i], c[j]);

swap(d[i], d[j]);

}

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

cout << a[i] << " " << b[i] << " " << c[i] << endl;

}

return 0;

}

Код 2

#include <iostream>

using namespace std;

struct unsortedtime {

int hours;

int minutes;

int seconds;

};

bool operator > (const unsortedtime &a, const unsortedtime &b) {

bool res = false;

if (a.hours > b.hours) res = true;

else if (a.hours == b.hours) {

if (a.minutes > b.minutes) res = true;

else if (a.minutes == b.minutes) {

if (a.seconds > b.seconds) res = true;

}

return res;

};

int main() {

int n;

cin >> n;

unsortedtime *a = new unsortedtime[n];

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

cin >> a[i].hours >> a[i].minutes >> a[i].seconds;

}

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

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

if (a[i] > a[i + 1]) {

swap(a[i], a[i + 1]);

}

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

cout << a[i].hours << " " << a[i].minutes << " " << a[i].seconds << endl;

}

return 0;

}

Решение задачи (код 1)

Для решения задачи переведём в секунды каждый момент времени и введём их в массив d[i]. Далее, в этом массиве проверяем какой элемент больше if (d[i] > d[j]) и упорядочиваем эти элементы в порядке возрастания используя swap().

Решение задачи (код 2)

Для решение задачи вторым способом создадим структуру unsortedtime. Каждый элемент в этой структуре будет соответствовать часу, минуте, секунде. После чего создадим оператор > , в котором будем сравнивать моменты времени. В случае необходимости будем менять их местами, используя функцию swap(). В результате выведем с помощью цикла моменты времени, упорядоченные в порядке неубывания.

Ссылки

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

Виктор Иванов

e-olymp 8688. Количество чисел без 8

05/06/2019 by Андрей Зиновьев

Задача

Напишите программу, которая определяет количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.

Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Тесты

Входные данные	Вывод программы
10	9
25833798135522720	4918510377816614
88888888888888	20334926626631

Continue reading →

Андрей Зиновьев

e-olymp 682. Сумма на отрезке

30/05/2019 by Никита Пушкин

Задача

Задан набор чисел $a_{1}, …, a_{n}$. Для заданных индексов $l$ и $r$ найдите $$S_{l,r}=a_{l}+a_{l+1}+..+a_{r}$$

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

В первой строке записано количество чисел $n$ $\left(1 \leq n \leq 10^{6}\right)$. Во второй строке записаны числа $a_{i}$ $\left(1 \leq a_{i} \leq 1000\right)$, разделенные пробелом. На третьей строке записано число $m$ $\left(1 \leq m \leq 10^{6}\right)$ — количество запросов. Далее на отдельных строках записаны сами запросы $l_{i}$ и $r_{i}$ $\left(1 \leq l_{i} \leq r_{i} \leq n\right)$.

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

Выведите в отдельных строках $m$ чисел $S_{l_i,r_i}$.

Тесты

#	Входные данные	Выходные данные
1	5 1 2 3 4 5 5 1 5 2 3 3 4 2 5 1 4	15 5 7 14 10
2	10 10 10 10 10 10 10 10 10 10 10 5 1 3 3 5 5 7 7 9 3 7	30 30 30 30 50
3	10 57 42 24 73 98 71 65 76 12 33 7 1 2 4 5 8 10 1 10 7 10 2 5 3 8	99 171 121 551 186 237 407
4	3 10 15 20 2 1 2 1 3	25 45
5	7 299 38924 2388 4399 7549 79475 57947 10 1 3 2 3 3 3 4 7 6 7 3 5 5 5 6 6 1 6 1 7	41611 41312 2388 149370 137422 14336 7549 79475 133034 190981

#include <iostream>

using namespace std;

int main() {

std::ios::sync_with_stdio(false);

int n;

cin>>n;

long long a[n];

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

cin>>a[i];

}

long long summ[n + 1];

summ[0] = 0;

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

summ[i] = summ[i - 1] + a[i - 1];

}

int m;

cin>>m;

while (m--) {

int l, r;

cin>>l>>r;

printf("%d", summ[r] - summ[l - 1]);

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

}

Решение

Сначала читаем с клавиатуры набор $n$ чисел и добавляем их в массив $a\left[n\right]$. Далее создаем массив $summ$ из $n+1$ элементов, $i$-ый элемент которого равен сумме всех элементов $a$ до $i-1$ включительно. Затем $m$ раз считываем $l$ и $r$ с клавиатуры, и отнимаем от $summ\left[r\right]$ «хвост» в виде суммы элементов до $l-1$ элемента.

Условие задачи можно найти на e-olymp
Код решения — ideone

Никита Пушкин

e-olymp 4749. Выручка театра

30/05/2019 by Иван Дуков

Задача

В театре [latex]n[/latex] рядов по [latex]m[/latex] мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ([latex]1[/latex] — соответствующий билет продан, [latex]0[/latex] — не продан).
Определите общую выручку от спектакля.

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

Сначала записано число [latex]n[/latex], затем число [latex]m[/latex] ([latex]n[/latex], [latex]m \leqslant 500[/latex]). После задана матрица стоимостей билетов ([latex]n[/latex] строк по [latex]m[/latex] чисел, каждое из чисел от [latex]0[/latex] до [latex]10000[/latex]). Далее задана матрица проданных билетов — снова [latex]n[/latex] строк по [latex]m[/latex] чисел.

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

Выведите общую выручку от продажи билетов.

Тесты

№	Входные данные	Выходные данные
1	3 3	25
	1 2 3
	4 5 6
	7 8 9

	1 0 1
	0 1 0
	1 0 1
2	2 2	0
	1 1
	2 2

	0 0
	0 0
3	4 5	380
	15 16 17 18 19
	19 18 17 16 15
	19 20 21 22 23
	23 22 21 20 19

	1 1 1 1 1
	1 1 1 1 1
	1 1 1 1 1
	1 1 1 1 1

Код программы с использованием одномерных массивов

#include <iostream>

using namespace std;

int main() {

int x [500*500];

int n, m;

cin >> n >> m;

int nm= n*m;

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

cin >> x[i];

}

int k;

long long int v = 0;

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

cin >> k;

v+= k*x[i];

}

cout << v << endl;

return 0;

}

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

Описываем целочисленный одномерный массив x [500*500] для хранения матрицы стоимостей билетов. Описываем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] (количество строк и столбцов матрицы) и считываем их. Описываем целочисленную переменную [latex]nm[/latex] (количество мест в зале) и инициализируем ее произведением [latex]n \cdot m[/latex]. Цикл инициализирует [latex]nm[/latex] элементов массива [latex]x[/latex]. Описываем целочисленную переменную [latex]k[/latex], которая принимает значения [latex]0[/latex] или [latex]1[/latex] (билет не продан или продан), и целочисленную переменную [latex]v[/latex] — стоимость проданных билетов ([latex]v[/latex] имеет тип long long int, так как максимальное значение, которое она может принять, составляет [latex]500 \cdot 500 \cdot 10000=2500000000[/latex]). Цикл считывает значения [latex]k[/latex] и увеличивает [latex]v[/latex] на k*x[i].

Код программы с использованием многомерных массивов

#include <iostream>

using namespace std;

int x[500][500];

int main(){

int n, m, p;

cin >> n >> m;

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

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

cin >> x[i][j];

unsigned long long v = 0;

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

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

cin >> p;

if (p) v += x[i][j];

}

cout << v;

}

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

По условию заданы количество строк [latex]n[/latex] и количество столбцов [latex]m[/latex] матрицы стоимости театральных билетов ( [latex] n,m\leqslant 500[/latex], каждое из чисел от [latex]0[/latex] до [latex]10000[/latex] ). Описываем целочисленную матрицу x[500][500]. Объявляем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] и вводим их значения с клавиатуры. Считываем матрицу x. Объявляем переменную unsigned long long v = 0 — стоимость проданных билетов. Целочисленная переменная [latex]p = 1[/latex], если билет на ( [latex]i,j[/latex] )-е место продан, и [latex]p = 0[/latex] — в противном случае. Во вложенных циклах считываем значение [latex]p[/latex] из матрицы проданных билетов. Проверяем [latex]p[/latex] на положительность и увеличиваем [latex]v[/latex] на стоимость билета на ( [latex]i,j[/latex] )-е место.

Ссылки

e-olymp
ideone (код с одномерными массивами)
ideone (код с многомерными массивами)

Иван Дуков

e-olymp 2524. Строки Фибоначчи

26/05/2019 by Дария Даниленко

Задача

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

Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи $F_{0} = a$, $F_{1} = b$, … . Они задаются следующим образом: $F_{0} = a$, $F_{1} = b$, $F_{i} = F_{i-2}F_{i-1}$, $i >1$. Первые семь строк Фибоначчи выглядят следующим образом: $a$, $b$, $ab$, $bab$, $abbab$, $bababbab$, $abbabbababbab$.

Дима занимается в кружке олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о строках Фибоначчи. Он быстро понял, что их длина с увеличением номера $n$ растет очень быстро, поэтому задача нахождения всех символов строки $F_{n}$ требует слишком большого объема памяти. Поэтому он решил ограничиться задачей нахождения некоторых символов.

Напишите программу, которая находит $k$-ый символ строки $F_{n}$.

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

Первая строка содержит количество тестов $t$ ($1 ≤ t ≤ 100$). Каждая из следующих $t$ строк содержит два целых числа $n$ и $k$ ($0 ≤ n ≤ 45$, $1 ≤ k ≤ |F_{n}|$, через $|F_{n}|$ обозначена длина строки $F_{n}$, позиции символов в строке нумеруются с единицы).

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

Выведите $t$ строк, каждая из которых содержит $k$-ый символ строки $F_{n}$.

Тесты

Входные данные	Выходные данные
4 0 1 1 1 3 2 7 7	a b a a
1 10 15	a
6 45 6 38 30 6 5 24 40 0 1 2 2	b a b b a b

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

#include <iostream>

using namespace std;

int fib[45];

char solve(int n, int k) {

if (n == 0) return 'a';

if (n == 1) return 'b';

if (k <= fib[n - 2]) return solve(n - 2, k);

return solve(n - 1, k - fib[n - 2]);

}

int main() {

int n, k, tests;

fib[0] = 1;

fib[1] = 1;

for (int i = 2; i < 45; i++) fib[i] = fib[i - 1] + fib[i - 2];

cin >> tests;

while (tests--) {

cin >> n >> k;

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

}

return 0;

}

Решение

Воспользуемся тем, что длина $i$-той строки Фибоначчи будет равна $i$-тому числу Фибоначчи, так как для них справедливо одно и то же рекуррентное соотношение. Заводим массив fib[45]; , куда мы вычислим первые ($n ≤ 45$) числа Фибоначчи. Функция solve(int n, int k) находит $k$-ый символ строки $F_{n}$: так как $F_{i} = F_{i-2}F_{i-1}$, то если $k ≤ |F_{n-2}|$, то $k$-ый символ строки следует искать в $F_{n-2}$, в другом случае следует искать $(k — F_{n-2})$-ый символ в $F_{n-1}$. Таким образом, постепенно углубляясь в рекурсию, программа будет иметь дело с задачами все меньших размеров, пока наконец не выйдет на одну из единичных строк ( n == 0 или n == 1 ), и не выведет $a$ или $b$ соответственно.

Ссылки

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

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

Дария Даниленко

e-olymp 2099. Два массива

26/05/2019 by Даниил Мозгунов

Задача

Даны два массива чисел. Требуется вывести те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве.

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

Сначала подаётся количество [latex]n[/latex] элементов в первом массиве, затем [latex]n[/latex] чисел — элементы массива. Затем записано количество [latex]m[/latex] элементов во втором массиве. Далее заданы элементы второго массива. Количество элементов каждого массива не превышает [latex]100[/latex]. Все элементы — целые числа.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	7 3 1 3 4 2 4 12 6 4 15 43 1 15 1	4 3 3 2 12
2	5 12 16 17 45 68 6 1 93 45 68 34 38	3 12 16 17
3	10 15 47 68 59 75 25 35 61 21 86 10 15 47 69 58 75 26 36 61 21 89	5 68 59 25 35 86
4	10 15 47 68 59 75 25 35 61 21 86 10 15 47 68 59 75 25 35 61 21 86	0 0

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

#include <iostream>

using namespace std;

int main() {

bool q;

int n, m, c = 0;

int arr1[101], arr2[101], arr3[101];

cin >> n;

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

cin >> arr1[i];

}

cin >> m;

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

cin >> arr2[i];

}

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

q = false;

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

if (arr1[i] == arr2[j]) q = true;

if (q == false) {

arr3[c] = arr1[i];

c++;

}

cout << c << endl;

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

cout << arr3[i] << " ";

}

cout << arr3[c - 1];

return 0;

}

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

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

Ссылки

Даниил Мозгунов

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

e-olymp 8173. Большинство

04/05/2019 by Никита Шпилевский

Задача

Голоса собраны! Были опрошены математики по всему миру, и каждый из них выбрал свой любимый номер между [latex]1[/latex] и [latex]1000[/latex]. Ваша цель — подсчитать голоса и определить самый популярный номер.

Если существует несколько голосов с наибольшим количеством, то выберите наименьшее число с максимальным количеством голосов.

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

Первая строка содержит количество тестов, от [latex]1[/latex] до [latex]100[/latex] включительно. Первая строка каждого теста содержит количество голосов [latex]V (1 \leq V \leq 1000)[/latex], за которой следуют [latex]V[/latex] строк — каждая из них содержит одно число от [latex]1[/latex] до [latex]1000[/latex].

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

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

Тесты

№	Входные данные	Выходные данные
1	2 3 42 42 19 4 7 99 99 7	42 7
2	1 5 11 12 13 14 15	11
3	2 2 1000 1000 1 3	1000 3

Код

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int testAmount, V, digit, numberOfMax, max, maxDigit, answer;

cin >> testAmount;

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

int digitAmountArray[1001] = {};

maxDigit = 0;

answer = 0;

cin >> V;

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

cin >> digit;

if(digit > maxDigit) maxDigit = digit;

digitAmountArray[digit]++;

}

max = digitAmountArray[0];

for (int p = 1; p <= maxDigit; p++) {

if(digitAmountArray[p] > max) {

max = digitAmountArray[p];

numberOfMax = p;

}

for(int l = 0; l <= maxDigit; l++) {

if(digitAmountArray[l] == digitAmountArray[numberOfMax]) {

answer = min(numberOfMax, l);

}

cout << answer << endl;

}

return 0;

}

Решение

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

Ссылки

- Задача на e-olymp
- Решение на e-olymp

Никита Шпилевский

e-olymp 2322. Столбцы

28/04/2019 by Михаил Бутник

Столбцы

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

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

В первой строке задано число [latex]x[/latex], не превышающее по модулю 2 [latex]\cdot[/latex] 10⁹. Во второй строке задано число [latex]n \left(1 \leqslant n \leqslant 100\right)[/latex]. Каждая из следующих [latex]n[/latex] строк содержит [latex]n[/latex] целых чисел, не превышающих по модулю 2 [latex]\cdot[/latex] 10⁹ — числа в ячейках таблицы.

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

Для каждого столбца в отдельной строке выведите YES, если в нем есть число [latex]x[/latex], и NO в противном случае.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2 0 1 0 0	NO YES
2	23 3 23 0 23 21 12 23 11 13 23	YES NO YES
3	7 1 0	NO
4	13 3 13 33 75 23 45 31 13 13 13	YES YES YES

Код

#include <iostream>

using namespace std;

int arr[101];

int main() {

long long x, c;

cin >> x;

int n, i = 0;

cin >> n;

while (cin >> c) {

if (c == x) {

arr[i % n]++;

}

i++;

}

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

if (arr[i] > 0) {

cout << "YES" << endl;

}

else {

cout << "NO" << endl;

}

return 0;

}

Решение

Для решения этой задачи заведём массив на [latex]n[/latex] элементов, в котором каждый элемент будет счётчиком соответствующего столбца. В цикле будем смотреть все элементы и, если нам встретится элемент [latex]x[/latex], увеличим соответствующий счётчик. Затем в другом цикле смотрим счётчик каждого столбца, если он больше нуля, то выводим YES, иначе — NO.

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

Михаил Бутник

e-olymp 4752. Кинотеатр

28/03/2019 by Анна Неделева

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера n × m, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

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

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

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

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

В первой строке заданы числа $n$ и $m$ $(1 ≤ n, m ≤ 1000)$.

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

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

Тесты

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

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

#include <iostream>

using namespace std;

int main() {

int arr[1000][1000], n, m, count1 = 1, count2 = 1, result = 0;

cin >> n >> m;

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

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

arr[i][j] = count1++;

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

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

if (arr[i][j] == count2) result++;

count2++;

}

cout << result << "\n";

}

Код программы с линейным массивом

#include <iostream>

using namespace std;

int main() {

int arr[1000 * 1000], n, m, result = 0;

cin >> n >> m;

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

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

arr[i * m + j] = i * m + j;

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

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

if (arr[i * m + j] == j * n + i) result++;

cout << result << "\n";

}

Код программы без массива

#include <iostream>

using namespace std;

int main() {

int n, m, result = 0;

cin >> n >> m;

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

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

if (i * m + j == j * n + i) result++;

cout << result << "\n";

}

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

Для решения задачи проверяем значения до пересадки и после, если они совпадут соответственно, то инкрементируем счётчик. А в конце выводим результат.

Ссылки

Анна Неделева

e-olymp 8530. Печать матрицы

26/02/2019 by Лиза Севастьянова

Задача

Условие

Задана матрица $n \cdot n$ — назовем ее $[1..n] \cdot [1..n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1..r] \cdot [1..c]$ массив ($r$ строк и $c$ столбцов исходного массива).

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

Первая строка содержит число $n (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \cdot n$. Последняя строка содержит два числа $r$ и $c$ $(1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

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

Выведите матрицу $r \cdot c$.

Тесты

№	Входные данные	Выходные данные
1	4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 3 2	1 2 5 6 9 1
2	5 18 25 34 44 -43 54 65 75 85 -32 95 15 25 35 -3 -4 15 -6 37 0 44 43 23 3 -12 4 3	18 25 34 54 65 75 95 15 25 -4 15 -6
3	2 0 -1 23 69 1 1	0
4	3 1 2 3 -4 -5 -6 7 8 9 3 1	1 -4 7

Решение

Для решения данной задачи необходимо ввести в массив все имеющиеся данные и вывести необходимые, соответственно заданным параметрам. Можно использовать как одномерные массивы, так и двухмерные.
В реализации с одномерными вводим все данные в массив $n \cdot n$, а затем выводим, используя вложенные циклы. Цикл проходит от $0$ до $r$ и от $(j \cdot n)$ — первого элемент необходимой строки до $(c + j \cdot n)$ — последнего элемента. В реализации с двумерными массивами заводим все данные в один массив и после выводим необходимые.

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

#include <iostream>

using namespace std;

#define N 100

int main() {

int n;

cin >> n;

int arr[N * N];

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

cin >> arr[i];

}

int r, c;

cin >> r >> c;

for (int i = 0; i < c * r; i++) {

cout << arr[((i / c) * n) + (i % c)] << ((1+i) % c == 0? "\n" : " ");

}

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

#include <iostream>

using namespace std;

#define N 100

int main() {

int n, r, c;

cin >> n;

int arr[N][N];

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

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

cin >> arr[i][j];

}

cin >> r >> c;

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

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

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

} cout << endl;

}

return 0;

}

Ссылки

Лиза Севастьянова

e-olymp 7504. Три прямоугольника

19/01/2019 by Николай Козиний

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

Задача

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

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

Одно число — количество закрашенных клеток

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	0 0 1 1 1 1 2 2 0 0 2 2	4
2	2 -2 -2 2 -1 -1 1 1 40 40 41 41	17
3	-1 2 2 -1 1 0 4 2 1 0 3 6	21
4	-100 -100 -99 -99 100 100 99 99 -100 -100 100 100	40000
5	3 0 4 1 1 0 3 3 1 0 3 3	7

Решение

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

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

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

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

#include <iostream>

#include <cmath>

using namespace std;

struct point{int x;int y;};

struct rect{point a;point b;};

rect getrect(point a, point b, rect c){

if(a.x > b.x)swap(a.x,b.x);

if(a.y > b.y)swap(a.y,b.y);

c.a = a;

c.b = b;

return c;

}

rect getrekt(rect c){

point a,b;

cin >> a.x >> a.y >> b.x >> b.y;

return getrect(a,b,c);

}

int area(rect sq){return (sq.b.x - sq.a.x) * (sq.b.y - sq.a.y);}

rect cross(rect l,rect r){

rect cr;

point a1,b1;

a1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:max(l.a.x,r.a.x));

a1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:max(l.a.y,r.a.y));

b1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:min(l.b.x,r.b.x));

b1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:min(l.b.y,r.b.y));

return getrect(a1,b1,cr);

}

int farea(rect *q){

return area(q[0]) + area(q[1]) + area(q[2]) - area(cross(q[0],q[1])) - area(cross(q[0],q[2])) - area(cross(q[2],q[1])) + area(cross(q[0],cross(q[1],q[2])));

}

int main() {

rect *q = new rect [3];

for(int i = 0;i < 3;i++)q[i] = getrekt(q[i]);

cout<<farea(q);

}

Решение. Многомерные массивы

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

#include <iostream>

#include <cmath>

#define N 100

using namespace std;

int main() {

int rect[3][4];

int field[2*N][2*N];

int count = 0;

for(int i = 0;i < 2*N;i++)for(int k = 0;k < 2*N;k++)field[i][k] = 0;

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

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

cin >> rect[i][k];

rect[i][k] = rect[i][k] + N;

}

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

for(int i = min(rect[k][0],rect[k][2]);i < max(rect[k][0],rect[k][2]);i++){

for(int j = min(rect[k][1],rect[k][3]);j < max(rect[k][1],rect[k][3]);j++){

field[i][j]=1;

}

for(int i = 0;i < 2*N;i++){

for(int k = 0;k < 2*N;k++){

if(field[i][k] & 1)count++;

}

cout<<count;

}

Код задачи на ideone
Еще один код задачи на ideone(многомерные массивы)
Засчитанное решение на e-olymp

Николай Козиний

e-olymp 94. Problem of prime numbers!

10/01/2019 by Руслан Масальский

The task is taken from e-olymp

Task

One of the most difficulties of an instructor is question design for the final-term exam. Dr. Ghavamnia teaches “Fundamentals of Algorithms” at University of Isfahan (UI) and has designed a good practical algorithmic problem for his exam. He wants that students use all of their algorithmic skills to code this problem as best and efficient as they can. The problem is as follows: a ring is composed of [latex]N[/latex] circles numbered from [latex]1[/latex] to [latex]N[/latex] as shown in diagram. You are given [latex]N[/latex] integer numbers. Put these numbers into each circle separately with the condition that sum of numbers in three adjacent circles must be a prime.
Each test case may have several solutions and your task is to find the one with minimum weighted sum. Weighted sum is defined as the sum of products of each number in circle by the sequence number of that circle. For instance, the weighted sum in above diagram is [latex]36[/latex] (and also it is the minimum).

Input

The first line of input contains a single integer, the number of test cases. Following, there is one line for each test case. Each test case begins with one integer, [latex]N[/latex] ([latex]3 \leq N \leq 15[/latex]), which is the number of circles. Next [latex]N[/latex] integers are the given numbers to put in circles (all between [latex]1[/latex] and [latex]100[/latex], inclusively).

Output

There should be one line for each test case in output. If there’s no way for building the ring, the word «impossible» should be outputted, or otherwise, a single integer which is the minimum weighted sum.

Tests

№	Inputs	Outputs
1	5 4 1 3 7 9 4 1 1 3 5 15 11 6 2 3 2 14 1 2 10 7 2 2 3 6 2 9 1 1 1 2 2 2 2 2 2 7 1 2 3 4 5 6 7	36 imposible 396 72 imposible

Code

#include <iostream>

#include <vector>

#include <string>

using namespace std;

int length;

vector <int> input(16);

vector <int> output(16);

bool used[16];

const int SIZE = 350;

bool isPrime[SIZE];

const int INF = 2147483647;

long min;

bool prime(int k) {

return isPrime[k];

}

void init() { // initialization for Sieve of Eratosthenes

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

isPrime[i] = true;

}

for (int i = 2; i * i < SIZE; i++) {

if (isPrime[i]) {

for (int j = i * i; j < SIZE; j += i) {

isPrime[j] = false;

}

void perm(int pos) {

if (pos == length) {

if (!prime(output[pos - 1] + output[0] + output[1]) || !prime(output[pos - 1] + output[pos - 2] + output[0])) {

return;

}

for (int z = 0; z < length; z++) {

long temp = 0;

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

temp += i * output[i - 1];

}

if (temp < ::min) {

::min = temp;

}

int k = output[0];

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

output[j] = output[j + 1];

}

output[length - 1] = k;

}

return;

}

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

if (!used[i]) {

output[pos] = input[i];

if (pos >= 2 && !prime(output[pos] + output[pos - 1] + output[pos - 2])) {

continue;

}

used[i] = true;

perm(pos + 1);

used[i] = false;

}

int main() {

string f;

init();

int t;

cin >> t;

for (int j = 0; j < t; j++) {::min = INF;

scanf("%d", &length);

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

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

}

output[0] = input[0];

used[0] = true;

perm(1);

f = (::min == INF ? "impossible" : to_string(::min));

printf("%s\n", f.c_str());

}

return 0;

}

Solution

We need all permutations of our array and if permutation suits us update [latex]min[/latex] value. To check if number is prime I use Sieve of Eratosthenes. To get all permutation I use recursive function which works in this way:
We accumulate an array in all possible ways. What we do:

Fixed empty position in array with a value
Remember that we used this value
Find all permutations of array with size which is smaller by 1
Forget that we used this value (to use it in next permutations)

We stop when we accumulate an array with size we need and check if this permutation suits us(if sum of all triples of this circle are prime). If yes update answer(if it is less than answer). So if we send this solution to server we will get time limit. We need to reduce permutations which do not suit us. To speed up our program we can reduce amount of permutations in this way: if we find out that sum of previous three numbers, which are fixed, is not prime, we do not need to continue this branch of recursion. Really if in our array we found that one sum of three number is not prime we do not need to accumulate this array further. But anyway we get time limit.
Let’s see the differences in complete array where any some of three numbers is prime number.
Input: 8 2 1
Let’s find all suitable permutations:

8 2 1
2 8 1
2 1 8
1 8 2
8 1 2
1 2 8

As you can see first three are different with shifts. Last three are also different with shifts. So we can fix one element find all permutations we need with less by 1 amount of elements and then shift all elements of every array to get all possible permutations which are correct as you can see above (1,2,3) (4,5,6). In the worst case it will work not for [latex]15![/latex] but for [latex]14![/latex]. And now we get Accept.
The complexity is [latex]O(n!)[/latex]
Why I did not get time limit at all (because of complexity)? In task said than amount of test which works with [latex]O(n!)[/latex] can be huge. But who will make so many tests? In our case there are near 5 tests in one.

Links

ideone
e-olymp

Руслан Масальский

Прикладная математика. Одесский национальный университет им. Мечникова

e-olymp 4751. Диагонали

08/01/2019 by Александр Мога

Задача

В квадратной таблице [latex] n × n [/latex] подсчитать сумы чисел, стоящих на главной и побочной диагоналях.

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

Вводится число [latex]n (1 \le n \le 500)[/latex], а затем матрица [latex] n × n [/latex]. Элементы матрицы — числа по модулю не больше [latex]10^5[/latex].

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

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

Вывести сумму чисел сначала на главной, а затем на побочной диагонали.

Тесты

Вход	Выход
4 134 475 30 424 303 151 419 235 248 166 90 42 318 237 184 36	411 1327
7 -59 21 7 5 12 868 -565 32 19 52 3 7 11 0 3 -123 -52 -99 -857 -4621 -561 11 232 86 652 46 3244 572 857 -1242 -6767 923 -575 12 1 552 232 2 63 -76 23 0 12 34 87 20 -7 767 959	967 -7282
3 1 45 82 96 29 90 757 23 12	42 868
2 12 32 99 71	83 131
5 12 32 54 76 12 95 23 21 123 0 65 32 1 773 992 5 32 155 866 912 134 44 74 11 23	36 136

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

#include <iostream>

using namespace std;

int main() {

int n;

int m=0;

int c=0;

cin >> n;

int ** x = new int * [n];

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

x[i] = new int[n];

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

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

cin >> x[i][j];

}

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

m+=x[i][i];

c+=x[i][n-1-i];

}

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

delete []x[i];

delete []x;

cout << m << " " << c;

return 0;

}

Решение

Создаем динамический массив.

Чтобы найти сумму главной диагонали берём, лишь те элементы массива, в которых номер строки и столбца равны.

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

Ссылки

e-olymp

ideone

Александр Мога