Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1 2
  1  Сиваченко Михаил Константинович, 12 января 2020 г. 12:27:50
     Админ, допишите, пожалуйста, в задаче, что можно со старта назад идти, а то решил совсем не ту задачу(
  2  Матус Даниил Дмитриевич, 07 августа 2019 г. 23:34:13
     Если кто первый тест не понял, то читайте условие. Сказано: дойти до магазина лишь тогда и только тогда, когда кончатся шаги.
  3  Трусов Дмитрий Сергеевич, 04 мая 2019 г. 18:51:37
     Подскажите, а какой ответ на тест: 2 3
     На тест 2 3 ответ 0.
  4  Соенджов Атагелди Соенджович, 19 декабря 2018 г. 8:02:07
     За Время: O(37 * 37) = O(1369) = 0.03
  5  Шаяхметов Ислам Робертович, 06 января 2018 г. 18:34:28
     ограничения бы побольше, а то уж больно маленькие для сложности O(k*k)
  6  Фалько Слава, 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
  7  Ганущак Влад Олегович, 22 января 2017 г. 15:11:30
     N K Ans:
3 37 1289624490
5 37 1739969550
Решать через рекурсию, даже через рекурсию с меморизацией, по моему мнению, не оптимально.
  8  Гимадутдинов Рустем, 05 декабря 2015 г. 20:38:22
     меморизация рекурсии загуглите
  9  Левченко Илья Владимирович, 29 мая 2014 г. 20:07:58
     Элементарная динамика по двум параметрам, решение занимает 4 строки. O(k*(n+k)).
  10  Абдрахманов Алдияр Маулынгазынович, 13 мая 2014 г. 8:44:58
     За O(n*(k-n)) o.0
  11  Захаров Константин Леонидович, 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. Однако такая рекурсия не заходит, уж больно много раз ей придется пересчитать одно и то же. Однако, это решается таким приемом как ленивая динамика, или меморизация. Советую найти на хабре (гуглом) статью про это, тогда добавите несколько строк и это решение уже работает на заданных ограничениях.
  12  Фоменко Владимир, 17 апреля 2013 г. 11:36:10
     (14,28)->592020
(13,27)->427570
  13  Василевский Виктор Владимирович, 11 сентября 2012 г. 21:16:00
     Дык это ж числа Каталана!
  14  Тест Тест Тест, 07 августа 2012 г. 19:45:35
     Блин, а рекурсией красивое решение. Жаль ограничения не позволяют.
  15  Бабанов Айдар Нурланович, 27 февраля 2011 г. 18:44:35
     Здесь я понял, если N четное, а К нечетное то вариант один-0. И наоборот
  16  Бабанов Айдар Нурланович, 27 февраля 2011 г. 18:02:27
     Мне кажется надо ходить в диапазоне старта и магазина, за рамки не выходить
     За рамку магазина выходить нельзя, а вот за рамку старта можно.
  17  Muslim Ertugan, 17 февраля 2011 г. 13:50:24
     Че то, вообще не врубаюсь, со старта назад ходить можно?
Или дальше магазина пройтись а потом назад?
А еще если дойдеш до магазина, а у тебя еще два хода в запасе, тогда можно ли будет сделать шаг
назад, потом вперед?
     Со старта назад можно, а вот доходить до магазина раньше К-го шага нельзя.
  18  Ключ к жизни, 03 декабря 2009 г. 13:07:40
     Можете сказать ответы на такие тесты:
input.txt:
1) 3 37
2) 1 9
3) 19 20
     output.txt:
1) 1289624490
2) 14
3) 0
  19  Гринчук Олег Валерьевич, 09 марта 2009 г. 11:25:01
     Задача очень легко решается, если рассмотреть массив A[1..k,1..n]
     Да в принципе может хватить и A[1..2][1..n], это как кому нравится.
  20  Акашаев Нурлан Амангельдиевич, 17 февраля 2009 г. 16:46:19
     да, алгоритм простой, только додуматься надо. Хехе
 1 2

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru