e-olymp 8651. Браслети (Bangles)

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

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). ($4 \leq N \leq 300$). У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Код

 

Рішення

Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(1, 2)$ насправді задає зв’язок між першим і другим типом. Маэмо граф, залишилось знайти кількість простих циклів завдовшки у чотири ребра (чотири вершини).
Построївши матрицю суміжності ми на справді побудували матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за один хід.
Нехай за х ходів ми потрапили з вершини $i$ у вершину $k$ рівно $a$ способами, а з вершини $k$ у вершину $j$ рівно $b$ способами. Тоді за $2x$ ходів ми можемо потрапити з вершини $i$ у вершину $j$ через вершину $k$ рівно $ab$ способами, що насправді еквівалентно возведенню матриці суміжності у степінь, яка дорівнює кількості ходів
Тепер за два перемноження отримаємо матрицю де arr[i][j] містить кількість способів дійти від вершини $i$ до вершини $j$ за 4 ходи. Сумма елементів на головній діагоналі майже дає нам потрібний результат. Нам треба відняти ходи такого типу 1-2-1-2-1 та 1-2-3-2-1. Щоб відняти ходи першого типу після першого перемноження поставимо на головній діагоналі нулі, що означатиме що ми не можемо у другому ході повернутися у ту вершину з якої прибули. Для другого типу треба помітити, що ми йдемо по тому шляху, по якому вже йшли тобто якщо мі за два ходи дійшли до певної вершини $a$ способами, то повертаючись назад отримаємо $2a$ способів, але з них рівно $a$ нам не підходять, тому після другого перемноження с діагоналі видаляємо сумму на ряді на моменті коли було зроблено усього $2$ ходи, звісно не враховуючи елементи на головній діагоналі. Ми будували неорієнтований граф тому сумму на діагоналі треба поділити на $2,$ а ще в наших циклах по $4$ вершини, тому треба ще поділити на 4.

Посилання

ideone
e-olymp

e-olymp 685. Сумма на параллелепипеде

Задача

Задана трехмерная таблица чисел [latex]a_{ijt}[/latex], где [latex]1\leq i\leq n[/latex], [latex]1\leq j\leq m[/latex], [latex]1\leq t\leq k[/latex]. Для заданных [latex]l_{x}, l_{y}, l_{z},r_{x}, r_{y}, r_{z}[/latex] найдите

[latex]S_{l_{x}, l_{y}, l_{z},r_{x}, r_{y}, r_{z}}=\sum_{i=lx,j=ly,t=lz}^{i\leq rx,j\leq ry,t\leq rz}a_{ijt}[/latex]

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

В первой строке записаны размеры таблицы — [latex]n, m, k \left ( 1\leq n, m, k\leq 100 \right )[/latex]. Далее записано [latex]n[/latex] блоков по [latex]m[/latex] строк, в каждой из которых записaно по [latex]k[/latex] чисел [latex]a_{ijt} \left ( 1\leq a_{ijt} \leq 1000 \right )[/latex]. Блоки разделены пустой строкой. В очередной строке записано число [latex]q \left ( 1\leq q\leq 10^{6} \right )[/latex] — количество запросов. В следующих [latex]q[/latex] строках описаны запросы [latex]l_{x_{i}}, l_{y_{i}}, l_{z_{i}}, r_{x_{i}}, r_{y_{i}}, r_{z_{i}}[/latex][latex]\left ( 1 \leq l_{x_{i}} \leq r_{x_{i}} \leq n, 1 \leq l_{y_{i}} \leq r_{y_{i}} \leq m, 1 \leq l_{z_{i}} \leq r_{z_{i}} \leq k \right )[/latex] .

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

Выведите [latex]q[/latex] чисел в отдельных строках — ответы на запросы.

Тесты

Входные данные Выходные данные
1 2 3 5
1 2 3 4 5
5 4 3 2 1
2 3 1 5 41 2 3 4 5
5 4 3 2 1
2 3 1 5 4
5
1 1 1 1 2 2
1 1 1 2 2 2
1 2 3 2 3 4
1 3 4 2 3 5
1 2 4 2 2 5
12
24
22
18
6

