e-olymp 2669. Поворот

11/06/2018 by Иван Мясоедов

Поворот

Дан массив [latex]n[/latex] × [latex]m[/latex]. Требуется повернуть его по часовой стрелке на [latex]90[/latex] градусов.

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

В первой строке даны натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 50)[/latex]. На следующих [latex]n[/latex] строках записано по [latex]m[/latex] неотрицательных чисел, не превышающих [latex]109[/latex] — сам массив.

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

Выведите перевернутый массив в формате входных данных.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 2 1 2 3 4	2 2 3 1 4 2
2	3 3 1 2 3 4 5 6 7 8 9	3 3 4 7 1 8 5 2 9 6 3
3	3 4 4 5 7 8 3 6 8 7 2 2 4 5	4 3 2 3 4 2 6 5 4 8 7 5 7 8
4	1 2 5 4	2 1 5 4
5	1 1 2	1 1 2

ВХОДНЫЕ ДАННЫЕ

ВЫХОДНЫЕ ДАННЫЕ

2 2

1 2

3 4

2 2

3 1

4 2

3 3

1 2 3

4 5 6

7 8 9

3 3

4 7 1

8 5 2

9 6 3

3 4

4 5 7 8

3 6 8 7

2 2 4 5

4 3

2 3 4

2 6 5

4 8 7

5 7 8

1 2

5 4

2 1

1 1

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int ** x = new int *[n];
    for (int i = 0; i < n; i++) 
        x[i] = new int[m];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) 
            cin >> x[i][j];
    cout << m << " " << n;
    cout << endl;
    for (int j = 0; j < m; j++){ 
        for (int i = n - 1; i >= 0; i--)
            cout << x[i][j] << " ";
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

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

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

x[i] = new int[m];

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

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

cin >> x[i][j];

cout << m << " " << n;

cout << endl;

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

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

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

cout << endl;

}

return 0;

}

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

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

Задача на сайте e-olymp
Код решения в Ideone

Related Images:

e-olymp 2261. Защита королевства

20/05/2018 by Иван Мясоедов

Защита королевства

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

Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [latex]12[/latex].
Помогите Теодору написать программу, вычисляющую штраф в заданной позиции.

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

Первая строка содержит три целых числа: [latex]w[/latex] — ширина сетки, [latex]h[/latex] — высота сетки и [latex]n[/latex] — количество арбалетных башен [latex](1 ≤ w, h ≤ 40000; 0 ≤ n ≤ min(w, h))[/latex].

Каждая из следующих n строк содержит два целых числа [latex]x_i[/latex] и [latex] y_i[/latex] — координаты клетки с башней [latex](1 ≤ x_i ≤ w; 1 ≤ y_i ≤ h)[/latex].

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	10 10 3 1 1 2 2 3 3	49
2	15 15 4 4 4 5 5 7 8 13 15	30
3	30 30 5 13 14 16 27 29 30 5 5 10 15	132
4	100 100 2 1 1 100 100	9604
5	3 3 3 1 1 2 2 3 3	0

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

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

int main() {
    int x_max, y_max, n, a=0, b=0;
    cin>>x_max>>y_max>>n;
    int *x=new int[n+2];
    int *y=new int[n+2];
    for(int i=1;i<n+1;i++) 
       cin>>x[i]>>y[i];
    x[0] = y[0] = 0;
    x[n+1] = x_max + 1; 
    y[n+1] = y_max + 1;
    sort(x, x + n+1);
    sort(y, y + n+1);
    for(int i=0; i<n+1; i++){ 
       if(x[i+1]-x[i]>a) a=x[i+1]-x[i];
       if(y[i+1]-y[i]>b) b=y[i+1]-y[i];
    }
    cout<<(a-1)*(b-1);
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int x_max, y_max, n, a=0, b=0;

cin>>x_max>>y_max>>n;

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

int *y=new int[n+2];

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

cin>>x[i]>>y[i];

x[0] = y[0] = 0;

x[n+1] = x_max + 1;

y[n+1] = y_max + 1;

sort(x, x + n+1);

sort(y, y + n+1);

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

if(x[i+1]-x[i]>a) a=x[i+1]-x[i];

if(y[i+1]-y[i]>b) b=y[i+1]-y[i];

}

cout<<(a-1)*(b-1);

return 0;

}

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

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

