Задача. Васькины дорожки
Кот Василий узнал, что у соседа Димы, проживающего от него через какое-то количество заборов завелись мыши. Так как в своём хозяйстве всех мышей он уже давно выловил, кот отправляется на охоту за мышами к соседу, пролезая через дыры в ограде. На каждом участке Василий, как любой воспитанный кот, перемещается по уже проложенным там тропинкам. В деревне Старые Васюки, где проживает Василий, всего одна улица и та протянулась вдоль реки, поэтому домики расположены только по одну сторону улицы. Известно, что между любыми соседними участками в заборе ровно одна дыра. Сколькими способами Василий может попасть на участок Димы, если известно, что Дима проживает на участке под номером $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.
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> using namespace std; int main() { int n, m, k, a, MIN, MAX; unsigned long rez = 1; cin >> n >> m >> k; MIN = min(m, k); MAX = max(m, k); for (int i = 1; i <= MAX; i++) { cin >> a; if (i >= MIN) rez *= a; } cout << rez; return 0; } |