Код

Решение

Создаем массивы arr — массив элементов исходной матрицы, и amountArray — массив количества элементов «на префиксе». В первой тройке вложенных циклов for заполняем массив arr. Затем в трех парах вложенных массивов заполняем соответственно первый «этаж» матрицы amountArray, первую строку и первый столбец всех «этажей». Далее, в тройке вложенных циклов for заполняем оставшиеся элементы массива. После, читаем запросы и выводим ответы.

Ссылки

e-olymp 4752. Кинотеатр

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера n × m, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.

prb4752.gif

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

prb4752_1.gif

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

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

В первой строке заданы числа $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

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

Код программы с линейным массивом

Код программы без массива

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

Для решения задачи проверяем значения до пересадки и после, если они совпадут соответственно, то инкрементируем счётчик. А в конце выводим результат.

Ссылки

e-olymp 8651. Браслети (Bangles)

Задача

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). $(4 ≤ N ≤ 300)$. У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Объяснение:

Існує два варіанти з’єднання: $(3,4) – (4,2) – (2,5) – (5,3)$ та $(1,4) – (4,5) – (5,3) – (3,1)$ У сусідніх деталях існують однакові замки. Це також справедливо для першої та останньої(четвертої) деталі.

Тесты

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

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

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

В ячейке $x[u-1][v-1]$ стоит единица тогда и только тогда, когда у нас есть звено, имеющее на одном конце замок номер $u$, а на другом $- v$. Теперь построим таблицу, где будет записано в ячейке $y[u-1][v-1]$ количество их общих пар замков, где $u$ и $v$ это пара замков. Потом в первой таблице будем проходить по каждой строке и искать все возможные пары единиц в столбиках, пусть $u$ и $v$ это индекс выбранных столбиков. И если ячейка $y[u-1][v-1]$ больше единицы, то будем отнимать единицу в этой ячейке, чтобы отбросить случай, когда в браслете первый и четвёртый замок одинаковой. Полученное число в этой ячейке будем добавлять к ответу. А запоминать в эту же ячейку на единицу меньше, чтобы потом при подсчёте результата не посчитать один и тот же браслет два раза. Рассмотрим для наглядности пример: когда дано $5$ типов замков и $7$ типов деталей: $1-3, 1-4, 2-4, 2-5, 3-4, 3-5, 4-5$. То есть для каждой пары запомним количество общих замков, так как нам нужно, чтобы количество общих замков для пар было больше единицы, выпишем для наглядности нужные: $1-5$ имеет $2$, $2-3$ имеет $2$, $3-4$ имеет $2$, $4-5$ имеет $2$ общих замка. В первой строке в первой таблице единственная пара это $3-4$, так как общих замков этой пары больше единицы, то пара нам подходит. То есть варианты браслета $1-3-4-1$ и $1-3-4-5$, поэтому отнимем единицу и получим количество нужных браслетов, то есть один браслет уже есть, это $1-3-4-5$. Смотрим дальше, во второй строке тоже одна пара $4-5$. Варианты получаемый браслетов $2-4-5-2$ и $2-4-5-3$, опять отнимем один вариант и остальные браслеты запомним, то есть браслет $2-4-5-3$. В третей строке получится пара $4-5$, но там один вариант $3-4-5-3$, что не подходит, если бы мы ранее не запоминали на единицу меньше, то сейчас мы бы посчитали второй раз тот же браслет $3-4-5-2$, который уже есть. В итоге мы получили $2$ браслета, то есть $1-3-4-5$ и $2-4-5-3$, что есть верным ответом.

Ссылки

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 8530. Печать матрицы

Задача

Условие

Задана матрица $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

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

Ссылки

e-olymp 7261. Трудный путь

Задача

Вася хорошо выпил и теперь, когда он добрался до своей улицы, он полностью потерял чувство направления. Поскольку он не помнит, с какой стороны его дом, он выбирает направление наобум. Более того, на каждом перекрёстке он с вероятностью $50\%$ продолжает идти вперёд, а иначе разворачивается и идёт назад. Он настолько потерял связь с реальностью, что может даже пройти мимо своего дома и не заметить этого!