Для решения данной задачи нужно создать два массива в [latex]x[/latex] и [latex]y[/latex] (в первом будут находится [latex]x_i[/latex] координаты, а во втором [latex]y_i[/latex]) размера на [latex]2[/latex] больше чем количество заданных башен, так как нужно учитывать рамки поля, для чего достаточно добавить две башни c координатами [latex]\left(0;0\right)[/latex] и [latex]\left(x_{max}+1; y_{max}+1\right).[/latex] Далее нужно отсортировать эти массивы и найти максимальную разность между соседними элементами ([latex]a[/latex] — максимальная разность между [latex]x_i[/latex] элементами, [latex]b[/latex] — максимальная разность между [latex]y_i[/latex]). Далее, по формуле [latex]\left(a-1\right)\cdot\left(b-1\right)[/latex] находим площадь самого большого незащищенного прямоугольника, которая равна количеству клеток в нем, что и является ответом задачи.

Задача на сайте e-olymp
Код решения в Ideone

Related Images:

e-olymp 921. Отрицательные элементы

13/05/2018 by Иван Мясоедов

Отрицательные элементы

Задан одномерный массив вещественных чисел длины [latex]n[/latex]. Определить сумму и количество отрицательных элементов в массиве.

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

В первой строке задано количество элементов массива [latex]n[/latex] ([latex]n[/latex] ≤ [latex]100[/latex]). В следующей строке через пробел задано [latex]n[/latex] вещественных чисел — элементы массива, значения которых не превышают по модулю [latex]100[/latex].

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

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

Тесты

#	ВХОДНЫЕ ДАННЫE:	ВЫХОДНЫЕ ДАННЫЕ:
1	5 6 -7.5 2.1 -2.0 0	2 -9.50
2	2 -1 -2	2 -3.00
3	6 1 1 1 1 1 1	0 0.00
4	7 -1.99 -5.34 9 6.43 -6.32 0 -7.43	4 -21.08
5	3 -1.992345 -5.334224 9	2 -7.33

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

#include <iostream>
using namespace std;

int main() {
    int n, m = 0;
    double k = 0;
    cin >> n;
    double *x = new double[n];
    for (int i=0; i<n; i++) 
        cin >> x[i];
    for (int i=0; i<n; i++) {
        if (x[i]<0){
             m++;
             k+=x[i];
         }
    }
    cout.precision(2);
    cout << m << " " << fixed << k;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m = 0;

double k = 0;

cin >> n;

double *x = new double[n];

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

cin >> x[i];

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

if (x[i]<0){

m++;

k+=x[i];

}

cout.precision(2);

cout << m << " " << fixed << k;

return 0;

}

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

Для решения данной задачи я описал две переменные: [latex]m[/latex] типа [latex]int[/latex] и [latex]k[/latex] типа [latex]double[/latex], которые изначально равны [latex]0[/latex]. Цикл ищет в массиве элементы которые меньше [latex]0[/latex]. C каждым найденным отрицательным элементом, [latex]m[/latex] увеличиваться на [latex]1[/latex], а к числу [latex]k[/latex] прибавляется сам элемент.

Задача на сайте e-olymp
Код решения в Ideone

Related Images:

e-olymp 8288. Олимпиада по программированию

30/12/2017 by Иван Мясоедов

Олимпиада по программированию

На АСМ-олимпиаду прибыло [latex]N[/latex] участников. В результате анкетированные члены жури установили, что [latex]A[/latex] участников программируют на Cи, [latex]B[/latex] на Python, [latex]C[/latex] на Pascal, [latex]X[/latex] одновременно знают Cи и Python, [latex]Y[/latex] — Python и Pascal, [latex]Z[/latex] — Cи и Pascal. Имея значения [latex]N, A, B, C, X, Y, Z[/latex] установите количество участников, которые программируют на трёх языках программирования.

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

В одной строке через пробел сем действительных чисел [latex]N, A, B, C, X, Y, Z[/latex] значения которых не превышают [latex]100[/latex].

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

Единственное число – количество участников, которые программируют на трёх языках программирования.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	100 40 50 60 15 20 25	10
2	100 50 60 60 20 40 25	15
3	80 50 40 60 20 30 25	5
4	80 50 40 60 0 0 0	0
5	40 20 30 0 5 0 10	5

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

#include <iostream>
using namespace std;

int main() 
{
    int n, a, b, c, x, y, z;
    cin >> n >> a >> b >> c >> x >> y >> z;
    if (x + y + z == 0) {
        cout << 0;
    }
    else {
        cout << (x + y + z) - (a + b + c - n);
    }
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, a, b, c, x, y, z;

cin >> n >> a >> b >> c >> x >> y >> z;

if (x + y + z == 0) {

cout << 0;

}

else {

cout << (x + y + z) - (a + b + c - n);

}

return 0;

}

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

