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 2667. Змейка

Задача

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

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

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

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

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

Тесты

Входные данные Выходные данные
$5 \ 2 \ 3 \ 1$ $4$
$6 \ 3 \ 4 \ 3$ $9$
$10 \ 5 \ 10 \ 2$ $48$

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

Решение

Читаем входные данные и объявляем массив $n$ на $m$, $num = 0$ — число элемента в этом массиве, далее будем заполнять его в цикле. Делаем перебор строк, для каждой строки есть число $j$ — номер элемента (в текущей строке), с которого мы записываем числа и число $dir$ — направление, в которое мы эти числа записываем (оно у нас 1 или -1). Если строка четная, то начинаем движение слева направо, если нечетная, то справа налево. Далее перебираем каждый элемент строки и записываем ему свой номер. В ответе выводим выбранный элемент.

Ссылки

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

Код решения задачи ideone

e-olymp 907. Первый не больший чем 2.5

Задача

Задан массив вещественных чисел. Найти первый элемент массива, значение которого не превышает 2.5.

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

В первой строке задано количество элементов массива $n\left ( 0 < n \leq 100 \right )$. В следующей строке задано $n$ вещественных чисел.

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

Вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. В случае отсутствия такого элемента в массиве вывести «Not Found» (без кавычек).

Тесты

Входные данные Выходные данные
$5 \\ 6 \ 7.5\ 2.1 \ 2.0 \ 0$ $3 \ 2.10$
$5 \\ 6 \ 7.5 \ 5.1 \ 7.0 \ 80$ $Not \ Found$
$7 \\ 5 \ 4.7 \ 50 \ 8.9 \ 2.7 \ 3 \ 1.5$ $7 \ 1.5$

Решение задачи с помощью потоковой обработки

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

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

Будем просматривать все веденные элементы и для каждого осуществлять проверку, если элемент не превышает 2.5, тогда в ответе выводим в одной строке сначала индекс найденного первого указанного элемента и его значение с 2 десятичными знаками. Если же такого элемента нет, выводим на экран $Not \ Found.$

Решение задачи с помощью массивов

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

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

Введем обозначения: $x$ – имя массива, $n$ – количество элементов в массиве, $i$ – индекс элемента массива. Нам необходимо просмотреть весь массив. Если значение просматриваемого элемента не превышает 2,5, то в ответе вывести в одной строке сначала индекс найденного первого указанного элемента массива и его значение с 2 десятичными знаками. Если же такого элемента в массиве нет, вывести $Not \ Found.$

Ссылки

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

Код решения с помощью потоковой обработки на ideone

Код решения с помощью массивов на ideone

e-olymp 50. Разрезанное число

Задача

Василий на бумажке в виде полоски написал число, кратное $d$. Его младший брат Дмитрий разрезал число на $k$ частей. Василий решил восстановить написанное число, но столкнулся с проблемой. Он помнил только число $d$, а чисел, кратных $d$, можно сложить несколько.
Сколько чисел, кратных числу $d$, может составить Василий, если составляя исходное число, он использует все части.

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

В первой строке записано два числа $d$ и $k$ $\left(1 ≤ k < 9, 1 ≤ d ≤ 100\right)$. В следующих $k$ строках находятся части числа. Количество цифр в разрезанных частях не превышает $10.$

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

Количество разных чисел.

Тесты

Входные данные Выходные данные
$5$ $3$
$13$
$85$
$45$
$4$
$11$ $2$
$1$
$111$
$1$
$11$ $3$
$11$
$8$
$11$
$0$
$71$ $8$
$4018916609$
$7495223237$
$3405637482$
$3166003637$
$8998228133$
$1141886496$
$9124347310$
$7736090711$
$584$

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

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

Согласно свойствам остатков от деления, остаток от деления суммы двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает сумма их остатков. А также остаток от деления произведения двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает произведение их остатков.
Значит, мы можем решить обычным перебором, но на каждом действии берем остаток от деления на $d$.
Также части чисел могут совпадать, в связи с чем необходима проверка на то, что мы составленное число еще не записывали. Для этого мы будем хешировать полученное число следующим образом: последнюю цифру умножим на $101^0$, предпоследнюю — на $101^1$ и так далее.
Если наш конечный результат делится на $d$ без остатка и если составленное число встречается в первый раз, то увеличиваем счетчик на $1$.

Ссылки

Условие задачи на e-olymp
Код решения

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 634. Вклад «Антикризисный»

Задача

Постоянные клиенты одного очень крупного банка (ООКБ) недавно получили возможность открыть новый вклад — «Антикризисный». Этот вклад отличается непростой схемой начисления процентов, поэтому вам, как единственному сотруднику ИТ-отдела банка, было поручено написание программы, которая будет вычислять сумму вклада с начисленными процентами.

Вклад «Антикризисный» может быть открыт на любой срок, но дата окончания вклада должна быть не позже $31$ декабря $2009$ года, процентная ставка по вкладу составляет $p$ процентов годовых. Это означает, что если в начале некоторого периода в $d$ дней, в течение которого сумма вклада не менялась, сумма вклада составляла $x$ рублей, то по окончании этого периода она будет составлять $x\cdot\left(1+\frac{p}{100}\cdot\frac{d}{365}\right)$.

Начисление процентов на вклад осуществляется ежемесячно, в последний день месяца (или в последний день действия вклада), при этом сумма процентов присоединяется ко вкладу. Таким образом, если на первое мая сумма вклада составляла $x$ рублей, то $31$ мая ко вкладу будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{31}{365}\right)$ рублей, и на первое июня сумма вклада составит $x\cdot\left(1+\left(\frac{p}{100}\right)\cdot\left(\frac{31}{365}\right)\right)$, а в июне проценты будут начисляться уже на эту сумму.

Если же последний день вклада был $20$ мая, то в этот день ко вкладу будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{20}{365}\right)$ рублей, а сумма вклада, которую получит клиент банка составит $x\cdot\left(1+\left(\frac{p}{100}\right)\cdot\left(\frac{20}{365}\right)\right)$. Аналогично выполняются расчеты и для случая, когда вклад был открыт не в первый день месяца. Так, например, если вклад был открыт $18$ февраля, то $28$ февраля к сумме вклада будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{11}{365}\right)$ рублей, а если же он был открыт $28$ февраля, то в тот же день $28$ февраля к сумме будет присоединено $x\cdot\left(\frac{p}{100}\right)\cdot\left(\frac{1}{365}\right)$ рублей.

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

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

Первая строка входного файла содержит три целых числа: исходную сумму вклада $x$, процентную ставку $p$ и длительность вклада $d \left(1 ≤ x ≤ 100000, 1 ≤ p ≤ 200, 1 ≤ d ≤ 365\right)$. Вторая строка входного файла содержит дату открытия вклада в формате «день-месяц-год». День и месяц обозначаются числами, при этом у чисел, меньших десяти, присутствуют ведущие нули. Гарантируется,что вклад открыт в $2009$ году, и дата его окончания также находится в $2009$ году.

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

В выходной файл выведите ответ на задачу c точностью $6$ знаков после десятичной точки.

Тесты

# Входные данные Выходные данные
1 1000 10 27
18 07 2009
1007.410921
2 1000 12 70
29 06 2009
1023.172779
3 1000 12 37
17 08 2009
1012.200053
4 1000 15 37
21 10 2009
1015.253781
5 1000 15 85
12 08 2009
1035.351224

Код

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

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

Ссылки

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

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

Задача

Заполнить массив размера $n × n$ единичками по спирали (см. пример).

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

Одно нечетное натуральное число $n$, не превышающее $50$.

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

Вывести построенную спираль. Центральная клетка должна содержать $0$.

Тесты

Входные данные Выходные данные
[latex]7[/latex] [latex]1111111 \\ 0000001 \\ 1111101 \\ 1000101 \\ 1011101 \\ 1000001 \\ 1111111[/latex]
[latex]1[/latex] [latex]0[/latex]
[latex]3[/latex] [latex]111 \\ 001 \\ 111[/latex]
[latex]5[/latex] [latex]11111 \\ 00001 \\ 11001 \\ 10001 \\ 11111[/latex]

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

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

Для начала мы верхнюю, нижнюю и правую грани зразу заполним единицами. Далее идем поочередно в четырех направления (вверх, вправо, вниз, влево). Мы имеем два параметра: ширину и высоту заполняемого единицами отрезка (ширине соответствуют движения вправо и влево, высоте — вверх и вниз). На каждом шаге уменьшаем соответствующий заполняемый отрезок (ширину или высоту) на $2$ и проверяем, чтобы он был больше $0$, иначе заканчиваем. На протяжении всего решения храним еще два параметра: координаты точки, откуда начнем следующий шаг.
P.s. На сайте www.e-olymp.com это решение не проходит полностью из-за неправильности $5$-го теста. У них в $5$-ом тесте центральный элемент $1$, что противоречит условию.

Ссылки

Условие задачи на e-olymp
Код решения

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

Задача

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

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

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

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

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

Тесты

Входные данные Выходные данные
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
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
6
30 -10 30 -69 -84 75
-3 -39 60 15 75 -74
36 68 35 23 25 -44
16 42 83 15 59 -18
71 43 35 -81 -38 51
37 -49 55 26 6 33
4 5
30 -10 30 -69 -84
-3 -39 60 15 75
36 68 35 23 25
16 42 83 15 59

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

Решение

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

  • первый цикл ($17$ строка кода) будет отвечать за количество выводимых строк матрицы — по условию, нужно вывести первые $r$ строк;
  • второй цикл ($18$ строка кода) будет отвечать за количество выводимых столбцов матрицы — по условию, нужно вывести первые $c$ столбцов.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone
Решение этой же задачи на C++