Пройдя $n$ кварталов, Вася засыпает прямо на улице. Проснувшись, он задаётся вопросом: какой у него был шанс заснуть рядом с домом? Ведь от перекрёстка, от которого он начал свой путь, до перекрёстка рядом с домом Васи всего $m$ кварталов. Помогите ему.

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

В одной строке содержатся два целых числа $n$ и $m$ [latex](0 \le n , m \le 1000)[/latex].

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

Выведите одно число — вероятность Васи заснуть на перекрёстке рядом со своим домом. Выведите ответ с абсолютной погрешностью не более $10^{-7}$.

Тесты

Входные данные Выходные данные
1 1 0.500000000
10 20 0.000000000
1000 100 0.000169397
16 2 0.174560547
90 44 0.000001273

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

Решение

Закодируем путь Васи последовательностью из 0 и 1. Пусть 1 соответствует движению вправо, а 0 влево. Пусть из $n$ шагов, которые совершил Вася, $k$ шагов он сделал вправо. Тогда $n-k$ шагов он сделал влево.Нас интересует вероятность того, что Вася переместился в одну из сторон (например вправо) на $m$ кварталов. Тогда должно выполняться: $m+n-k=k$откуда $k=\frac{m+n}{2}$.Количество последовательностей длины $n$ с $k$ единицами равно $C_n^k$. Поскольку Вася совершил $n$ перемещений, то у него имеется $2^n$ вариантов выбора различных путей. Следовательно вероятность того что Вася пройдет вправо m кварталов, равна $\frac{C_n^k}{2^n}$, где $k=\frac{m+n}{2}$. Отметим, что искомая вероятность равна 0, если $m+n$ нечетно. В этом случае Вася просто не сможет попасть домой, то есть $m+n=2k$ четно.

Ссылки

e-olymp 1463. На перекрёстке

Задача

Дано таблицу [latex] n \times n [/latex]. Возбуждённостью строки или столбца назовём сумму чисел в нём. Необходимо определить число, находящееся на перекрёстке наиболее возбуждённой строки и наименее возбуждённого столбца. Причём, чем выше будет этот перекрёсток (а среди них левее), тем большей будет вероятность прохождения теста.

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

Первая строка входного файла содержит число [latex]n (1 \le n \le 100)[/latex], последующие $n$ строк содержат саму таблицу. Числа в таблице натуральные и не превышают $100000$.

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

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

В выходной файл выведите единственное число – ответ к задаче.

Тесты

Вход Выход
2
4 3
2 1
3
3
1 1 1
1 1 1
1 1 1
1
4
3 2 5 8
13 32 51 9
12 22 3 17
2 1 1 5
13
2
32 19
65 11
11
3
3 9 2
13 1 0
3 1 7
2

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

 

Решение

Создаем динамический массив, в котором вводим числа.

Отдельно создаем массивы для поиска суммы строк и суммы столбцов. Ищем наиболее возбужденную строку и наименее возбужденный столбец, а также запоминаем их с помощью отдельных переменных. После вводим запомненные «координаты», и получим востребованное нами число.

Ссылки

e-olymp

ideone

 

e-olymp 1485. Серия степеней матриц

Задача

По заданной матрице A размера n×n и положительному целому значению $k$ вычислить сумму $S = A + A^2+ A^3 + … + A^k.$

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

Первая строка содержит три положительных целых числа $n (n ≤ 30)$, $k (k ≤ 10^9)$ и $m (m < 10^4)$. Каждая из следующих $n$ строк содержит $n$ неотрицательных целых чисел меньших $32768$, задающих элементы матрицы $A$ в порядке возрастания строк.

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

Вывести элементы матрицы $S$ по модулю $m$ в таком же виде как и входная матрица $A$.

Тесты

