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

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

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

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

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

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

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

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

e-olymp 7368. Средний балл для фигуристов

25/12/2018 by Алина Гук

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

Задача

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

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей[latex]\left( 0 \lt n \leqslant 10, 0 \lt m \leqslant 100 \right)[/latex] для каждого из фигуристов.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 4 7 8 9 8 10 6 5 5 4 7 9 9 10 7 7 7 7 10 9 8	8.33 5.33 9.00 8.50
2	3 4 1 2 3 3 5 2 7 1 6 9 8 3	2.00 3.00 6.00 8.00
3	10 2 1 2 3 4 5 6 7 8 9 10 1 1 1 2 2 2 3 3 3 4	5.50 2.50

Код программы (Потоковая обработка)

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

cout << fixed << setprecision(2);

int n, m, tmp, sumGl, sumMin, sumMax, valMin, valMax, countMin, countMax;

cin >> n >> m;

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

sumGl = sumMin = sumMax = 0;

valMin = 11;

valMax = 0;

countMin = countMax = 0;

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

cin >> tmp;

sumGl += tmp;

if(tmp < valMin) {

sumMin = tmp;

valMin = tmp;

countMin = 1;

}

else if(tmp == valMin) {

sumMin += tmp;

countMin++;

}

if(tmp > valMax) {

sumMax = tmp;

valMax =tmp;

countMax = 1;

}

else if(tmp == valMax) {

sumMax += tmp;

countMax++;

}

cout << (sumGl - sumMax - sumMin) / (double)(n - countMax - countMin) << " ";

}

return 0;

}

Решение

Читая каждую оценку:

Добавляем оценку к общей сумме;
Если введенная оценка равна минимальной, то добавляем ее к сумме минимальных и увеличиваем счётчик количества минимальных.
Если введенная оценка меньше минимальной, то минимальной становится введённая оценка. Счетчик количества минимальных равен [latex]1.[/latex] Сумма минимальных равна введённой оценке.
Если введенная оценка равна максимальной, то добавляем ее к сумме максимальных и увеличиваем счётчик количества максимальных.
Если введенная оценка больше максимальной, то максимальной становится введённая оценка. Счетчик количества максимальных равен [latex]1.[/latex] Сумма максимальных равна введённой оценке.

Тогда после введения всех [latex]n[/latex] оценок имеем:

[latex]sumMax[/latex] — сумма максимальных оценок.
[latex]sumMin[/latex] — сумма минимальных оценок.
[latex]countMax[/latex] — количество максимальных оценок.
[latex]countMin[/latex] — количество минимальных оценок.
[latex]sumGl[/latex] — общая сумма оценок.

Для нахождения среднего арифметического значения оценок, соответствующего условию будем применять формулу: [latex]S_с = \frac{sumGL-sumMin-sumMax}{n-countMin-countMax}[/latex]

Код программы (Массивы)

#include <iostream>

#include <iomanip>

using namespace std;

double res(int *arr, int len) {

int min,max;

min = arr[0];

max = arr[0];

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

if(arr[i] > max) {

max = arr[i];

}

if(arr[i]<min) {

min = arr[i];

}

int sum = 0;

int count = 0;

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

if(arr[i] != max && arr[i] != min) {

sum += arr[i];

count++;

}

return sum/((double)count);

}

int main() {

int m, n;

cin >> n >> m;

cout << fixed << setprecision(2);

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

int* arr = new int[n];

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

cin >> arr[j];

}

cout << res(arr, n) << " ";

delete[] arr;

}

return 0;

}

Решение

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

Ссылки

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

Код программы на ideone (Потоковая обработка)

Код программы на ideone (Массивы)

Алина Гук

e-olymp 8361. Робот

25/12/2018 by Богдан Подгорный

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

Условие

Движение робота управляется программой. Программа состоит из следующих команд:

[latex]S[/latex] — сделать шаг вперед
[latex]L[/latex] — повернуться на [latex]90°[/latex] влево
[latex]R[/latex] — повернуться на [latex]90°[/latex]вправо

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

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

Одна строка из заглавных латинских букв [latex]S[/latex], [latex]L[/latex], [latex]R[/latex], описывающая программу для робота. Общее число команд в программе не превышает [latex]200[/latex], при этом команд [latex]S[/latex] — не более [latex]50[/latex].

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

Выведите одно число, количество шагов, которое будет сделано (то есть выполнено команд [latex]S[/latex]) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите число [latex]-1[/latex].

Тесты

№	Inputs	Outputs
1	SSLSLSLSSRSRS	5
2	LSSSS	-1
3	LLSRSRSRSLLLLSSSSLRSRSSSRSRSRS	15
4	LLLLLLLL	-1
5	SRLSRLSLRSLRLSLSLSLSSSLRLSSLRSLRSRSRSRSLRLSRLLLLLSRLSRL	7

Код

#include <iostream>

#include <vector>

using namespace std;

