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

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

HotLog


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

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

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