Ввод Вывод
1 2 2 4
0 1
1 1
1 2
2 3
2 4 7 2
3 5 12
10 8 9
2 16 7
1 0 0 0
0 1 0 0
1 1 0 0
0 1 0 0
3 5 10 78
7 6 0 1 6
12 9 1 1 8
1 1 3 1 9
8 5 34 1 7
5 5 5 5 5
2 67 36 32 48
2 6 10 49 65
67 14 58 4 29
64 54 33 45 46
41 4 50 8 55
4 3 2 4
3 3 3
3 3 3
3 3 3
2 2 2
2 2 2
2 2 2
5 5 100 1000
1846 4675 8090 4539 1234
4567 7453 9564 6548 1111
5674 9876 5432 1010 1515
0 478 3 11 0
68303 7777 32767 14 8008
614 7 945 925 381
22 332 981 689 527
351 627 130 686 420
340 628 819 758 629
913 426 396 871 91

Код

Решение

Для решения данной задачи опишем матрицу как структуру и функциями зададим простейшие операции над матрицами — сложение и умножение. Результат обеих функций будем будем брать по модулю $m$, чтоб уменьшить числа, с которыми работаем.

Далее создадим функцию быстрого возведения в степень. $A^k$ представим как $\left(A^2\right)^\frac{k}{2}$ при четном  $k$ и $A × \left(A^2\right)^{\frac{k — 1}{2}}$ в противном случае. Такой алгоритм позволяет значительно уменьшить количество умножений.

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

Все, что еще необходимо сделать — вывести результат по модулю $m$.

Замечание

Тесты на e-olymp требуют отсутствия пробела после последнего столбца.

Ссылки

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

Код задачи на Ideone

e-olymp 7504. Три прямоугольника

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

Задача

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

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

Одно число — количество закрашенных клеток

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

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

После этого задача сводится к написанию функции общей площади. То, что решение, в котором мы просто суммируем площадь трех прямоугольников проходит лишь на один тест, наводит на мысль о том, что мы добавляем площадь пересечений несколько раз. Следовательно, от суммы площадей трех прямоугольников отнимем площадь их пересечения друг с другом и добавим площадь пересечения всех трех(поскольку в случае, если существует пересечение трех, то мы лишний раз отнимаем его площадь).

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

Решение. Многомерные массивы

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

Код задачи на ideone
Еще один код задачи на ideone(многомерные массивы)
Засчитанное решение на e-olymp

e-olymp 2507. Граница

Задача

В международной политике важным понятием является граница между государствами. Нечеткое понимание сторонами того, где проходит граница, может привести к международным конфликтам и даже войнам. В этой задаче ситуация обстоит несколько проще, так как у двух рассматриваемых в задаче государств есть четкое понимание, какая территория принадлежит какому из них. Территория, занимаемая этими двумя государствами, представляет собой прямоугольник размером [latex]h[/latex] на [latex]w[/latex] километров, разбитый на квадраты со стороной в один километр. Каждый из этих квадратов полностью принадлежит либо первому государству, либо второму. Необходимо определить длину границы между двумя государствами. Сторона единичного квадрата считается принадлежащей границе, если по одну сторону от нее лежит квадрат, принадлежащий первому государству, а по другую — принадлежащий второму.

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

Первая строка содержит два целых числа: [latex]w[/latex] и [latex]h \left(1 \leqslant w, h \leqslant 100\right)[/latex] — размеры прямоугольника в километрах. Далее следуют [latex]h[/latex] строк, описывающих территорию. Каждая из них содержит [latex]w[/latex] символов. Если символ равен [latex]A[/latex], то соответствующий единичный квадрат принадлежит первому государству, а если он равен [latex]B[/latex], то второму. Гарантируется, что каждому государству принадлежит хотя бы один квадрат. Территории каждого из государств представляют собой связные области.

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

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

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5 6
AAABB
ABBBB
AAABB
AAAAB
AAAAB
AABBB
13
2 4 3
AAAA
AAAA
AAAB
2
3 5 9
BBBBB
ABBBB
AABBB
AAABB
AAAAB
AAABB
AABBB
ABBBB
BBBBB
15
4 2 1
AB
1
5 6 5
AABBBB
BBBBBB
BBBAAA
AAAAAA
AAAAAA
10

Код

Решение

