e-olymp 1325. Васькины дорожки

Задача. Васькины дорожки

Кот Василий узнал, что у соседа Димы, проживающего от него через какое-то количество заборов завелись мыши. Так как в своём хозяйстве всех мышей он уже давно выловил, кот отправляется на охоту за мышами к соседу, пролезая через дыры в ограде. На каждом участке Василий, как любой воспитанный кот, перемещается по уже проложенным там тропинкам. В деревне Старые Васюки, где проживает Василий, всего одна улица и та протянулась вдоль реки, поэтому домики расположены только по одну сторону улицы. Известно, что между любыми соседними участками в заборе ровно одна дыра. Сколькими способами Василий может попасть на участок Димы, если известно, что Дима проживает на участке под номером $k,$ а сам Василий проживает на участке под номером $m$?

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

В единственной строке находятся через пробел сначала количество домов в деревне $n,$ затем номер участка Василия $m,$ номер участка Димы $k,$ а далее $n$ чисел, обозначающее количество тропинок, ведущих либо к дыре в заборе, либо от дыры в заборе, либо между дырами в заборе соседей $i$ и $i+1.$ Все входные данные натуральные числа, не превышающие $10.$

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

Единственное число — количество различных способов для Василия попасть на нужный участок для охоты.

Тесты

Ввод Вывод
1 3 2 3 4 5 3 15
2 10 5 7 1 2 3 4 5 6 7 8 9 10 210
3 4 2 1 3 4 7 8 12
4 10 8 8 1 9 6 7 5 3 8 2 4 10 2
5 1 1 1 1 1
6 10 1 10 1 1 1 1 1 1 1 1 1 10 10
7 7 5 3 2 2 2 4 4 4 5 32
8 10 1 10 10 10 10 10 10 10 10 10 10 10 10000000000
7 5 3 2 1 2 3 4 5 6 7 8 9 10 6

Решение

Что бы определить количество различных способов попасть на нужный участок мы должны, сначала, посчитать сколькими способами кот Василий может пересечь (по тропинкам) участок на котором он находится. Затем, для каждого из возможных вариантов пересечения первого участка посчитать сколькими способами Василий может пересечь второй участок и так далее, до заданного. Таким образом общее количество вариантов попасть, для нашего друга, из участка $m$ в участок $k$ является произведением количества вариантов пересечения каждого участка в отдельности.

Прочтём значения $n$, $m$ и $k$. Переменная rez будет хранить результат. В цикле от $1$ до наибольшего номера из участков Димы и Василия, будем проверять достигли ли мы наименьшего номера их участков. По достижении начинаем перемножать количества тропинок ведущих к дыркам в заборе. Мы можем это делать с начиная с любого из участков так как операция умножения коммутативна. Завершив цикл в переменной rez у нас уже будет правильный ответ. Выведем его.

Типа данных  unsigned long хватит по условию данной задачи, так как все числа натуральные, а значит большие $0.$ И не превышают $10,$ следовательно максимальное значение переменной  rez будет $10^{10}$ что помещается в unsigned long.

Код

Условие задачи

Решение

Код на ideone

Ю4.36

Задача: Гидрологами исследовано течение реки в некотором сечении: произведена серия замеров от одного берега до другого перпендикулярно фарватеру, полученные данные: [latex]{s}_{i}[/latex]  — расстояние от левого берега, м; [latex]{h}_{i}[/latex]  — глубина реки, м; [latex]{v}_{i}[/latex]  — скорость течения, м/с, [latex]i=1,2…,n[/latex] . Каков расход воды в секунду? То есть сколько кубометров воды протекает через сечение в секунду?

Тесты:  (сначала вводятся все данные одного массива, а не поочерёдно)

Ввод Ответ Комментарий
3
[2 4 6] [4 5 5] [3 7 2]
 88 Работает
2
[13 42] [17 18] [3.14 2.71]
1409.85 Работает

Объяснение переменных:

int n - количество замеров

int area = 0 - площадь поперечного сечения (требуется для формулы расхода воды)

int velocity = 0 - cумма скоростей, позже будет делится на количество замеров (тоже для формулы)

double s[n], h[n], v[n]; - массивы с данными о замере

Код: проверить на ideone.

Алгоритм выполнения описан в комментариях в коде.

Используется формула расхода воды:  [latex]Q=Av[/latex]  , где [latex]A[/latex]  — площадь поперечного сечения, а [latex]v[/latex]  — среднее арифметическое скорости течения всех замеров. Метод подсчета площади сечения реки описан по ссылке.

Для понимания метода:

270

 

Первый и последний «замер» на картинке образуют треугольники (относительно берега). Между ними —  прямоугольные трапеции (  [latex]S=\frac { a+b }{ 2 } h[/latex], где [latex]a[/latex], например, линия 2-го замера (по картинке), а  [latex]b[/latex]  линия 3-го замера соответственно, [latex]h[/latex]  — расстояние от 2-го замера до 3-го (нынешнее расстояние от берега отнять прошлое). Суммируем площади фигур — это и будет площадь сечения реки.

Замечание:

Данные должны вводится последовательно относительно удаления от левого берега. Подразумевается, что гидрологи обязательно замеряли всю реку (от левого до правого берегов) минимум 2-мя замерами.