Люди добрые помогите с задачей

14 лет назад, # |

Любой путь из клетки [1, 1] в клетку [N, M] состоит ровно из N + M - 2 шагов. Из них N - 1 раз по одной оси, а M - 1 по другой. И тут в игру вступает комбинаторика. Ответом является число сочетаний из N + M - 2 по M - 1, что, в принципе, равно числу сочетаний из N + M - 2 по N - 1.

Ну а как это посчитать по непростому модулю - это другой вопрос. Я бы использовал такой подход: подсчитаем для каждого простого числа сколько раз оно входит в качестве множителя в числитель и знаменатель числа сочетаний. Факторизацию надо осуществлять, перебирая только простые делители, которые заранее можно получить с помощью решета Эратосфена.

→ Ответить

slowpoke

14 лет назад, # |

Каждый путь можно представить как строку из N-1 символов 'R' (ход вправо) и M-1 символов 'U' (ход вверх), как-то перемешанных между собой. И наоборот, каждой такой строке соответствует некоторый путь. Поэтому число путей равно числу таких строк -- это число сочетаний C(N+M-2, N-1).

C(N+M-2, N-1) = (N+M-2)!/((N-1)!*(M-1)!)

Чтобы быстро это посчитать, можно найти для каждого простого числа от 2 до N+M-2 степень, в которой оно входит в каждый из факториалов. Степень, в которой простое число p входит в факториал N! равна [N/p]+[N/p^2]+[N/p^3]+... Все деления целочисленные. Простые числа можно определить решетом Эратосфена. Зная степени простых чисел, просто перемножаем эти числа по модулю K.

→ Ответить

14 лет назад, # |

Всем большое спасибо!!!!

→ Ответить

gnull

14 лет назад, # |

← Rev. 2 →

-10

Еще можно обозначить массив a[0..n+1][0..m+1], каждая ячейка a[i][j] будет обозначать количество способов попасть в клетку i,j. a[1][1]=1; ( есть только один способ попасть в клетку в которой мы уже стоим ) для всех остальных a[i][j]=a[i-1][j]+a[i][j-1], так как в клетку i,j мы можем попасть из клеток (i-1),(j) и (i),(j-1). a[0][j] и a[i][0] равны 0, по-тому, что мы не можем туда попасть и кол-во способов 0. Ответом будет a[n][m](кол-во способов попасть в клетку n,m)

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

Если посмотреть на ограничения (N и M порядка 10⁶), то массив размерности N x M мы не заведем. Более того, решение с оценкой времени выполнения O(NM) будет работать в лучшем случае 1000 секунд, а это означает, что даже если реализовать так, чтобы обходиться двумя строками матрицы, то все равно такое решение не зайдет. Учим комбинаторику!

→ Ответить

kostya_by

14 лет назад, # |

ээээ....эта задача какбэ на еще идущем заочном этапе кубка моей гимназии=)

→ Ответить

14 лет назад, # ^ |

Сами виноваты, нечего давать баяны на официальные этапы. Пусть новые задачи придумывают.

→ Ответить

KA-95

14 лет назад, # ^ |

Всё,Костя,надо снимать задачу)

Кстати,а кто её писал,ты или Ваня?

→ Ответить

kostya_by

14 лет назад, # ^ |

Черневич)

→ Ответить

14 лет назад, # ^ |

Как совет организаторам: ничего не снимайте :) Просто дисквалифицируйте участника, который таким образом решил сдать задачу. У вас есть полная информация о нем, just do it!

→ Ответить

ivan.popelyshev

14 лет назад, # ^ |

А мы его поминусуем :)

→ Ответить

14 лет назад, # ^ |

-12

ЭЭЭ) она же не принимается!! (причём давно!!!)!!

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

Не стоит обращать столько внимания на вклад

→ Ответить

yeputons

14 лет назад, # ^ |

Вот только в хабр, пожалуйста, CF не надо превращать, где за упоминание слов "рейтинг" и "карма" любой человек (кроме, видимо топов) загоняется в такой минус, что легче зарегистрировать новый аккаунт, чем выбраться до уровня "моу писать новые посты и комментировать чаще раза в час".
Жутко бесит. Правда, тут еще нет системы "<20 рейтинга - писать нельзя" - это радует. Поэтому можно действительно обращать меньше внимания.

→ Ответить

14 лет назад, # ^ |

и не собирался)

→ Ответить

yeputons

14 лет назад, # ^ |

Просто "Не стоит обращать столько внимания" - именно этой фразой и аргументируют минусовальщики на хабре :) А то, что после этого человек ничего делать не может, всем, конечно, пофиг.
Закрыли тему :)

→ Ответить

Liaksiejka

14 лет назад, # ^ |

Такое чувство что если бы он сюда написал условие какой-то другой задачи,не баянной как вы тут говорите, никто бы не написал решение. (да и не знал я что она была на tc когда-то)Так что не вижу ничего плохого в этой задаче. :)

→ Ответить

14 лет назад, # ^ |

-14

ТЕМ БОЛЛЕ каким бокам я до вашего кубка!!!!!!!!!!!! Я просто нашел интересную задача и решил уточнить у более знающих людей как её правильно решить!!!!!!

→ Ответить

Liaksiejka

14 лет назад, # ^ |

← Rev. 2 →

:))) да действительно и даже тесты не поменял. А контест кстати еще идет.
Мне все равно , в том плане если кто-то загуглит решение, или прочитает его в книге, но пусть он сделает это сам :) В конце-концов это же заочный этап(да, спасибо). Но тупо вот так написать сюда , как-то совсем уж некрасиво. А в плане дисквалификации. Никто не будет дисквалифицирован.

→ Ответить

14 лет назад, # ^ |

мб заочный?

→ Ответить

14 лет назад, # ^ |

-8

Я в нем даже не участвую!! !!!!!

→ Ответить

freopen

14 лет назад, # ^ |

1. Вы прочитали то, на что ответили? Проблема в том, что Вы создали хорошо индексируемое поисковиками решение задачи активного контеста. И тут уже не важно, участвуете вы или нет. И, все-таки, я думаю, что это было скорее предупреждение, чем обвинение.

2. Ну неужели нельзя обойтись без 43 восклицательных знаков на три сообщения и без слов, набранных заглавными буквами? Ну это же не сложно вроде бы...

→ Ответить

yeputons

14 лет назад, # ^ |

Не лень было считать? :)

→ Ответить

freopen

14 лет назад, # ^ |

+20

Не лень было проверять, что я не с потолка цифру взял?

→ Ответить

14 лет назад, # ^ |

На свете есть масса гимназий и тд... И если организаторы "сумели" придумать очевидное условие задачи - это проблема организации... Не дело отвечающих на позыв ----помогите с задачей отслеживать контесты всяко-разных гимназий...

→ Ответить

taras.klaskovsky

14 лет назад, # ^ |

А кто-то просит их отслеживать или винит отвечающих?

→ Ответить

14 лет назад, # ^ |

Никто не просит... Но когда после сообщения "Помогите... " появляется комментарий "Это с нашего еще идущего поселкового контеста" - умиляет...

→ Ответить

taras.klaskovsky

14 лет назад, # ^ |

Не вижу здесь вины организаторов и вообще какой-либо проблемы, помимо вашей умиляемости. Человек запостил задачу, в комментариях написали источник.

→ Ответить

14 лет назад, # ^ |

Просмотрев обсуждение я вижу что человеку за фразы типа "не знаю я ваших кубков..." поставили кучу минусов... Если это участник контеста - нужно не минусовать, а дисквалифицировать( расстреливать), если нет - то минусование навевает нездоровые амбиции организаторов и тд

→ Ответить

taras.klaskovsky

14 лет назад, # ^ |

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

→ Ответить

Liaksiejka

14 лет назад, # ^ |

← Rev. 2 →

Тарас, в след. раз когда, какой-нибудь парень с поселка\деревни\агрогородка\местечка, напишет что-нибудь неприятное для тебя , напиши ему в личку что он мудак, и не ведись на его троллинг.

→ Ответить

Jokser

14 лет назад, # |

А мне интересно решение данной задачи, если на карту еще поставить L (порядка 10^3) препятствий, в виде прямоугольников.

→ Ответить

14 лет назад, # |

-17

→ Ответить

freopen

14 лет назад, # ^ |

В этом случае я бы посоветовал давать ссылку на задачу, чтобы все могли быстро понять, откуда эта задача. Да и читаемость задачи повысится. Если источника в интернете нет, можно хотя бы писать источник задачи (такое-то соревнование, такой-то год, к примеру). Это займет немного времени и избавит Вас от недопонимания.

→ Ответить

14 лет назад, # ^ |

Может прописать в правилах, чтоб все сообщения типа "Помогите с задачей" сопровождались бы ссылками на условие и тд...

→ Ответить

14 лет назад, # ^ |

А правил то сопсно и нет)

→ Ответить