e-olymp 1661. Рюкзак Алладина

Условие

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

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

Требуется определить максимальную стоимость груза, который Алладин может поместить в свой рюкзак.

Будем считать, что в пещере имеются предметы $n$ различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен $w$. Каждый предмет типа $i$ имеет вес $w_{i}$ и стоимость $v_{i}$ $(i = 1, 2, \ldots, n)$.

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

В первой строке содержится два натуральных числа $w$ и $n$ $(1 \leq w \leq 250, 1 \leq n \leq 35)$ — максимальный вес предметов в рюкзаке и количество типов предметов. Следующие $n$ строк содержат по два числа $w_{i}$ и $v_{i}$ $(1 \leq w_{i} \leq 250, 1 \leq v_{i} \leq 250)$ — вес предмета типа $i$ и его стоимость.

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

Выведите максимальную стоимость груза, вес которого не превышает $w$.

Тесты

Входные данные Выходные данные
1 10 2
5 10
6 19
20
2 250 35
187 100
28 109
245 142
123 83
237 78
36 172
15 248
90 24
181 137
40 233
8 99
231 128
79 132
43 217
156 104
45 191
130 113
105 225
206 5
26 120
26 119
64 138
23 147
19 202
79 54
149 185
158 79
209 88
110 133
235 209
188 230
15 220
107 164
235 137
60 167
4067
3 35 4
20 4
1 2
10 8
7 6
70

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

Решение

Допустим $w = 9$, $n = 2$, первый предмет $w_{1} = 3$, $n_{1} = 4$, а второй предмет $w_{2} = 2$, $n_{2} = 1$. После того как считаем условие в два одномерных или один двумерный массив (как вам удобнее). Создадим одномерный массив в котором его размер будет равен $w$ и первый элемент будет равен 0, а остальные будут равны минус бесконечности или как в нашем случае (в коде) -1, как показано на (рис. 1). И дальше как показано на (рис. 2) начиная с элемента с номером веса предмета мы прибавляем его стоимость к стоимости предыдущей как показано в коде s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];, если прошлый не минус бесконечность. И так же со вторым элементом, когда они пересекаются с первым мы их сравниваем и вписываем в массив больший. И в самом конце проходим заново массив и выбираем самый больший элемент, где бы он ни был как показано на (рис. 3). И таким образом на последних позициях которые равняются весу, будут записаны самые дорогие комбинации, благодаря записи самых дорогих элементов в ячейки.

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

e-olymp 9537. Транспонирование матрицы

Задача

Задана матрица [latex]A[/latex]. Транспонируйте ее.
Пусть [latex]B[/latex] — транспонированная матрица [latex]A[/latex]. Пусть [latex]B[/latex] — транспонированная матрица [latex]A[/latex]. Тогда [latex]
B_{ij} = A_{ji}[/latex]

[latex]\begin{pmatrix}
1&2 \\
3&4 \\
5&6
\end{pmatrix}^T = \begin{pmatrix}
1 &3 &5 \\
2 &4 &6
\end{pmatrix}[/latex]

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

Первая строка содержит размеры матрицы [latex]n[/latex] и [latex]m[/latex]. [latex]1 \leq m,n \leq 100 [/latex] Следующие [latex]n[/latex] строк содержат по [latex]m[/latex] целых чисел и описывают матрицу [latex]A[/latex].

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

Выведите транспонированную матрицу [latex]A[/latex]: [latex]m[/latex] строк по [latex]n[/latex] целых чисел.

Тесты

Входные данные Выходные данные
1 3 2
1 2
3 4
5 6
1 3 5
2 4 6
2 3 3
0 1 2
1 0 3
2 3 0
0 1 2
1 0 3
2 3 0
3 4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
4 10 3
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
16 17 18
19 20 21
22 23 24
25 26 27
28 29 30
1 4 7 10 13 16 19 22 25 28
2 5 8 11 14 17 20 23 26 29
3 6 9 12 15 18 21 24 27 30

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

Решение

При получении первой матрицы мы получаем индекс каждого элемента — [latex]i[/latex], [latex]j[/latex] и количество строк и столбцов — [latex]n[/latex] и [latex]m[/latex]. Зная саму матрицу, количество строк и столбцов мы можем создать матрицу, где строк столько, сколько столбцов в первой матрице, и наоборот.
Сама же перестановка элементов происходит посредством смены индекса строки и столбца — элемент [latex]a[/latex] с индексом [latex]i[/latex] строки и [latex]j[/latex] столбца становится элементом [latex]b[/latex] с индексом [latex]j[/latex] строки и [latex]i[/latex] столбца.

Cсылки

Условие на e-olymp
Код на ideone

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

Условие

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

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

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

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

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