Алгоритм решения данной задачи состоит в том, чтоб найти разность между числом участников, что одновременно знают по два языка $(X + Y + Z)$, и числом, что показывает на сколько языков больше чем людей (разностью между общим количеством языков и участников) $(A + B + C — N)$. Тем самым, мы найдем количество людей, которые знают одновременно 3 языка. Его также можно объяснить используя диаграмму Эйлера-Венна, на которой отмечено семь областей. Из условия следует, что:

$\begin {cases} x_1 &+ &x_2 &+ &x_3 &+ &x_4 &+ &x_5 &+ &x_6 &+ &x_7 &=N \newline x_1 &+ & & & &&x_4 &+ & & &x_6 &+ &x_7 &=A \newline & & &&x_3 &+ &x_4 &+ &x_5 &+ & & &x_7 &=B\newline & &x_2 &+ & & & & &x_5 &+ &x_6 &+ &x_7 &=C \newline & & &&& &x_4 && && &+ &x_7 &=X \newline & & & & && & &x_5 & & &+ &x_7 &=Y \newline & & & & & & & & & &x_6 &+ &x_7 &=Z \end{cases}$

Нам нужно найти количество участников в [latex]x_7[/latex] области (области одновременного пересечения всех трех кругов). И получается, что:

$(X + Y + Z)-(A + B + C — N)=x_7$

Если же после ввода данных, окажется, что количество людей знающих два языка равно нулю $(X + Y + Z == 0)$, то программа выведет, что людей знающих одновременно три языка также нет.

Задача на сайте e-olymp
Код решения в Ideone

Related Images:

e-olymp 7367. Спортсмен

21/12/2017 by Иван Мясоедов

Задача

Спортсмен в первый день пробежал 10 км. Каждого следующего дня он увеличивал норму на 10% от нормы предыдущего дня. Опредилить через какое найменьшее количество дней спортсмен пробежит сусмарный путь не меньший чем [latex]N[/latex] км.

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

Целое число [latex]N (0 < N≤ 1000)[/latex].

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

Единственное число – количество дней.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	9	1
2	45	4
3	324	16
4	1234	28
5	213213123	153

Код программы №1 (с использованием цикла):

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
   double k = 1, T = 10, N, S = 10;
   cin >> N;
   while (N > T) {
       S = S * 1.1;
       T = S + T;
       k++;
   }
   cout << k;
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double k = 1, T = 10, N, S = 10;

cin >> N;

while (N > T) {

S = S * 1.1;

T = S + T;

k++;

}

cout << k;

return 0;

}

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

Сначала вводим 4 переменные: [latex] k=1 [/latex] ( количество дней ), [latex] T=10 [/latex] ( количество километров которое спортсмен пробежал ), [latex] N [/latex] ( количество километров которое спортсмен должен пробежать ) и [latex] S [/latex] ( количество километров которое спортсмен пробегает в день ). Цикл каждый раз будет прибавлять к расстоянию которое пробежал спортсмен, количество километров которое спортсмен должен пробежать в течение следующего дня, с учетом того, что каждый день он будет пробегать на [latex] 10 [/latex] процентов больше, чем в прошлый день, параллельно увеличивая количество дней, пока [latex] N [/latex] будет больше [latex] T [/latex]. Если же [latex] N [/latex] при вводе изначально будет меньше [latex] T [/latex], то программа выведет, что спортсмену достаточно одного дня.

Время срабатывания программы при [latex]N = 1000[/latex] : [latex]65[/latex] [latex]ms[/latex]

Ссылки

Задача на сайте e-olymp
Код решения в Ideone

Код программы №2(с использованием линейных вычислений):

#include <iostream>
#include <cmath>

using namespace std;

int main() 
{
   double s;
   cin >> s;
   cout << ceil (log(s / 100 + 1) / log(1.1));
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double s;

cin >> s;

cout << ceil (log(s / 100 + 1) / log(1.1));

return 0;

}

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

Также данную задачу можно решить с помощью формулы геометрической прогрессии [latex]S=\frac{b_1(q^n-1)}{q-1}[/latex] из которой нам нужно будет выразить степень [latex] n [/latex] через логарифм при условии того, что по условию задачи мы знаем, что [latex] q=1.1 [/latex] и [latex] b_1=1 [/latex]. И мы получаем, что [latex] \left(n=\log_{1.1}\left(\frac{s}{100}+1\right)\right) [/latex]. При записи логарифма по основанию в С++ мы пользуемся основным свойством логарифмов: [latex] \log_{a}\left(b\right)=\frac{\log_{c}\left(b\right)}{\log_{c}\left(a\right)} [/latex]. Также используем функцию сeil, которая округлит выходное число вверх, до ближайшего целого. ( [latex] S [/latex] — количество километров, которое должен пробежать спортсмен ).