struct point{

int x, y;

point(){

x = 0;

y = 0;

}

point(int x1,int y1){

x=x1;

y=y1;

}

bool isequal(point&a, point&b);

}my_point;

bool point::isequal(point&a, point&b){

return a.x == b.x and a.y == b.y;

}

int main() {

int counter = 0, x = 0, y = 0, res = 0;

point a;

char c;

bool stop = false;

vector coor(1);

while(cin >> c and stop == false){

if(c == 'L'){

counter = (counter + 1)%4;

}

else if(c == 'R'){

counter = ((counter - 1) + 4)%4;

}

else{

if(counter == 0){

y++;

}

else if(counter == 1){

x--;

}

else if(counter == 2){

y--;

}

else{

x++;

}

res++;

point a(x,y);

for(int j = 1; j < coor.size();j++){

if(my_point.isequal(coor[j],a)){

stop = true;

}

coor.push_back(a);

}

cout << ((stop == true) ? res : -1);

return 0;

}

Решение

Если представить, что точка старта движения робота имеет координаты [latex]\left(0;0 \right)[/latex], то, соответственно, при движении координата будет изменяться на 1 единицу за шаг. Всего координата может изменяться четырьмя способами: координата [latex]x[/latex] уменьшается на единицу, координата [latex]x[/latex] увеличивается на единицу, координата [latex]y[/latex] уменьшается на единицу, координата [latex]y[/latex] увеличивается на единицу. Тогда можно сделать вывод, что эти 4 состояния можно привязать к счетчику, который будет меняться при каждом повороте налево и направо. Для хранения координат как единого объекта можно создать структуру point. Также необходимо запоминать в массив координаты точки после передвижения вперед для того, чтобы в будущем проверять каждую точку на совпадение с предыдущими, чтобы знать когда прервать проверку строки. В главном цикле при встрече символа «[latex]S[/latex]» делаем проверку на состояние счетчика, чтобы увеличивать соответствующую координату. После изменения координаты необходимо проверить ее на совпадение с предыдущими, если она совпала, то назначаем переменной stop значение true для того, чтобы прервать цикл и вывести результат. Если координата не совпала, то добавляем ее в массив(если использовать vector, это делается с помощью команды push_back(), если обычный массив, то придется создать дополнительную переменную и увеличивать ее каждую встречу команды «[latex]S[/latex]»). Если в итоге робот не вернется в то место, где побывал, то переменная stop останется со значением false и выведется «[latex]-1[/latex]».

Ссылки

Богдан Подгорный

e-olymp 458. Черно-белая графика

24/12/2018 by Юлиана Боурош

Задача

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

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

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

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

Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.

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

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

Тесты

	Входные данные	Выходные данные
1	5 3 01000 11110 01000 10110 00010 10110 0110	11110 11100 11110
2	2 3 010 111 000 101 1010	11 10 10
3	4 4 1111 0101 0000 1110 0011 0101 0111 1111 0011	1111 0101 0000 1110
4	3 6 100011 000111 000000 111011 001100 010101 1000	000 100 110 000 101 010

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

( использован одномерный массив)

#include <iostream>

using namespace std;

bool my_operation (bool a, bool b, bool* res) {

if (!a and !b) return res[0];

else if (!a and b) return res[1];

else if (a and !b) return res[2];

else return res[3];

}

int main() {

int w, h, n;

bool truth_t[4];

cin >> w >> h;

n = w * h;

bool *first_t = new bool [n];

bool *second_t = new bool [n];

char c;

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

cin >> c;

first_t[i] = (c == '1' ? true : false);

}

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

cin >> c;

second_t[i] = (c == '1' ? true : false);

}

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

cin >> c;

truth_t[i] = (c == '1' ? true : false);

}

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

if (i != 0 && i % w == 0)

cout << endl;

cout << my_operation(first_t[i], second_t[i], truth_t);

}

return 0;

}

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

(использован двумерный массив)

#include <iostream>

using namespace std;

bool my_operation (bool a, bool b, bool* res) {

if (!a and !b) return res[0];

else if (!a and b) return res[1];

else if (a and !b) return res[2];

else return res[3];

}

int main() {

int w, h;

bool truth_t[4];

cin >> w >> h;

bool **first_t = new bool *[h];

bool **second_t = new bool *[h];

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

first_t[i] = new bool [w];

second_t[i] = new bool [w];

}

char c;

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

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

cin >> c;

first_t[i][j] = (c == '1' ? true : false);

}

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

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

cin >> c;

second_t[i][j] = (c == '1' ? true : false);

}

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

cin >> c;

truth_t[i] = (c == '1' ? true : false);

}

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

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

cout << my_operation(first_t[i][j], second_t[i][j], truth_t);

}

if (i < h - 1) cout << endl;

}

return 0;

}

Решение

Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции my_operation, которая принимает две переменные a и b булевского типа и булев массив res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений a и b. Результат сравнения выводим.

Ссылки

Одномерный массив
- ideone.com
- e-olymp.com
Двумерный массив
- ideone.com
- e-olymp.com

Юлиана Боурош