Занесем прямоугольную область в многомерный массив символов. Рассмотрим символ x[i][j]. Если он не совпадает с x[i + 1][j], то между ними имеется граница длины 1 (снизу от x[i][j] проходит граница). Аналогично, если x[i][j] не совпадает с x[i][j + 1], то между ними имеется граница длины 1 (справа от x[i][j] проходит граница). Остается перебрать все символы и подсчитать для них количество нижних и правых границ.

Запустить код (ideone) можно здесь
Задача на E-olymp

e-olymp 45. Топливо

Задача

$N$ котелень одинаковой мощности соединены системой трубопроводов из $M$ труб для перекачки топлива. На $09:00$ утра оказалось, что фактические запасы топлива $A_{k}$ тонн $(k=1..N)$ таковы, что в одной из котелень его значительно меньше нормы $B$ тонн, а на остальных — достаточно, либо с избытком.

Суммарные запасы топлива позволяют исправить ситуацию, если перераспределить топливо. В каждый момент времени из $N$ насосов могут работать $0$ или $2$ (в соседних котельных, перекачивающих и принимающих топливо), при этом перекачка одной тонны топлива на $1$ км занимает $C$ минут.

Через какое наименьшее время $T$ минут эта работа будет выполнена?

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

В первой строке заданы 4 числа $N$,$M$, $B$,$C$. Во второй — массив значений $A_{1..N}$. Далее идут $M$ строк — пары номеров котелень и длины труб между ними. Все данные — неотрицательные целые числа, не превышающие $50$.

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

Единственное число — искомое время.

Тесты

5   5   4   6
5  4  8  1  6
1  2  3
2  3  5
2  4  2
3  4  6
3  5  4
102
8 10 8 10
8 11 8 0 8 12 8 12
7 8 2
7 6 4
6 2 3
2 1 4
2 3 1
3 1 2
1 5 9
3 5 6
3 4 5
4 5 2
690
11 10 9 5
9 9 9 9 4 9 12 10 10 9 13
3 1 9
1 2 5
2 8 6
2 7 4
1 4 8
4 5 4
4 6 8
1 9 6
9 10 3
10 11 3
520
2 1 3 1
0 6
1 2 10
30
50 50 43 50
44 44 44 45 2 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 44 44 45 43 48 49 46 45 48 44 44 44 45 43 48 49 46 45 48
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1
39 40 1
40 41 1
41 42 1
42 43 1
43 44 1
44 45 1
45 46 1
46 44 1
46 48 1
48 49 1
49 50 1
50 1 1
8400
3 3 1 2
3 0 1
1 3 1
2 3 2
1 2 4
6

Решение 1

Решение 2

 Объяснение 1

Вряд ли было бы понятно, если бы я начал сейчас здесь подробно объяснять код. Поэтому, пояснение именно кода я оставлю по этой ссылке, а тут попробую объяснить идею.

Идея решения сама по себе, думаю, достаточно проста: по сути, простой перебор всех вариантов и нахождение наиболее подходящего. Точнее, как бы строится дерево от котла, где недостаёт топлива, и идёт вычисление расстояния до котла, где есть свободное топливо (по веткам связанных с ним котлов). Несколько более сложная, пожалуй, её реализация. В данном решении я воспользовался рекурсивной функцией, которая возвращает либо расстояние до ближайшего котла, откуда можно взять топливо (общее расстояние- то есть все промежуточные котлы, через которое перекачивается топливо, учитываются), либо возвращает $-1$, что говорит о том, что таких котлов (в данной ветке) нет.

Объяснение 2

И снова, сомневаюсь, что мне тут стоит описывать идею решения. А идея — это алгоритм Дейкстры, и вряд ли я сейчас сделаю объясню его лучше этих сайтов. Поэтому я лучше просто  оставлю ссылки на них и на википедию. Отмечу только разницу между переменными $n$ и $visit$ в структуре. $visit$- характеризует вершину, буквально, как посещённую или нет. То есть, рассматривались ли вершины, ведущие из неё. В то время как, $n$— переменная, означающая, принимали ли мы эту вершину во внимание до этого (могли рассматривать путь к данной вершине, но ещё не проверили от неё идущие). Последнюю включил в код просто чтобы не приравнивать $len$ какому-то конкретному числу (по алгоритму, условно, должно быть равно бесконечности). Вектор $dis$-вектор дистанций от данной, к связанной с ней вершинам.

