Задача №24

[shai_xylyd]

На тикле у меня программа считала 0.000471 секунды на P4 3ГГц и 0.023618 секунды на PDA n311, соответственно.
Ссылку на код выложу позже, что бы дать вам подумать над алгоритмом:)

[shai_xylyd]

Правильная идея уже прозвучала — мое решение здесь.

[steck]

а разве это будет не факториальное разложение числа 1000000?

[shai_xylyd]

Да, оно самое, от разложения до ответа один шаг.

[naething]

Тупое решение на C++ без включения мозга:

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
int v[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for (int i = 1; i < 1000000; ++i)
next_permutation(v, v + 10);
copy(v, v + 10, ostream_iterator<int>(cout));
}

[naething]

С включением мозга:

#include <iostream>

int main()
{
int fact[10];
fact[0] = 1;
for (int i = 1; i < 10; ++i)
fact[i] = i * fact[i — 1];

int a = 0;
int x = 1000000 — 1;

for (int i = 9; i >= 0; --i)
{
int d = x / fact[i];
int j = 0;
for (int k = 0;; ++j)
if (0 == (a & (1 << j)))
if (k++ == d) break;
a |= (1 << j);
std:: cout << j;
x -= d * fact[i];
}
}

[shai_xylyd]

Аналогично решил. Странно, на хабре тру решение почти сразу опубликовали, а там народ по-большей части перебором решает. Наверное, правильные книги в России детям читают:)

[shai_xylyd]

Почти последние три цифры не в том порядке.