|
|
|
|
|
|
|
| 1 Шахмуратов Артур Тимурович, 04 июня 2026 г. 13:59:45 |
| вы все пишете что там комбинаторика паскаль рекурсия, но никто не упомянул про нестандартность реализации дп. вот код #include <bits/stdc++.h> using namespace std; vector<int> ans; vector<int> a; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; vector<ll> prev_dp(n+k); prev_dp[k-1] = 1; vector<ll> dp(n+k); for (int j = 0; j < k; j++) { for (int i = 0; i < n+k; i++) { if (i != 0) { dp[i] += prev_dp[i - 1]; } if (i != n + k - 1) { dp[i] += prev_dp[i + 1]; } } if (j < k - 1) { dp[n + k - 1] = 0; } prev_dp = dp; dp = vector<ll>(n+k, 0); } cout << prev_dp[n + k - 1]; }
|
|
|
| 2 Арестович Егор Викторович, 06 апреля 2025 г. 11:41:09 |
| Изи задача, простейшая рекурсия с мемоизацией, AC, долго не мог решить эту задачу. Вернулся, и решил за 10 минут)
|
|
|
| 3 Кондибор Михаил Валентинович, 28 сентября 2024 г. 10:42:45 |
| Маленькая подсказка: Решайте треугольником Паскаля
|
|
|
| 4 Серикбек Асанали, 06 мая 2023 г. 18:46:17 |
| Рекурсия с мемоизацией заходит, главное понимать при каких случаях нужно останавливаться
|
|
|
| 5 Сиваченко Михаил Константинович, 12 января 2020 г. 12:27:50 |
| Админ, допишите, пожалуйста, в задаче, что можно со старта назад идти, а то решил совсем не ту задачу(
|
|
|
| 6 Матус Даниил Дмитриевич, 07 августа 2019 г. 23:34:13 |
| Если кто первый тест не понял, то читайте условие. Сказано: дойти до магазина лишь тогда и только тогда, когда кончатся шаги.
|
|
|
| 7 Трусов Дмитрий Сергеевич, 04 мая 2019 г. 18:51:37 |
Подскажите, а какой ответ на тест: 2 3
На тест 2 3 ответ 0.
|
|
|
| 8 Соенджов Атагелди Соенджович, 19 декабря 2018 г. 8:02:07 |
| За Время: O(37 * 37) = O(1369) = 0.03
|
|
|
| 9 Шаяхметов Ислам Робертович, 06 января 2018 г. 18:34:28 |
| ограничения бы побольше, а то уж больно маленькие для сложности O(k*k)
|
|
|
| 10 Фалько Слава, 09 августа 2017 г. 18:50:37 |
если рассмотреть таблицу K*N то аналогия с треугольником Паскаля. Решение элементарно без графов и рекурсии.
1
0 1
1 0 1
0 2 0 1
2 0 3 0 1
0 5 0 4 0 1
5 0 9 0 5 0 1
|
|
|
| 11 Ганущак Влад Олегович, 22 января 2017 г. 15:11:30 |
N K Ans:
3 37 1289624490
5 37 1739969550
Решать через рекурсию, даже через рекурсию с меморизацией, по моему мнению, не оптимально.
|
|
|
| 12 Гимадутдинов Рустем, 05 декабря 2015 г. 20:38:22 |
| меморизация рекурсии загуглите
|
|
|
| 13 Левченко Илья Владимирович, 29 мая 2014 г. 20:07:58 |
| Элементарная динамика по двум параметрам, решение занимает 4 строки. O(k*(n+k)).
|
|
|
| 14 Абдрахманов Алдияр Маулынгазынович, 13 мая 2014 г. 8:44:58 |
| За O(n*(k-n)) o.0
|
|
|
| 15 Захаров Константин Леонидович, 29 ноября 2013 г. 0:14:47 |
| Не знаю кто тот человек, идущий по шагу в минуту к магазу (угадайте что он купит). Но упомянутое красивое решение рекурсией здесь все же заходит) Правильным является состояние, когда steps = k, pos = n. Если задать отношение rec(pos,steps) = rec(pos+1, steps+1) + rec(pos-1,steps+1), то rec(n,k) = 1, прочие rec(a,k) = 0. Вопрос сколькими способами можем прийти к (n,k). А стартуем мы откуда? Из (0,0), т.е. позиция 0, сделано шагов 0. Однако такая рекурсия не заходит, уж больно много раз ей придется пересчитать одно и то же. Однако, это решается таким приемом как ленивая динамика, или меморизация. Советую найти на хабре (гуглом) статью про это, тогда добавите несколько строк и это решение уже работает на заданных ограничениях.
|
|
|
| 16 Фоменко Владимир, 17 апреля 2013 г. 11:36:10 |
(14,28)->592020
(13,27)->427570
|
|
|
| 17 Василевский Виктор Владимирович, 11 сентября 2012 г. 21:16:00 |
| Дык это ж числа Каталана!
|
|
|
| 18 Тест Тест Тест, 07 августа 2012 г. 19:45:35 |
| Блин, а рекурсией красивое решение. Жаль ограничения не позволяют.
|
|
|
| 19 Бабанов Айдар Нурланович, 27 февраля 2011 г. 18:44:35 |
| Здесь я понял, если N четное, а К нечетное то вариант один-0. И наоборот
|
|
|
| 20 Бабанов Айдар Нурланович, 27 февраля 2011 г. 18:02:27 |
Мне кажется надо ходить в диапазоне старта и магазина, за рамки не выходить
За рамку магазина выходить нельзя, а вот за рамку старта можно.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
