e-olymp задача: 841. Спираль

Условие

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

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

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

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

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

Тесты

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

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

Решение

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

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

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

картинка (1.1)

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

 

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

Задача

В театре [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

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

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

Описываем целочисленный одномерный массив 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].

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

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

По условию заданы количество строк [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 8525. Четные отрицательные в матрице

Задача. Четные отрицательные в матрице

Задана матрица размера $n \times n$. Найдите количество и сумму ее четных отрицательных элементов.

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

Первая строка содержит число $n \left(1 \leq n \leq 100\right)$. Следующие строки содержат матрицу $n \times n$. Элементы матрицы по модулю не больше $100$.

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

Выведите в одной строке количество и сумму четных отрицательных чисел в матрице.

Тесты

Ввод Вывод
1 3
4 -2 5
1 -4 -12
0 1 -3
3 -18
2 5
-100 -100 -100 -100 -100
-100 -100 -100 -100 -100
-100 -100 -100 -100 -100
-100 -100 -100 -100 -100
-100 -100 -100 -100 -100
25 -2500
3 2
0 0
0 0
0 0
4 3
-2 -1 -1
-1 -2 -1
-1 -1 -2
3 -6
5 2
6 8
12 100
0 0
6 4
-25 0 12 5
-29 47 23 15
11 100 -89 20
55 25 42 -12
1 -12
7 2
-12 -12
-12 -12
4 -48

Решение

При обработке двумерного массива я использовал один цикл длиной в $n^2$ витков.
В нём я обращался к элементам с помощью целого и остатка от деления на $n$, то есть изменял второй индекс заново через каждые $n$ элементов, увеличивая, при таком переходе, первый индекс на единицу.
Используя этот приём я избежал вложенных циклов и просматривал элементы в том же порядке, как если бы их использовал.

Код

e-olymp 5057. Спиралька

Задача

Выведите двумерный массив, размерами [latex]n \times n[/latex], заполненный числами от [latex]1[/latex] до [latex]n^2[/latex] по спирали. Числовая спираль начинается в левом верхнем углу и закручивается по часовой стрелке.

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

Одно число [latex]n (1 \leqslant n \leqslant 10)[/latex].

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

Выведите [latex]n^2[/latex] чисел – заполненный по спирали массив.

Тесты

Ввод Вывод
1 1 1
2 2 1 2
4 3
3 3 1 2 3
8 9 4
7 6 5
4 5 1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
5 9 1 2 3 4 5 6 7 8 9
32 33 34 35 36 37 38 39 10
31 56 57 58 59 60 61 40 11
30 55 72 73 74 75 62 41 12
29 54 71 80 81 76 63 42 13
28 53 70 79 78 77 64 43 14
27 52 69 68 67 66 65 44 15
26 51 50 49 48 47 46 45 16
25 24 23 22 21 20 19 18 17

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

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

Все решение задачи сводится к тому, чтобы постепенно заполнять крайние квадраты, «окаймляя» внутренность массива и постепенно сужая диапазон заполнения и длину стороны заполняемого квадрата. В основном цикле вложенными циклами поочередно заполняем строки и столбцы: верхнюю, крайний справа, нижнюю, крайний слева. После «сворачиваем» вправо, когда вложенные циклы заканчиваются и во внешнем(основном) счетчик увеличивается на 1. Полный цикл на n действий делать смысла не имеет в силу того, что, дойдя до половины, массив уже будет полностью заполнен в строках ниже.

Ссылки

e-olymp 8525. Четные отрицательные в матрице

Задача

Задана матрица размера $n \times n.$ Найдите количество и сумму ее четных отрицательных чисел.

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

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

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

Выведите в одной строке количество и сумму четных отрицательных чисел в матрице.

Тесты

Входные данные Выходные данные
1 3
4 -2 5
1 -4 -12
0 1 -3
3 -18
2 2
4 -7
2 9
0 0
3 5
3 4 -5 7 2
1 2 3 4 -2
-2 -4 -6 -8
4 2 -4 0 -1
6 -26
4 4
1 2 3 4
-1 -2 -4 -3
4 -5 -8 -12
-4 -5 -7 0
5 -30

Код

С помощью двумерного массива

Без использования массива

Решение

С помощью массива

Создаем массив.  С помощью цикла for проверяем: если число отрицательное и чётное, то прибавляем его к sum. Выводим количество таких чисел и их сумму.

Без массива

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

Ссылки

e-olymp 936. Формулы Крамера

Условие задачи
Решить систему двух линейных уравнений с двумя неизвестными по формулам Крамера. Система уравнений, приведенная во входных данных, имеет вид:
[latex]\begin{cases} 5x_1+8x_2=11 \\ -3x_1+6x_2=15 \end{cases}[/latex]

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

Выходные данные
Первый корень системы уравнений вывести в первой строке, а второй корень во второй строке с точностью до $0.001$.

Continue reading

e-olymp 2812. Уголок

Задача

Дана прямоугольная доска [latex]M×N[/latex], некоторые клетки в которой вырезаны. Сколькими способами можно поставить на неё «уголок» из трёх клеток так, чтобы все три клетки уголка находились внутри доски и не были вырезаны?

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

В первой строке входного файла даны два числа [latex]M[/latex] и [latex]N[/latex] [latex](1 \leq M, N \leq 100)[/latex], разделённые пробелом. В следующих [latex]M[/latex] строках содержится по [latex]N[/latex] символов в каждой; [latex]i[/latex]-ый символ [latex]j[/latex]-ой из этих строк равен ‘X’ (большая буква икс), если клетка вырезана, и ‘.’ (точка) в противном случае.

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

Выведите одно число — сколько существует способов поставить уголок на данную доску.

Тесты

Входные данные Выходные данные
2 2
..
..
4
2 3
..X
.X.
1
5 4
….
X.XX
….
X..X
..XX
12

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

Решение

Для решения данной задачи создаем динамический массив типа bool x на y. Заполняем соответствующий элемент значением true, когда вводится «.» и значением false в противном случае. Далее увеличиваем значение количества уголков на $1$, если существуют не пустые клетки.

Ссылки

e-olymp
Ideone

e-olymp 1489. Шоколад

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленьких шоколадных долек — прямоугольников $2 \cdot 1$.

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

Помогите Пете поделиться шоколадкой с Машей.

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

В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.

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

В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».

TESTS

Входные данные Выходные данные
2 3
1 1 2
3 3 2
Yes
5 6
1 2 2 3 3 4
1 5 6 7 7 4
8 5 6 9 10 10
8 11 11 9 12 13
14 14 15 15 12 13
No
4 7
1 1 2 5 8 11 6
2 14 4 7 3 9 5
3 7 10 6 13 2 3
4 3 8 12 5 7 7
Yes

Код решения

 

Решение

Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true, и false в обратном случае. Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа bool. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.

Ссылки

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