e-olymp 

ideone(1)

ideone(2)

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

Задача

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $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

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

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

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

Решение

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

Ссылки

e-olymp 5090. На перекрёстке

Задача

Есть таблица $n × n.$ Оживленностью строки или столбца назовем сумму чисел в ней. Нам очень хочется определить число на перекрестке самой оживленной строки и самого неоживленного столбца. Причем, чем выше будет этот перекресток (а среди них – чем левее), тем больше будет вероятность прохождения теста.

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

В первой строке находится число $n (1 \leq n  \leq 100).$ В следующих $n$ строчках задана таблица. Числа в таблице натуральные и не превышают $100000.$

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

Выведите число на перекрестке самой оживленной строки и самого неоживленного столбца.

Тесты

Входные данные Выходные данные
1 2
4 3
2 1
3
2 3
1 1 1
1 1 1
1 1 1
1
3 5
13 15 17 2 9
4 56 8 90 0
4 3 5 7 5
23 4 5 71 4
5 6 7 8 10
0
4 4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1

Код

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

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

Решение

Для решения данной задачи используем двумерный массив размера $n \times n$. С помощью цикла for ищем самую оживленную строку, затем самый неоживленный столбец, и выводим элемент таблицы на их перекрёстке.
Для решения с помощью одномерного массива действуем аналогично, работая с массивом длинны $n^2$, используя следующее соответствие: $x[i][j] \sim x[i \cdot n + j]$

Ссылки

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

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 4557. Одинокий король

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

Задача


Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из $n$ его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.
Определите, побывал ли король дважды на одном и том же поле за свои [latex] n [/latex] ходов.

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

В первой строке задано общее число ходов короля [latex] n [/latex] [latex](0 ≤ n ≤ 1000)[/latex]. В последующих [latex] n [/latex] строках заданы направления перемещения короля: строка под номером [latex] i + 1 [/latex] задаёт направление перемещения короля на [latex]i[/latex]-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.
Напоминаем, что манхэттенское расстояние между точками с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] определяется по формуле: [latex]d = |x_2 — x_1| + |y_2 — y_1|[/latex].

Тесты

# Входные  данные Выходные данные
1 5 1 2 4 7 4 4
2 5 1 2 4 6 4 Ok 2
3 3 1 2 1 Ok 5
4 3 1 5 1 2
5 8 8 8 8 8 8 8 8 8 Ok 8

Код

Решение

За изначальное местоположение короля возьмем точку с координатами [latex](0, 0)[/latex], а все передвижения короля по шахматной доске — это изменение абсциссы и (или) ординаты данной точки. Создадим два динамических массива  x = new int [n];  и  y = new int [n]; на [latex] n [/latex] элементов каждый, для абсцисс и ординат соответственно. Они будут хранить изменения координат всех точек, в которых побывал король. При этом, так как мы считаем, что начинаем движение с начала координат начнем заполнение массивов со второго элемента. Когда массивы в цикле  for (int i = 1; i <= n; i ++);  заполнятся будем искать совпадающие точки в другом цикле, если же таких не найдется, посчитаем расстояние между конечным и начальным местоположением короля, однако так как начальное местоположение короля — это начало координат, то ограничимся лишь немного упрощенной формулой [latex]d = |x_n| + |y_n|[/latex], или же в коде это выглядит так:  abs(x[n]) + abs(y[n]);. После, не забываем удалить уже использованные массивы, чтобы освободить память.

Код 2

Решение 2

Данный способ будет отличаться тем, что в отличии от предыдущего решения мы ограничимся лишь одним массивом, содержащим попарно координаты абсцисс и ординат соответственно. Также операторы  if(); можно заменить массивами  X[]; и  Y[]; , которые на соответствующих местах уже содержат изменение абсциссы и ординаты положения короля при конкретном перемещении.

Код 3

Решение 3