Тесты

Входные данные Выходные данные
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 такт – заполняет левую грань снизу вверх, как показано на рисунке ниже.

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


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

e-olymp-8577. Супер платформи

Условие

У багатьох старих іграх з двовимірною графікою можна зіткнутися з такою ситуацією. Який-небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. При цьому, при стрибку з однієї платформи на сусідню, у героя витрачається $\left|y_2–y_1\right|$енергії, де $y_2$ та $y_1$ – висоти, на яких розміщені ці платформи. Крім того у героя є суперприйом, який дозволяє перестрибнути через платформу, причому на це витрачається $3·|y_2–y_1|$ одиниць енергії. Кількість використань суперприйому обмежена й повинна перебувати в межах від $k_{min}$ до $k_{max}$ разів (обидві межі включно). Звичайно ж, енергію потрібно витрачати максимально економно.

Припустимо, що вам відомі координати усіх платформ у порядку від лівого краю до правого та обмеження на кількість використань суперприйому $k_{min}$ та $k_{max}$. Чи зможете ви знайти, яку мінімальну кількість енергії потрібно герою, щоб дістатись від першої платформи до останньої?

Вхідні дані

У першому рядку записана кількість платформ $n (1 \leq n ≤ 10000)$. Другий рядок містить n натуральних чисел, які не перевищують 30000 – висоти, на яких розміщено платформи. Третій рядок містить два цілі невід’ємні числа $k_{min}$ та $k_{max}$ $\left(0 ≤ k_{min} ≤ k_{max} ≤ \frac{n–1}{2}\right)$.

Вихідні дані

Виведіть єдине число – мінімальну кількість енергії, яку повинен витратити гравець на подолання платформ (звісно ж у припущенні, що cheat-коди використовувати не можна).

Тесты

Ввод Вывод
1 3
1 5 10
0 1
9
2 9
1 3 2 3 8 10 25 17 25
2 4
24

Код

Решение

В решении суперприёмы из условия для удобства буду называть суперпрыжками.
Решим эту задачу динамически. На каждом шаге будем искать масив, где записано сколько минимально надо потратить энергии что б добраться до каждой платформы, сделав ровно $j$ суперпрыжков. Легко получить рекурсивную зависимость: для того, что бы попасть на $i$ платформу нам надо либо прыгнуть с предыдущей $(a_{j (i-1)}+|p_i-p_{i-1}|)$ либо сделать суперпрыжок с платформы под номером $i-2$ $( a_{(j — 1)(i — 2)} + 3|p_{i — 2} — p_i| )$. Не забудем про то, что не всегда можно прыгнуть с предыдущей так как мы могли бы и не попасть на нее за $j$ суперпрыжков. Таким образом для некоторых платформ( а именно первых в каждом масиве) мы будем делать суперпрыжок с платформы под номером $i-2$. На каждом шаге если нам разрешено сделать столько суперпрыжком сколько мы сделали обновляем общее минимальное количество затраченной энергии если оно больше чем результат, полученный нами на последней платформе. Таким образом на каждом шаге мы будем получать минимальные затраты для определенного количества прыжков. Таким образом минимальное из этих самых ответов и будет тем что требуется в задаче.

Оптимизация

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

Ссылки

e-olymp 657. Игра с монетами

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

Условие

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более $ K$ стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

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

В первой строке находится сначала число стопок $ N,$ за ним идут $ N$ чисел, задающих количество монет в стопках слева направо, а затем число $ K.$ Все числа в строке разделены пробелами.
$ 1 \leqslant N \leqslant 180, 1 \leqslant K \leqslant 80,$ количество монет в стопке — не менее $ 1$ и не более $ 20 000$.

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

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

Тесты

Inputs Outputs
1 3 4 9 1 3 14
2 4 1 2 2 7 3 5
3 5 3 4 8 1 7 2 18
4 12 67 8 6 12 6 90 54 89 145 32 45 65 4 357
5 14 32 53 5 52 9 8 17 5 87 44 51 12 15 56 10 312
6 14 76 112 3 1 98 4 172 33 65 90 2 71 18 32 14 777

Код

Решение

Анализируя задачу, становится понятно, что ее можно решить методами динамического программирования, а именно трехмерная динамика по параметрам: количество уже взятых стопок — l, количество стопок, которые можно взять kи какой игрок сейчас ходит p. Каждый игрок старается ходить оптимально, тогда для первого игрока задача взять максимальное количество монет, а для второго игрока задача оставить наименьшее количество монет оппоненту. Решение исполнено с помощью рекурсии, где терминальный случай-когда в массиве осталось количество стопок, меньшее или равное тому, сколько игрок может взять. Также стоит проверять высчитывалась ли раньше данная позиция, иначе задача не зайдет по времени.

