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

Поворот

Дан массив [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

 

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

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

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

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

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

Задан одномерный массив вещественных чисел длины [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

 

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

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

Для решения данной задачи я описал две переменные: [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

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

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

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

Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф [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

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

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

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

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

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

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

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

На АСМ-олимпиаду прибыло [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

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

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

Алгоритм решения данной задачи состоит в том, чтоб найти разность между числом участников, что одновременно знают по два языка $(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

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

Задача

Спортсмен в первый день пробежал 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 (с использованием цикла):

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

Сначала вводим 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], то программа выведет, что спортсмену достаточно одного дня.

Ссылки

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

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

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

Также данную задачу можно решить с помощью формулы геометрической прогрессии [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] — количество километров, которое должен пробежать спортсмен ).

Ссылки