Изначально создаем двумерный массив заполненый нулями. Однако будем считать изначальное положение короля в точке с координатами [latex](1001, 1001)[/latex], чтобы не было проблем с отрицательными значениями. В данном варианте кода для большей краткости и разнообразия будем использовать оператор  switch();. Если король в клетке не был, то поставим [latex]1[/latex], если же был — выводим номер хода. Высчитываем манхэттенское расстояние если король не был в одной точке дважды.

Ссылки

  • Засчитанное решение 1 на e-olymp.
  • Засчитанное решение 2 на e-olymp.
  • Засчитанное решение 3 на e-olymp.
  • Код 1 в ideone.
  • Код 2 в ideone.
  • Код 3 в ideone.

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$ цикла, один из которых будет вложен в предыдущий:

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

Ссылки

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

e-olymp 1484. Серебрянная матрица

Задача

Матрицу будем называть серебрянной, если она удовлетворяет следующим условиям:

Размеры матрицы [latex]n\times n[/latex].
Все элементы матрицы лежат во множестве [latex]S = [/latex]{[latex] 1, 2, 3, \ldots, 2n-1[/latex]}.
Для каждого целого числа [latex]i \left(1 ≤ i ≤ n\right),[/latex] все элементы [latex]i[/latex]-ой строки и [latex]i[/latex]-го столбца образуют множество {[latex] 1, 2, 3, \ldots, 2n-1[/latex]}.
Например, следующая матрица размера [latex]4×4[/latex] является серебряной:

1 2 5 6
3 1 7 5
4 6 1 2
7 4 3 1

Доказано, что серебряная матрица размером [latex]2^K\times 2^K[/latex] всегда существует. Вам следует построить серебряную матрицу [latex]2^K\times 2^K[/latex].

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

Единственное число [latex]K \left(1 ≤ K ≤ 9\right).[/latex]

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

Вывести серебряную матрицу размером [latex]2^K×2^K[/latex]. Для вывода матрицы [latex]2^K\times 2^K[/latex], следует вывести [latex]2^K[/latex] строки, каждая из которых содержит [latex]2^K[/latex] целых чисел.

Тесты

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

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

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

Доказано, что матрица гарантировано существует. Напишем частный случай когда матрица имеет степень 1. Затем рекурсивно будем заполнять матрицу такими числами которых гарантировано нет ни в строке, ни в столбце. Например, для случая [latex]k = 1[/latex] подбираем вручную матрицу удовлетворяющую всем условиям. В противном же случае спускаемся к случаю [latex]k = 1[/latex] и затем наращиваем недостающие ряды подходящими для нас числами. То есть находим промежуток from и с помощью него заполняем одинаковыми значениями диагонали матрицы. Затем идем по незаполненным полям и заполняем новыми числами, которые еще не встречались.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Псевдо строчная таблица

Задача

В тридесятом государстве объявлено новое соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $m \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Все строки таблицы равны между собой. Задача участников — начертить таблицу наименьшей высоты. Алиса снова очень хочет победить, но она все еще плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит два натуральных числа $m$ и $n$, $(1 \leqslant m,n \leqslant 100).$ Далее идут $m$ строк содержащие по $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

Вывести минимальную высоту таблицы.

Тесты

$2 \ 3$ $12$
$1 \ 2 \ 3 \\ 1 \ 2 \ 3$
$1 \ 3$ $10$
$2 \ 3 \ 5$
$4 \ 4$ $96$
$3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9$
$3 \ 1$ $6$
$2 \\ 2 \\ 2$
$5 \ 3$ $430$
$46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12$
$2 \ 6$ $216$
$7 \ 32 \ 3 \ 23 \ 12 \ 31 \\ 7 \ 32 \ 3 \ 23 \ 12 \ 31$
$7 \ 5$ $945$
$5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78$
$1 \ 1$ $5$
$5$
$3 \ 7$ $210$
$10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10$
$2 \ 2$ $202$
$100 \ 1 \\ 100 \ 1$

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

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

Так как все строки равны между собой, тогда решение задачи состоит в том, чтобы разбить таблицу на строки размером $1 \times n$ и найти их минимальную высоту. Как находить высоту $h$ для каждой такой строки было показано тут. Тогда минимальная высота всей таблицы равна $m \cdot h.$

Ссылки

Код решения