Дистанционная подготовка: Какая к черту простая динамика?
Какая к черту простая динамика?
от Никита Пушкин - Суббота 3 Май 2014, 19:23
2963. Калькулятор
  Ну и что тут простого? Как решить эту задачу?
Re: Какая к черту простая динамика?
от Peter Cherepanov - Воскресенье 4 Май 2014, 00:28
  Нужно обходить дерево поиска в ширину и запоминать результаты, чтобы сократить перебор.
Re: Какая к черту простая динамика?
от Никита Пушкин - Воскресенье 4 Май 2014, 00:25
  То есть тупой проход по всем вариантам? Я такое пробовал, в итоге программа зависает на тесте 562340.
Re: Какая к черту простая динамика?
от Григорий Резников - Понедельник 5 Май 2014, 14:25
  Тут проще заходит.
Можно просто утверждать, что a[i]=min(a[i-1],a[i/2],a[i/3]) и убирать последние два параматра,если i не делится на 2 или на 3.
Re: Какая к черту простая динамика?
от Никита Пушкин - Понедельник 5 Май 2014, 22:02
  Я решил просто делить число на 3, если оно делится; в противном случае делю на 2, если оно делится; в противном случае вычитаю 1. Ответ неверный выходит.

А если применять динамическое программирование с массивом и циклом, то массив тупо не поместит в себе 10^6 элементов. Подскажите, как это сделать?

Блин, как вообще все это освоить? Мне это трудно дается.
Re: Какая к черту простая динамика?
от Антон Карабанов - Вторник 6 Май 2014, 15:57
  "массив тупо не поместит в себе 10^6 элементов"
Отчего же? Памяти аж 64 Мб выделено.
Да и времени 3 секунды - можно пешком дойти :)
Re: Какая к черту простая динамика?
от Никита Пушкин - Вторник 6 Май 2014, 20:30
  А я и не знал. Спасибо, теперь почти все проходит. Только тест 10 почему-то не работает. Не подскажете, что не так?
Re: Какая к черту простая динамика?
от Владислав Толстиков - Пятница 24 Июль 2015, 23:40
  Поправка: a[i] = 1 + min (a[i-1],a[i/2],a[i/3])
где у меня ошибка?
от Кирилл Майченко - Понедельник 27 Июль 2015, 02:29
  #include <iostream>

using namespace std;

int main()
{
    int a[100000];
    int n,i,k,l;

    cin >> n;
    a[1] = 0; a[2] = 1; a[3] = 1; a[4] = 2; a[5] = 3;
    a[6] = 2; a[7] = 3; a[8] = 3; a[9] = 3;

    for (i = 10; i <= n; i++)
    {
        if ((i % 2 == 0) || (i % 3 == 0))
        {
            a[i] = 1 + min(min(a[i-1],a[i/2]),a[i/3]);
        } else
        {
            a[i] = a[i-1]+1;
        }
    }

    cout << a[n] << endl;
    return 0;
}

Re: где у меня ошибка?
от Егор Колодин - Пятница 24 Март 2017, 01:53
  Ну хотя бы a[9] = 2
ok
от nikoloz gabriadze - Четверг 1 Ноябрь 2018, 13:27
  4