Ссылки

e-olymp 683. Частичная сумма матрицы

Задача

Задана матрица чисел $a_{ij}$ где $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$. Для всех $i, j$ найдите $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt}.$$

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

В первой строке записаны размеры матрицы — $n, m$ $(1 \leqslant n, m \leqslant 1000)$. В последующих $n$ строках записано по $m$ чисел $a_{ij}$ $(1 \leqslant a_{ij} \leqslant 1000)$.

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

Выведите $n$ строк по $m$ чисел $S_{i,j}$.

Тесты

Входные данные Выходные данные
3 5
1 2 3 4 5
5 4 3 2 1
2 3 1 5 4
1 3 6 10 15
6 12 18 24 30
8 17 24 35 45
4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
6 7
15 78 69 36 567 654 5
54 54 52 81 237 5 98
987 2 65 5 32 89 67
541 89 4 32 4 1 40
68 7 345 6 21 23 56
9 5 7 2 5 4 1000
15 93 162 198 765 1419 1424
69 201 322 439 1243 1902 2005
1056 1190 1376 1498 2334 3082 3252
1597 1820 2010 2164 3004 3753 3963
1665 1895 2430 2590 3451 4223 4489
1674 1909 2451 2613 3479 4255 5521

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

 

Решение

Создаем  матрицу x[1001][1001]  вне int main() . Сдвигаем индексацию массива на единицу и заполняем его. Таким образом первая строка и первый столбец у нас оказываются заполнены нулями. Чтобы не вычислять каждую новую $S_{i,j}$ от $(i+1)\cdot (j+1)$ предыдущих значений, воспользуемся основным свойством частичных сумм: если $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt},$$ то тогда $S_{i,j} — a_{ij}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j}\cap S_{i,j-1}$, где $S_{i-1,j}\cap S_{i,j-1} = S_{i-1,j-1}$. Тогда при $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$ вычисляем частичные суммы по формуле: $$S_{i,j} = S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{ij}.$$

Ссылки

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

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

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

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

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

Вхідні дані

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

Вихідні дані

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

Тести

Inputs Outputs
1
5 7
1 3
1 4
2 4
2 5
3 4
3 5
4 5
2
2
4 4
1 2
2 3
3 4
1 4
1
3
5 5
1 2
2 3
3 5
1 4
1 5
1

Код

 

Рішення

Зробимо ізоморфний перехід в графи, а саме можна помітити, що визначивши типи запків як вершини матимемо зв’язки між типами, як існуючий елемент браслета, тобто пара $(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\limits_{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 7534. Замкнутое сокровище

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

Задача

Группа из $n$ бандитов спрятала украденное сокровище в комнате. Дверь в комнату следует отпереть только когда понадобится вынести сокровище. Так как бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и унести украденное только если этого захотят не менее $m$ из них.

Они решили разместить несколько замков на двери таким образом, чтобы она открывалась только когда открыты все замки. Каждый замок может иметь до $n$ ключей, распределенных среди некоторого подмножества бандитов. Группа бандитов может открыть замок, только если кто-то в группе имеет ключ к этому замку.

По имеющимся значениям $n$ и $m$ определить такое наименьшее количество замков, что если ключи от них правильно распределить среди бандитов, то каждая группа состоящая из не менее чем $m$ бандитов сможет открыть все замки, но никакая группа из меньшего числа бандитов открыть все замки не сможет.

Например, если $n = 3$ и $m = 2$, то достаточно $3$ замков — ключи от замка $1$ получают бандиты $1$ и $2$, ключи от замка $2$ получают бандиты $1$ и $3$, ключи от замка $3$ получают бандиты $2$ и $3$. Ни один из бандитов не может открыть все замки самостоятельно, но любая группа из $2$ бандитов может открыть все замки. Можно убедиться, что $2$ замков для этого случая не достаточно.

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

Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа $n(1 \leqslant n \leqslant 30)$ и $m(1 \leqslant m \leqslant n)$.

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

Для каждого теста вывести в отдельной строке минимальное количество необходимых замков.

Тесты

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

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

Решение

Для каждой группы из $m-1$ бандитов существует замок такой, что его могут открыть все остальные группы, кроме этой. Потому что, просто обьеденив две группы с одинаковыми замками, мы получим одну большую чем $m-1$, которая не может открыть замок. Таким образом, всего должно быть столько замков, сколько существует способов выбрать $m-1$ группу из $n$ бандитов. То есть $C_{n}^{m-1}$.
Для нахождения биномиальных коэффициентов воспользуемся треугольником Паскаля, который будем хранить в двумерном массиве.

Ссылки

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

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

Треугольник Паскаля на Wikipedia

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 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)