Вниз  Алгоритмизация
- 13.12.2015 / 18:35
Askalite
  Пользователь

Askalite 
Сейчас: Offline
Можно хранить размер числа в байтах:
Размер числа:Число размера файла:файл
- 15.12.2015 / 18:19
mcdevil
  Пользователь

mcdevil 
Сейчас: Offline
Всем привет. На олимпиаде была такая задача, есть кенгуру и поле. Размер поля в ширину n клеток, длина 1 клетка. Кенгуру может прыгать k (k=<n) клеток, нужно рассчитать возможные ходы. Например, n=5, k = 2;
  1. Out:
  2. 1 1 1 1 1
  3. 1 2 2
  4. 2 2 1
  5. 2 1 1 1
  6. 1 1 1 2
Как это сделать?

Изменено Ксакеп (17.12 / 10:24) (всего 1 раз)
- 17.12.2015 / 10:25
Ксакеп
  Модератор форума

Ксакеп 
Сейчас: Offline
mcdevil, почему у тебя где-то 5, а где-то 3 ширина поля?
- 17.12.2015 / 11:36
aNNiMON
  Супервизор

aNNiMON 
Сейчас: Offline
Ксакеп, потому что "Out:"
__________________
 let live
- 17.12.2015 / 11:38
Ксакеп
  Модератор форума

Ксакеп 
Сейчас: Offline
aNNiMON, хрень сморозил.
- 17.12.2015 / 11:42
aNNiMON
  Супервизор

aNNiMON 
Сейчас: Offline
Ксакеп, подумай ещё раз. В сумме везде 5. Или тебе нули ещё дописать?
__________________
 let live
- 17.12.2015 / 11:44
Dinisimys
  Пользователь

Dinisimys 
Сейчас: Offline
mcdevil, а откуда кенгуру начинает пригать? С первой клетки? То ли ты что-то не дописал, то ли я тугой
- 17.12.2015 / 12:31
Ксакеп
  Модератор форума

Ксакеп 
Сейчас: Offline
aNNiMON, а, я сначала подумал, это какая-то доска.
mcdevil, динамическое программирование.
- 17.12.2015 / 13:57
Freddy
  Пользователь

Freddy 
Сейчас: Offline
Цитата mcdevil:
Всем привет. На олимпиаде была такая задача, есть кенгуру и поле. Размер поля в ширину n клеток, длина 1 клетка. Кенгуру может прыгать k (k=<n) клеток, нужно рассчитать возможные ходы. Например, n=5,
Можно построить такое дерево, в узлах которого содержится пройденный кенгуру путь. Пример:
В корне дерева элемент со стоимостью 0.
У этого узла - k потомков. Для k = 2 получится:

0
|-1
|-2

Далее строишь для каждого дочернего узла поддеревья, следя за тем условием, чтобы значения в узлах поддеревьев не превысили n. Получится так:

0
|-1
| |-2 (потому что прыжок равен 1 + значение в родителе 1)
| |-3 (потому что прыжок равен 2 + значение в родителе 1)
|
|-2
    |-3 (потому что прыжок равен 1 + значение в родителе 2)
    |-4 (потому что прыжок равен 2 + значение в родителе 2)

Построив дерево целиком, нужно обойти все возможные пути от корня к листьям. Например, первый путь:
0 -> 1 -> 1 (В узле значение 2, у родителя - значение 1. Вычитаем и получаем единицу)... и т. д.

Надеюсь, смысл понятен.
- 17.12.2015 / 14:05
Dinisimys
  Пользователь

Dinisimys 
Сейчас: Offline
Текстовое условие так и не понял, но аннимон хоть просветил насчет исходных данных. Основываясь только на аут, может я и не правильно понял, но вот какойто алгоритм:
  1. m=[1,1...,1]
  2. jmin=n
  3. for(I=0;сумма(m)>=n;I++) {
  4. m[i]=k
  5. jmax=jmin-1
  6. jmin-=k-1
  7. for(j=jmax;j>jmin;j--) {
  8. m[j]=0
  9. }
  10. }
Так на глаз проверил, нету где протестировать. Это так сказать начало, там еще.надо инверсию сделать, чтобы вывести еще и задом наперед все это. Это уже думаю сам сделаешь.
Наверх  Всего сообщений: 127
Фильтровать сообщения
Поиск по теме
Файлы топика (2)