Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 13.02.2010, 03:11
Новичок

Отправить личное сообщение для Zero Посмотреть профиль Найти все сообщения от Zero
 
Регистрация: 08.08.2009
Сообщений: 8

Куб
www.snarknews.info SNSS-2009 day_5_A_airport (задача 0301)

Дан куб K( n*n*n , 1<=n<=1000000).
K[1][1][1]=1;
K[i][j][k]=K[i-1][j][k]+K[i][j-1][k]+K[i][j][k-1];

Для заданного n вывести значение K[n][n][n].

(для n=3
1 1 1 1 2 3 1 3 6
1 2 3 2 6 12 3 12 30
1 3 6 3 12 30 6 30 90 Т.е. K[3][3][3]=90)

Задача легко решается за O(n^3), но из ограничений ясно, что подойдет только алгоритм O(n). Может быть есть даже "красивая" формула для этой задачи?
  #2  
Старый 13.02.2010, 03:18
Новичок

Отправить личное сообщение для Zero Посмотреть профиль Найти все сообщения от Zero
 
Регистрация: 08.08.2009
Сообщений: 8

1 1 1____1 2 3____1 3 6
1 2 3____2 6 12___3 12 30
1 3 6____3 12 30__ 6 30 90
Original: Здание аэропорта города Пловдив можно представить в виде трёхмерного куба nxnxn со сторонами, параллельными осям координат, две противоположные вершины которого размещаются в точках (0,0,0) - вход в аэропорт со стороны лётного поля и (n,n,n)-выход из аэропорта. Холлы аэропота находятся в точках с целыми координатами, причём движение организовано так, что из каждого холла прибывшие пассажиры могут перейти в любой из холлов, у которых ровно одна координата больше соответствующей координаты текущего холла на 1, а остальные две координаты совпадают с соответствующей координатой текущего холла.
Организаторы олимпиады хотят узнать количество различных путей, по которым прибывшие пассажиры могут пройти до выхода из аэропорта.
ФВФ: Выведите колиечство различных путей по модулю 2946859.
  #3  
Старый 13.02.2010, 03:29
гость

 
Сообщений: n/a

у тебя каждый путь - это последовательность длины 3*(n-1) из трех типов движений "вниз", "вправо", "вглубь" (ну или как то так). Каждый тип должен встречаться ровно по n-1 разу.

Т.е., обозначая эти движения цифрами, ты грубо говоря ищещь сколько существует строк длины 3*(n-1), в которых есть n-1 единиц, n-1 двоек, n-1 троек.

Вспоминаем школьный курс комбинаторики. n-1 единиц можно расставить на 3(n-1) местах C(3(n-1), n-1) способами, n-1 двоек на оставшихся 2(n-1) местах - C(2(n-1), n-1)) способами, оставшиеся места пойдут под тройки, т.е 1 способ. Перемножая число способов получишь ответ.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра