IT-CON 2012(Фотоотчет)

Начало разбора

IT-CON 2012 (Олимпиада для студентов 3-5 курсов) Разбор + Материалы + Монитор

Условия задач

Разбор:
A. Трехзначные числа
Задачу можно решать перебором всех чисел в интервале [100,999], что дает генерацию чисел в порядке возрастания. Для каждого числа находим сумму цифр и сравниваем ее с заданной. Удовлетворяющие числа будем хранить в динамическом массиве.

Решение 1(конвертация числа в строку)
Решение 2(откусывание последней цифры числа)
Решение 3(перебор цифр)

B. Электронная почта
Задача ну умение переводить буквы латинского алфавита в нижний регистр. Пожалуй самая легкая задача олимпиады.

Решение 1(с использованием функции tolower())
Решение 2(сопоставление заглавных и прописных букв)
Решение 3(с использованием смещения)

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

Решение

D. Уникальные элементы
Самым простым решением было “загнать” все элементы в set и вывести количество элементов получившегося set’a.
В рамках другого решения можно было отсортировать массив любым известным алгоритмом сортировки, алгоритмическая сложность которого не превышала бы квадратичную. В результате можно было перебрать все пары соседних элементов и найти те из них, где текущий элемент не равен последующему. Количество таких пар + 1 является ответом на задачу.

Решение 1 (с использованием set’a)
Решение 2 (с использованием sort’a)
 
E. Сапер
Чисто техническая задача. Жизнь существенно упростит массив движений, в котором нужно записать смещения в 8 направлений:

1. ...
2. int moveX[8] = {-1,-1,-1, 0, 0, 1,1,1};
3. int moveY[8] = {-1, 0, 1,-1, 1,-1,0,1};
4. bool correct(int x, int y) {
5.   if (x < 1 || y < 1) return false;
6.   if (x > n || y > m) return false;
7.   return true;
8. }
9. ...
10. for (int p=0;p<8;++p){
11.   int x = i + moveX[p];
12.   int y = j + moveY[p];
13.   if (correct(x,y) && mas[x][y] !=-1)
14.     ++mas[x][y];
15. ...

* This source code was highlighted with Source Code Highlighter.

Решение

F. Генерация подмножеств
Классическая задача по комбинаторике.
Рассмотрим первое решение. Пусть N = 3. Рассмотрим все числа от 0 до 2^n – 1.
           123
      0 –> 000 = {}
      1 –> 001 = {3}
      2 –> 010 = {2}
      3 –> 011 = {2,3}
      4 –> 100 = {1}
      5 –> 101 = {1,3}
      6 –> 110 = {1,2}
      7 –> 111 = {1,2,3}

Решение 1 (через двоичное представление)
Решение 2 (рекурсивное с построением дерева состояний)

G. Количество нулей у факториала
Стоит заметить, что количество нулей, на которые заканчивается факториал равно количеству десяток в разложении этого факториала на множители. Десятка состоит из двух простых сомножителей. При этом множитель 5 в разложении факториала на простые множители будет встречаться намного реже, чем множитель 2. Поэтому количество нулей у факториала на конце будет равно количеству пятерок в разложении его на простые множители.

Решение 1
Решение 2

H. Язык разметки RHTML 1.0.
Можно применить один из двух подходов: конечный автомат и механизм “откусывания”.
Первый пишется дольше, но работает всегда быстрее и легко масштабируется. Второй способ пишется проще и работает чуть медленнее. Главное аккуратность и обильное тестирование.

Решение 1 (конечный автомат)
Решение 2 (с помощью “откусывания”)
Решение 3 (конечный автомат + С-строка) [Автор: Сагунов Данил]

I. Объединение прямоугольников
Единственная задача, для которой я не писал тесты, а взял оригинальные с задачника Федора Меньшикова.
Я ее уже рассматривал ранее(6D. Площадь прямоугольников)

Решение

J. Путь в матрице
Оригинальное условие задачи находится здесь: http://projecteuler.net/problem=83
Я предполагал решение задачи через алгоритм Дейкстры, но ограничения были подобраны так, что и реализация алгоритма Флойда также укладывались в отведенные лимиты. При таком подходе представляет исходную матрицу в виде графа, где каждая вершина имеет до 4 соседей. Ребро между (i,j) и (i+1,j) вершиной будет иметь вес a[i][j], где a – исходная матрица. После того как граф построен можно запускать вышеописанные алгоритмы.
Участники, сдавшие решения предложили обычный BFS на матрице. Это решение пишется намного проще.

Решение 1(алгоритм Флойда)
Решение 2(алгоритм Дейкстры)
Решение 3(BFS)


Тесты и условия задач: http://goo.gl/DvISB
Авторские решения:     http://goo.gl/lyEjn
Размороженный монитор: http://goo.gl/QOTRa

Нахождение количества компонент связности

Рассмотрим базовую задачу.
Условие:
Дан неориентированный граф G, имеющий N вершин и M ребер. Чтобы все рассмотренные подходы имели практических смысл, ограничим N<=1000.
Необходимо найти количество компонент связности данного графа.

Формат входных данных: В первой строке входного файла находятся N и M, разделенные пробелом. Далее идет M строк, содержащих пару вершин, между которыми находится ребро. Вершины нумеруются с 1.
Формат выходных данный: В единственной строке выдать количество компонент связности графа.

Пример:
input.txt
15 11
1 2
2 3
2 11
10 11
11 12
11 15
4 12
12 13
8 14
7 14
5 6
output.txt
4

Компонента связности неориентированного графа является подграф, в котором для любой пары вершин v и u существует путь. Между двумя различными компонентами связности не существует пути.

Задача стара, как мир. Но тем не менее сегодня покажу несколько подходов по ее решению.

1. Поиск в глубину(DFS)
Самое классическое решение. Даже комментировать особо нечего.

1. const int SIZE = 1e3 + 10;
2. vector<int> adj[SIZE];
3. bool usd[SIZE];
4. ...
5. void dfs(int cur) {
6.   usd[cur] = true;
7.   for (int i=0;i<adj[cur].size();++i) {
8.     int nxt = adj[cur][i];
9.     if (!usd[nxt])
10.       dfs(nxt);
11.   }
12. }
13. int connected_components_amount_dfs() {
14.   int cnt = 0;
15.   for (int i=1; i<=n; ++i) {
16.     if (!usd[i]) {
17.       dfs(i);
18.       ++cnt;
19.     }
20.   }
21.   return cnt;
22. }

* This source code was highlighted with Source Code Highlighter.

Граф храним в виде списка смежности(строка 2). Общая сложность решения $latex O(N + M)$.
Решение

2. DSU подобная структура(ленивый подход)
Будем делать конденсацию компоненты в одну вершину. Идея следующая: будем последовательно обрабатывать ребра. Каждая компонента связности будет представлена одной своей вершиной(титульная). При этом неважно какой. По ходу обработки ребер титульная вершина компонент может меняться.
В итоге для нахождения количества компонент связности нужно найти количество титульных вершин.

1. const int SIZE = 1e3 + 10;
2. int p[SIZE];
3. bool usd[SIZE];
4. ...
5. int connected_components_amount_dsu() {
6.  
7.   scanf("%d %d", &n, &m);
8.  
9.   for (int i=1;i<=n;++i) {
10.     p[i] = i;
11.   }
12.  
13.   for (int i=0;i<m;++i) {
14.     scanf("%d %d", &f, &s);
15.     int par = p[f];
16.     for (int j=1;j<=n;++j) {
17.       if (p[j] == par)
18.         p[j] = p[s];
19.     }
20.   }
21.   for (int i=1;i<=n;++i)
22.     usd[p[i]] = true;
23.   int cnt = 0;
24.   for (int i=1;i<=n;++i) {
25.     if (usd[i]) ++cnt;
26.   }
27.   return cnt;
28. }

* This source code was highlighted with Source Code Highlighter.

Заметим, что сам граф непосредственно вообще никак не хранится. Общая сложность $latex O(M*N)$ 
Решение

3. Система непересекающихся множеств (DSU)
Реализацию, представленную выше можно существенно усовершенствовать. При добавлении нового ребра будем “мерджить меньшее подмножество к большему” + сжимать пути. У emaxx’а рассматривается доказательство того, что ассимптотика обработки одного ребра равна $latex O(\alpha (N))$, где $latex \alpha (N)$ – обратная функция Аккермана.

1. const int SIZE = 1e3 + 10;
2.  
3. int p[SIZE];
4. int size[SIZE];
5.  
6. int par(int x) {
7.   return p[x] == x ? x : p[x] = par(p[x]);
8. }
9. int connected_components_amount_dsu() {
10.  
11.   scanf("%d %d", &n, &m);
12.  
13.   for (int i=1;i<=n;++i) {
14.     p[i] = i;
15.     size[i] = 1;
16.   }
17.  
18.   for (int i=0;i<m;++i) {
19.     scanf("%d %d", &f, &s);
20.     f = par(f); s = par(s);
21.     if (f != s) {
22.       if (size[f] > size[s])
23.         swap(f,s);
24.       p[f] = s;
25.       size[s] += size[f];
26.     }
27.   }
28.   bool usd[SIZE];
29.   memset(usd, 0, sizeof(usd));
30.   for (int i=1;i<=n;++i)
31.     usd[par(i)] = true;
32.   int cnt = 0;
33.   for (int i=1;i<=n;++i) {
34.     if (usd[i]) ++cnt;
35.   }
36.  
37.   return cnt;
38. }

* This source code was highlighted with Source Code Highlighter.

Как и прежде сам граф не хранится в виде матрицы смежности. Общая сложность $latex O(M * \alpha (N))$

4. Алгоритм Флойда.
Этот подход для самых ленивых, правда он требует хранить граф явно в виде матрицы смежности.
Запускаем алгоритм Флойда и строим матрицу достижимости для каждой пары вершин. В результате если первоначально adj[u][v] указывало на наличие ребра между u и v, то после работы алгоритма adj[u][v] будет указывать на наличие пути между u и v. После чего можно написать DFS двумя вложенными циклами.

1. const int SIZE = 1e3 + 10;
2. int adj[SIZE][SIZE];
3. bool usd[SIZE];
4. ...
5. int connected_components_amount_floyd() {
6.  
7.   for (int k=1;k<=n;++k){
8.     for (int i=1;i<=n;++i){
9.       for (int j=1;j<=n;++j){
10.         if (adj[i][k] + adj[k][j] == 2)    
11.           adj[i][j] = 1;
12.       }
13.     }
14.   }
15.  
16.   int cnt = 0;
17.   for (int i=1;i<=n;++i) {
18.     if (!usd[i]) {
19.       ++cnt;
20.       usd[i] = true;
21.       for (int j=1;j<=n;++j) {
22.         if (adj[i][j] && !usd[j])
23.           usd[j] = true;
24.       }
25.     }
26.   }
27.   return cnt; 
28. }

* This source code was highlighted with Source Code Highlighter.

Алгоритм ужасно долгий, но зато пишется довольно просто. Общая сложность $latex O({ N }^{ 3 }) $
Решение

Собственно пока и все. Мы рассмотрели 3 принципиально разных подхода. На маленьких ограничениях можно выбрать тот из них, что больше по душе.

Нахождение номера старшего бита числа

Задача нахождения номера старшего единичного бита числа довольно часто встречается в олимпиадном программировании, например в задаче RMQ.
Рассмотрим четыре способа решения этой задачи. Условимся, что задачу будем решать для целого числа N ($latex 1\leqslant{N}\leqslant{2}^{32}-1$).

1. naive [O(logN)] Первый способ самый простой и очевидный: будем сдвигать N вправо на один бит, пока оно не станет равным 1 (а не 0, так мы сэкономим одну итерацию).

1. inline int high_bit_line(UINT n) {
2.   int res = 0;
3.   while (n != 1) {
4.     n >>= 1;
5.     res++;
6.   }
7.   return res;
8. }

* This source code was highlighted with Source Code Highlighter.

Сложность первого алгоритма - количество цифр в двоичном представлении N, то есть $latex \log_2{N}$.

2. log2 [O(const)] Второй способ математический. Поскольку номер старшего бита - показатель старшей степени двойки, то его номер можно найти с помощью логарифма, округлив его вниз:

1. #include <cmath>
2.  
3. const double EPS = 1e-11;
4. inline double log2(double n) {
5.   return log(n) / log(2.0);
6. }
7. inline int high_bit_log2(UINT n) {
8.   return (int)(log2((double)n) + EPS);
9. }

* This source code was highlighted with Source Code Highlighter.

Вроде бы все классно, но могут возникнуть проблемы с округлением. Поскольку математические операции в cmath могут возвращать неточные значения (например, sqrt(4) = 1.9999...) , то приходится добавлять к их результатам константу. Константа должна быть строго меньше числа, обратного максимальному значению N, иначе это может привести к неправильному результату (например, если к $latex log_2({2}^{32}-1)$ прибавить 10^-9, то результат будет больше 31). Поэтому в нашем случае я взял 10^-11, так как $latex \frac 1 {{2}^{32}} \approx {2}*{10}^{-10}$.
К сожалению, библиотека cmath в Visual Studio не поддерживает функцию log2, поэтому пришлось делать промежуточную функцию. Сложность вычисления логарифма равна константе, но она достаточно велика.

3. Binary search [O(log(logN))] В основе этого способа лежит метод бинарного поиска. Будем брать правую часть числа (в двоичном представлении), пока она не равна нулю, а иначе берем левую часть, постепенно деля число пополам, пока не получим 1:

1. inline int high_bit_bs(UINT n){
2.   int size = sizeof(n) * 4;
3.   int res = 0;
4.   while (n != 1) {
5.     int l = n >> size;
6.     if (l) {
7.       n = l;
8.       res += size;
9.  
10.     } else {
11.       n ^= l << size;
12.     }
13.     size >>= 1;
14.   }
15.   return res;
16. }

* This source code was highlighted with Source Code Highlighter.

Рассмотрим применение этого алгоритма к числу 1234567890.

$latex 0 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 | 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0$ res = 0; size = 16;

$latex 0 1 0 0 1 0 0 1|1 0 0 1 0 1 1 0$ res = 16; size = 8;

$latex 0 1 0 0|1 0 0 1$ res = 24; size = 4;

$latex 0 1|0 0$ res = 28; size = 2;

$latex 0|1$ res = 30; size = 1;
Сложность этого способа равна логарифму от числа битов N, то есть $latex \log _{ 2 } (\log _{ 2 }{ N } )$.

4. Binary search with mask [O(log(log(N)))]
Да, я не ошибся, сложность четвертого алгоритма почти равна сложности третьего, так как этот способ является всего лишь небольшой оптимизацией предыдущего. В третьем алгоритме мы находим правую часть числа через левую (строка 9). Здесь мы затрачиваем две операции: битового сдвига и исключающего ИЛИ (XOR). Эти операции можно заменить на сложение и И (AND), добавив константный массив масок:

const int MASK_R[6] = {0x0000FFFF, 0x000000FF, 0x0000000F, 0x00000003, 0x00000001};

Немного исправив код третьего способа, получаем:

1. inline int high_bit_bsm(UINT n){
2.   int size = sizeof(n)*4;
3.   int res = 0;
4.   int m = 0;
5.   while (n != 1) {
6.     int l = n >> size;
7.     if (l) {
8.       n = l;
9.       res += size;
10.     } else {
11.       n &= MASK_R[m];
12.     }
13.     size >>= 1;
14.     m++;
15.   }
16.   return res;
17. }

* This source code was highlighted with Source Code Highlighter.

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

Выводы: Подход с бинарным поиском  дает наилучший результат.
Если нужно решать поставленную задачу на ограниченном диапазоне, который можно хранить в памяти, то лучше динамикой подсчитать позицию старшего единичного бита для каждого числа в диапазоне.
Эта идея хорошо описана в вики конспектах ИТМО(Раздел “Применение к задаче RMQ”).

Problem 377 [ProjectEuler.net]

 

 

 

[Условие задачи]
Решать задачу начнем с простого.
Для начала найдем $latex f(13)$. Это можно сделать несложным рекурсивно-комбинаторным алгоритмом, который оставим для самостоятельной проработки.
Итог: $latex f(13)=3835856884757$

Получить $latex f(169)$ тем же алгоритмом вряд ли получится.
Далее будет описан алгоритм, который может это сделать. Представленную логику можно применить для любой степени 13.

Введем интуитивно понятные термины:
Префикс длины L числа N – первые L цифр (старшие разряды) числа N.
Постфикс длины L числа N – последние L цифр (младшие разряды) числа N.
Сумма префикса/постфикса – сумма цифр, входящих в префикс/постфикс.
Под промежуточным числом будем понимать число, которое используется при подсчете значения $latex f({ 13 }^{ k })$, так например число 1121 является промежуточным для $latex f(5)$
По условию задачи нужно найти последние 9 цифр ответа. Минимальным постфиксом длины 9 промежуточного числа для $latex f(169)$ является 111111111, а максимальным - 999999999. Т.к. в условии оговорено, что в состав промежуточного числа не входит ноль, то можно сделать утверждение, что количество различных постфиксов длины 9 для промежуточных чисел будет ровно $latex { 9 }^{ 9 }=387 420 489$, а различных сумм заданных постфиксов $latex 81-9+1=73$.
Для фиксированного постфикса промежуточного числа найдем количество возможных префиксов. Пусть сумма постфикса равна $latex S$, тогда сумма префикса равна $latex 169-S$.
Пусть $latex G(N)$ – функция которая возвращает количество всевозможных префиксов, сумма цифр которых равна $latex N$. Остаточные знания нам навевают понятие Разбиение числа на слагаемые, но в нашем случае нужно использовать не разбиение, а Композицию числа на слагаемые.
В общем случае количество композиций числа $latex N$ на ненулевые слагаемые равно $latex { 2 }^{ N-1 }$, но это только в том случае, если нет ограничений на слагаемые. В нашем же случае каждое ненулевое слагаемое должно не превышать 9.
Для того, чтобы найти $latex G(N)$ вспомним старую задачу Зайчик. Если вникнуть, то можно увидеть, что в этой задаче как раз и ищется функция $latex G(N)$ с ограничением на максимальное слагаемое.
Получаем: $latex \displaystyle G(N)=\left\{\begin{matrix}1, N=0\\ 2^{N-1}, 1<=N<=9\\ \sum_{i=1}^{9}G(N-i), N>9\end{matrix}\right.$
Последняя формула выглядит весьма угрожающе. В интернетах находим, что $latex G(N)$ образует последовательность чисел, называемых Fibonacci 9-step numbers.
И вот наверное сейчас мы подошли к самому интересному. $latex G(169-9)$ мы еще сможем найти, а как быть если степень 13 будет велика. Нужен способ, который находит G(N) быстрее чем за O(N).
В книге “Программирование. Теоремы и задачи”(А.Шень) приводится пример, как можно найти N-ое число Фибоначчи за O(logN) с помощью быстрого возведения в степень начальной матрицы. Тот же принцип можно использовать и здесь. Приведу фрагмент, по которому можно понять общую логику:

1. typedef unsigned long long ULL;
2. const ULL OSN = (ULL)1e9;
3. const ULL BASE[SIZE][SIZE] = {
4.   {128, 64, 32, 16, 8, 4, 2, 1, 1},
5.   {64, 32, 16, 8, 4, 2, 1, 1, 0},
6.   {32, 16, 8, 4, 2, 1, 1, 0, 0},
7.   {16,  8, 4, 2, 1, 1, 0, 0, 0},
8.   {8,  4, 2, 1, 1, 0, 0, 0, 0},
9.   {4,  2, 1, 1, 0, 0, 0, 0, 0},
10.   {2,  1, 1, 0, 0, 0, 0, 0, 0},
11.   {1,  1, 0, 0, 0, 0, 0, 0, 0},
12.   {1,  0, 0, 0, 0, 0, 0, 0, 0}
13. };
14. const ULL A[SIZE][SIZE] = {
15.   {1, 1, 0, 0, 0, 0, 0, 0, 0},
16.   {1, 0, 1, 0, 0, 0, 0, 0, 0},
17.   {1, 0, 0, 1, 0, 0, 0, 0, 0},
18.   {1, 0, 0, 0, 1, 0, 0, 0, 0},
19.   {1, 0, 0, 0, 0, 1, 0, 0, 0},
20.   {1, 0, 0, 0, 0, 0, 1, 0, 0},
21.   {1, 0, 0, 0, 0, 0, 0, 1, 0},
22.   {1, 0, 0, 0, 0, 0, 0, 0, 1},
23.   {1, 0, 0, 0, 0, 0, 0, 0, 0}
24. };
25. const ULL E[SIZE][SIZE] = {
26.   {1, 0, 0, 0, 0, 0, 0, 0, 0},
27.   {0, 1, 0, 0, 0, 0, 0, 0, 0},
28.   {0, 0, 1, 0, 0, 0, 0, 0, 0},
29.   {0, 0, 0, 1, 0, 0, 0, 0, 0},
30.   {0, 0, 0, 0, 1, 0, 0, 0, 0},
31.   {0, 0, 0, 0, 0, 1, 0, 0, 0},
32.   {0, 0, 0, 0, 0, 0, 1, 0, 0},
33.   {0, 0, 0, 0, 0, 0, 0, 1, 0},
34.   {0, 0, 0, 0, 0, 0, 0, 0, 1}
35. };
36. ULL G(ULL n) {
37.   ULL res = 0;
38.   if (n <= 9) {
39.     res = _pow(2, n - 1);
40.   }
41.   else {
42.     matrix AN = E, cur = A;
43.     n -= SIZE - 2;
44.     while (n) {
45.       if (n & 1)
46.         AN = AN * cur;
47.       cur = cur * cur;
48.       n >>= 1;
49.     }
50.     matrix fin = matrix(BASE) * AN;
51.     res = fin.data[0][1];
52.   }
53.   return res;
54. }

* This source code was highlighted with Source Code Highlighter.

Все нужные кирпичики описаны. Теперь соберем их в общую картину. 
Последние 9 цифр суммы всех промежуточных чисел для $latex f(169)$ c фиксированным постфиксом можно найти по формуле: $latex postfix*G(169-sum(postfix))mod1e9$. Перебрав все возможные постфиксы можно найти и само значение $latex f(169)$. Для всех остальных степеней 13, как уже говорилось ранее, применима такая же логика. 
Можно предложить несколько схем, ускоряющих общие вычисления. Но их мы оставим для самостоятельной проработки.

Расстановка знаков в арифметическом выражении

[Все темы по размещениям]

Задача: 155. Дешифровка выражения(contester.tsure.ru) [Условие]
Предварительные темы:    [Генерация всех размещений с повторениями рекурсивным способом]
                         [Генерация следующего размещения с повторениями]
                         [Подсчет арифметического выражения(обратная польская нотация)]
Дополнительная практика: Задачи для подсчета арифметического выражения (см. занятие 4 - архив)

Итак, имеется корректное арифметическое выражение вида (9?8)?(0?3)?2=-25, вместо знаков ? необходимо поставить одну из 4 операций +,-,*,/ так, чтобы выражение стало правильным. Если такого сделать нельзя, то нужно вывести “No solution.”. Для удобства гарантируется, что в левой части выражения все числа являются цифрами и отсутствуют унарные знаки. В правой же части может быть любое число по модулю не превышающее 10¹⁵.

Опять же для удобства рассмотрим более короткий пример: 2?(3?4)=-10
Алфавит знаков содержит четыре элемент: {+,-,/,*}.
Количество позиций в размещении(количество знаков ? в выражении): 2
Общее количество размещений: 4²=16

Сгенерируем все размещения с повторениями рекурсивным способом и получим все возможные комбинации исходного арифметического выражения:

1. 2+(3+4)=9
2. 2+(3-4)=1
3. 2+(3*4)=14
4. 2+(3/4)=2
5. 2-(3+4)=-5
6. 2-(3-4)=3
7. 2-(3*4)=-10
8. 2-(3/4)=2
9. 2*(3+4)=14
10. 2*(3-4)=-2
11. 2*(3*4)=24
12. 2*(3/4)=0
13. 2/(3+4)=0
14. 2/(3-4)=-2
15. 2/(3*4)=0
16. 2/(3/4)=NAN

* This source code was highlighted with Source Code Highlighter.

Значение NAN обозначает, что в выражении присутствует деление на ноль. Сам подсчет будем делать с помощью перевода в обратную польскую запись, подсчетом значения на лету.
Подсчет значения на лету можно сделать так:

1. string opers = "+-*/";
2. bool calc(INT &f, INT &s, char op, INT &res) {
3.   switch(op) {
4.     case '+' : res = f + s; return true;
5.     case '-' : res = f - s; return true;
6.     case '*' : res = f * s; return true;
7.     case '/' : if (s != 0) {
8.             res = f / s;
9.             return true;
10.           }
11.           return false;
12.   }
13.   return false;
14. }
15. bool calc_last (stack<INT> &val, stack<char> &oper) {
16.   INT s = val.top(); val.pop();
17.   INT f = val.top(); val.pop();
18.   INT r = -1;
19.   if (calc(f,s,oper.top(),r)) {
20.     val.push(r);
21.     oper.pop();
22.     return true;
23.   }
24.   return false;
25. }
26. int prior(char op) {
27.   switch(op) {
28.     case '+':
29.     case '-': return 0;
30.     case '*':
31.     case '/': return 1;
32.   }
33.   return -1;
34. }
35. bool is_num(char c) {
36.   return '0' <= c && c <= '9';
37. }
38. bool calc(const string &expr, INT &res) {
39.   stack<INT> val;
40.   stack<char> oper;
41.   for (int i=0;i<expr.size();++i) {
42.     if (is_num(expr[i]))
43.       val.push(expr[i] - '0');
44.     else if (expr[i] =='(')
45.       oper.push(expr[i]);
46.     else if (expr[i] == ')') {
47.       while (oper.top() != '(') {
48.         if (!calc_last(val, oper))
49.           return false;
50.       }
51.       oper.pop();
52.     }
53.     else { // expr[i] - операция
54.       while (!oper.empty()) {
55.         if (prior(oper.top()) >= prior(expr[i])) {
56.           if (!calc_last(val, oper))
57.             return false;
58.         }
59.         else break;
60.       }
61.       oper.push(expr[i]);
62.     }
63.   }
64.   while (!oper.empty()) {
65.     if (!calc_last(val,oper))
66.       return false;
67.   }
68.   res = val.top();
69.   return true;
70. }

* This source code was highlighted with Source Code Highlighter.

Исходный код: здесь

Отправляем в систему проверки на contester.tsure.ru и получаем вердикт: TLE9. =))
В худшем случае количество операций равно 10, значит общее количество генерируемых размещений будет 4¹⁰=1048576. Получается, что приведенный фрагмент кода подсчета значения выражения на лету будет запускаться более 1 млн. раз. Т.к. в данной задаче нам придется генерировать все размещения, то естественным путем оптимизации исходного решения – минимизировать количество построений обратной польской записи.
Рассмотрим несколько выражений и их обратные польские записи.

Номер     Выражение           Обратная польская запись
1         5*2+3-(7+2)/2       5 2 * 3 + 7 2 + 2 / -
2         5/2-3+(7-2)*2       5 2 / 3 – 7 2 – 2 * + 
3         5+2*3/(7*2)-2       5 2 3 * 7 2 * / + 2 -
4         5-2/3*(7/2)+2       5 2 3 / 7 2 / * – 2 +

Подсчет выражения по обратной польской записи осуществляется за 1 проход.
Т.к. соответствующие операции в выражениях 1 и 2 имеют одинаковые приоритеты, то для них получаются две обратные польские записи, которые можно считать подобными. Тоже самое можно наблюдать для выражений 3 и 4.
Две обратные польские записи назовем подобными, если соответствующие операции имеют одинаковый приоритет.
Все операции можно разбить на две группы:
1. С меньшим приоритетом(0) : + , -
2. С большим приоритетом(1) : * , /

Поэтому изначально можно сгенерировать до 2¹⁰=1024 размещений из приоритетов [0 и 1]. При этом, если на место операции выпадает 0 в размещении это говорит о том, что на ее место будут последовательно поставлены операции с нулевым приоритетом, т.е + или –.
Для выражений с одинаковыми размещениями приоритетов получаются подобные обратные польские записи.

Рассмотрим выражение:              5?2?3?(7?2)?2
Текущее размещение из приоритетов: {1, 0, 0, 0, 1} 
Обратная польская запись:          5 2 [1] 3 [0] 7 2 [0] 2 [1] [0], где [x] – операция с приоритетом x
Как можно заметить, текущая обратная польская запись соответствует 1 и 2 выражению из таблицы.

Далее подумаем, как можно перебрать конкретные знаки, с уже расставленными приоритетами операций.
Для текущего размещения R можно поставить в соответствие два размещения F и S.
При этом длина F равна количеству нулей в размещении R, а длина S – количеству единиц.
Элементы множества F будут состоять из операций с нулевым приоритетом, а S – из элементом с единичным приоритетом.

Номер   Выражение        R              F           S
1       5*2+3-(7+2)/2    {1,0,0,0,1}    {+,-,+}     {*,/}
2       5/2-3+(7-2)*2    {1,0,0,0,1}    {-,+,-}     {/,*}
3       5+2*3/(7*2)-2    {0,1,1,1,0}    {+,-}       {*,/,*}
4       5-2/3*(7/2)+2    {0,1,1,1,0}    {-,+}       {/,*,/}

Все вышеизложенную идею можно описать так. При этом получается, что в худшем случае придется генерировать 2¹⁰=1024 обратных польских записей вместо 4¹⁰=1048576. Благодаря этим преобразованием последнее решение уложилось в 1.5 секунды на сервере проверки.

В целях рефакторинга второй реализации можно скрестить генерацию размещений R и {F,S}.

Получение номера по размещению с повторениями

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Ранее мы научились генерировать размещение с повторениями по номеру. Как выяснилось вся задача свелась к переводу числа из 10-ой в k-ричную систему счисления. Текущая задача представляет собой обратное действие, следовательно будем переводить “число” из k-ричной в 10-ую систему.

Пусть размещение R = {2, 0, 2, 2, 1, 1, 1, 2}; n = 8; k = 3. Найдем номер этого размещения в лексикографическом порядке.
20221112₃=2*2187+0*729+2*243+2*81+1*27+1*9+1*3+2*1=4374+486+162+27+9+3+2=5063₁₀.

Учитывая, что нумерация всех размещений начинается с 0, получаем что размещение R имеет порядковый номер 5064.

1. typedef unsigned long long ULL;
2. ULL get_num_by_placement_rep(const vector<int> &cur, int n, int k) {
3.   ULL num = 0;
4.   ULL step = 1;
5.   for (int i=cur.size()-1;i>=0;--i) {
6.     num += cur[i] * step;
7.     step *= k;
8.   }
9.   return num;
10. }

* This source code was highlighted with Source Code Highlighter.

Генерация размещения с повторениями по номеру

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008
Практика: [82. Все строки длины n из k различных символов]

Как и ранее алфавитом будем считать первые k цифр начиная с нуля. Длина размещения равна n. Необходимо по номеру сгенерировать размещение с повторениями в лексикографическом порядке.
Для начала давайте рассмотрим все размещения с повторениями для n = 2 и k = 4:

1. 00
2. 01
3. 02
4. 03
5. 10
6. 11
7. 12
8. 13
9. 20
10. 21
11. 22
12. 23
13. 30
14. 31
15. 32
16. 33

Внимательный читатель возможно уже нашел закономерность между порядковым номером и размещением. Если внимательно присмотреться, то можно заметить, что размещения с повторениями это числа в k-ричной системе счисления и их перечисление в лексикографическом порядке полностью совпадает с их перечислением в порядке возрастания.
Проверим наше утверждение на размещении “31”: 31₄=4*3+1=13. Но размещение “31” соответствует 14 размещению. Номер 13 получился, потому что нумерация размещений изначально начинается с 0.
Данная логика отображена в следующей функции:

1. typedef unsigned long long ULL;
2. void gen_placement_rep_by_num(vector<int> &cur, ULL num, int n, int k) {
3.   cur.assign(n,0);
4.   int pos = n - 1;
5.   while (num) {
6.     cur[pos--] = num % k;
7.     num /= k;
8.   }
9. }

* This source code was highlighted with Source Code Highlighter.

Если значения n и k настолько велики, что не помещаются в unsigned long long необходимо использовать длинную арифметику.

Генерация следующего и предыдущего размещения с повторениями

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Пусть задан алфавит, состоящих из первых k цифр, начиная с 0. Также имеется текущее размещение с повторениями длины n. Найдем следующее размещение с повторениями в лексикографическом порядке.

R_i = {1, 5, 6, 4, 6}; n = 5; k = 7
R_i+1 = {1, 5, 6, 5, 0}

Для генерации следующего размещения будем пользоваться простым правилом:
Перебираем все элементы справа налево. Если текущий элемент равен k-1, тогда обнуляем его и переходим к элементу левее. В противном случае увеличиваем текущий элемент на 1 и заканчиваем генерацию. Если на текущем шаге были перебраны все элемента размещения, но не получилось инкрементировать никакой элемент, значит на текущем шаге мы работали с последним размещением для заданных n и k.

1. bool next_placement_rep(vector<int> &cur, int n, int k) {
2.   int r = 1;
3.   int pos = n-1;
4.   while (pos>=0 && r) {
5.     cur[pos]++;
6.     r = cur[pos] == k;
7.     if (r) cur[pos] = 0;
8.     --pos;
9.   }
10.   return !r;
11. }

* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь

Генерация предыдущего размещения делается по аналогичной схеме:

1. bool prev_placement_rep(vector<int> &cur, int n, int k) {
2.   int r = 1;
3.   int pos = n-1;
4.   while (pos >=0 && r) {
5.     cur[pos]--;
6.     r = cur[pos] == -1;
7.     if (r) cur[pos] = k-1;
8.     --pos;
9.   }
10.   return !r;
11. }

* This source code was highlighted with Source Code Highlighter.

Генерация всех размещений с повторениями рекурсивным способом

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008
Практика: Все строки длины n из k различных символов

Пусть задан алфавит из K первых цифр, начиная с 0. Необходимо сгенерировать все размещения с повторениями длины N для элементов данного алфавита. Другими словами для N = 2 и K = 4 получаем:

1. 00
2. 01
3. 02
4. 03
5. 10
6. 11
7. 12
8. 13
9. 20
10. 21
11. 22
12. 23
13. 30
14. 31
15. 32
16. 33

Генерация такой последовательности не должно составить большого труда:

1. void gen(int pos) {
2.   if (pos == n) {
3.     for (int i=0;i<n;++i)
4.       printf("%d",cur[i]);
5.     printf("\n");
6.     return;
7.   }
8.   for (int i=0;i<k;++i) {
9.     cur[pos] = i;
10.     gen(pos+1);
11.   }
12. }

* This source code was highlighted with Source Code Highlighter.

Изначально функция gen запускается с параметром 0.
Полное решение: здесь

Генерация размещения без повторений по номеру за O(N*N)

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: [3784. Генерация размещений]

Ранее мы рассмотрели получение номера по размещению за O(N*N). В данной же задаче нужно сделать все с точностью до наоборот:

1. int placement_amount(int n, int m) {
2.   int res = 1;
3.   for (int i = n; i >= n-m+1; --i) {
4.     res *= i;
5.   }
6.   return res;
7. }
8. void gen_placement_by_num(int num, int n, int m, vector<int> &mas) {
9.   vector<bool> usd(n,false);
10.   int _n = n-1, _m = m-1;
11.   for (int i=0;i<m;++i) {
12.     int block_cnt = num / placement_amount(_n,_m);
13.     num -= block_cnt * placement_amount(_n,_m);
14.     int pos = 0;
15.     ++block_cnt;
16.     while (block_cnt) {
17.       if (!usd[pos])
18.         --block_cnt;
19.       ++pos;
20.     }
21.     usd[pos-1] = true;
22.     mas[i] = pos;
23.     --_n; --_m;
24.   }
25. }

* This source code was highlighted with Source Code Highlighter.

При многократном вызове функции gen_placement_by_num можно сделать препроцессинг и не использовать функцию placement_amount.

Получение номера по размещению без повторений за O(N*N)

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004.
Практика: 192. По размещению!

Рассмотрим все размещения для n = 4 и m = 3:

1. 123
2. 124
3. 132
4. 134
5. 142
6. 143
7. 213
8. 214
9. 231
10. 234
11. 241
12. 243
13. 312
14. 314
15. 321
16. 324
17. 341
18. 342
19. 412
20. 413
21. 421
22. 423
23. 431
24. 432

* This source code was highlighted with Source Code Highlighter.

Можно заметить, что все размещения можно разбить на 4(n) блока. Элементы первого блока начинаются на 1, второго - на 2 и т.д. В каждом блоке находится равное количество элементов равное (n-1)!/(n-m)!. В нашем случае по 6 элементов.
Зная значения n и m и текущее размещение, можно найти размер блока B и определить интервал [L,R], в котором лежат все размещения, начинающиеся на общий первый элемент.
L = B * LESS, где LESS - количество элементов алфавита, меньших первого элемента размещения.
R = L + B – 1.
Далее извлекаем первый элемент размещения из общего алфавита и решает ту же задачу для n`=n-1 и m`=m-1. Рассмотрим идею на конкретном примере:
Пусть n = 9, m = 7. Размещение R = {6, 3, 8, 1, 9, 4, 7}.

Итерация	Размещение	Размер блока	Нижняя граница	Неиспользованный члены
1	6******	8!/2! = 20160	5*20160 = 100800	123456789
2	63*****	7!/2! = 2520	2*2520  =   5040	12345789
3	638****	6!/2! = 360	5*360   =   1800	1245789
4	6381***	5!/2! = 60	0*60    =      0	124579
5	63819**	4!/2! = 12	4*12    =     48	24579
6	638194*	3!/2! = 3	1*3     =      3	2457
7	6381947	2!/2! = 1	2*1     =      2	257

Номер размещения будет равен сумме нижних границ интервалов на каждой итерации:
100800+5040+1800+0+48+3+2 = 107693. Полученный номер был получен с тем расчетом, что изначально все размещения нумеровались с нуля.
Все вышесказанное можно реализовать таким образом:

1. int placement_amount(int n, int m) {
2.   int res = 1;
3.   for (int i = n; i >= n-m+1; --i) {
4.     res *= i;
5.   }
6.   return res;
7. }
8. int get_num_by_placement(const vector<int> &mas, int n, int m) {
9.   vector<bool> usd(n,false);
10.   int res = 0;
11.   int _n = n-1, _m = m-1;
12.   for (int i=0;i<mas.size();++i) {
13.     int amount = 0;
14.     for (int j=0;j<n;++j) {
15.       if (!usd[j]) amount++;
16.       if (mas[i] == j) {
17.         int ampt = (amount - 1) * placement_amount(_n, _m);
18.         res += (amount - 1) * placement_amount(_n, _m);
19.         usd[j] = true;
20.       }
21.     }
22.     usd[mas[i]] = true;
23.     --_n; --_m;
24.   }
25.   return res;
26. }

* This source code was highlighted with Source Code Highlighter.

Генерация следующего и предыдущего размещения без повторений за O(N)

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: K4.Размещения.(dl.gsu.by)

На текущий момент мы умеем генерировать следующее размещение в лексикографическом порядке со сложностью O(N*N) и O(N*log(N)). Сегодня сделаем эту операцию с линейной сложностью. Для этого нужно будет вспомнить алгоритм генерации следующей перестановки в лексикографическом порядке. Для удобства я буду пользовать STL’ным аналогом next_permutation. Итак начнем по порядку.

Пусть n = 9, m = 5. В качестве алфавита будем использовать цифры от 1 до 9. Рассмотрим текущее размещение P_i = {1,2,4,9,8}. Найдем следующее размещение P_i+1 в лексикографическом порядке.
Поставим во взаимно-однозначное соответствие текущему размещению P_i перестановку Perm_i, префикс которой равен Pi, а постфикс формируется из оставшихся минимальных элементов алфавита, не использованных в P_i.

Permi	124983567	Формируем перестановку Permi.
	124987653	Реверсируем хвост перестановки
Permi+1	125346789	Генерируем следующую перестановку в лексикографическом порядке.

Получив перестановку Perm_i+1, отбрасываем хвост и получаем следующее размещение P_i+1= {1,2,5,3,4}.
Если на каком-то этапе не получилось сгенерировать следующую перестановку, значит на текущем этапе обрабатывалось последнее размещение в лексикографическом порядке.

1. bool next_placement(string &perm, int m) {
2.   reverse(perm.begin()+m, perm.end());
3.   return next_permutation(perm.begin(), perm.end());
4. }

* This source code was highlighted with Source Code Highlighter.

Т.к. выполнение реверса хвоста и генерация следующей перестановки имеют сложность O(N), то и генерация следующего размещения так же будет иметь линейную сложность.
Полная реализация: здесь

Генерация предыдущего размещения выполняется таким же образом.

1. bool prev_placement(string &perm, int m) {
2.   reverse(perm.begin()+m, perm.end());
3.   return prev_permutation(perm.begin(), perm.end());
4. }

* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь

Генерация следующего размещения без повторений за O(N*N) и O(N*log(N))

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: K4.Размещения.(dl.gsu.by)

Пусть n = 9, а m = 6. Рассмотрим текущее размещение P_i = {1,3,6,5,9,8}. Найдем следующее размещение P_i+1 в лексикографическом порядке. Алфавитом в данном случае будет являться набор цифр от 1 до 9.

Для начала разделим все элементы алфавита на две группы: те, что входят в текущее размещение P_i и те, что нет(множество F - свободные члены): 

136598247

Будем последовательно перебирать элементы размещения P_i справа налево. Если на каком-то этапе для текущего элемента размещения P_i[j] можно найти элемент F[k] из свободных членов, который больше его, то заменяем P_i[j] на F[k]. При этом F[k] должен быть минимально возможным. При этом может возникнуть две ситуации:
1) Это сделать удалось. При это нужно дополнить размещение так, чтобы ее размер стал равным m. Для этого на свободные места последовательно добавляем элементы множества F в порядке возрастания начиная с самого маленького.
2) Этого сделать не удалось. Текущий элемент P_i[j] удаляем из текущего размещения и добавляем в множество F. Берем следующий элемент P_i[j-1] и повторяем итерацию. Если же не удалось найти такой элемент, значит на текущей итерации мы работали с последним размещением в лексикографическом порядке.

Давайте получим размещение P_i+1 по вышеизложенным правилам:

Pi   =	136598247	Нет свободного элемента больше 8
	136592478	Нет свободного элемента больше 9
	136524789	Есть 3 свободных элемента больше 5: 7,8,9. Выбираем 7 и меняем их местами
	136724589	Первые 4 элемент размещения Pi+1 определены
Pi+1 =	136724589	Дополняем префикс размещения Pi+1

Данный подход можно реализовать со сложностью O(N*N):

1. string letters = "1234567";
2. bool next_placement(string &cur, vector<bool> &usd, int n, int m) {
3.   int beg = -1;
4.   for (int i=m-1;i>=0;--i) {
5.     if (beg != -1) break;
6.     for (int j=cur[i] - letters[0] + 1; j < n; ++j) {
7.       if (!usd[j]) {
8.         usd[j] = true;
9.         usd[cur[i] - letters[0]] = false;
10.         cur[i] = letters[j];
11.         beg = i;
12.         break;
13.       }
14.     }
15.     if (beg == -1)
16.       usd[cur[i] - letters[0]] = false;
17.   }
18.   if (beg != -1) {
19.     for (int i=beg+1, j = 0; i<m && j<n;++j) {
20.       if (!usd[j]) {
21.         usd[j] = true;
22.         cur[i++] = letters[j];
23.       }
24.     }
25.     return true;
26.   }
27.   else
28.     return false;
29. }

* This source code was highlighted with Source Code Highlighter.

Рассмотрим параметры, передаваемые в функцию next_placement:
1. cur – текущее размещение.
2. usd – массив меток. Если usd[i] == false, значит i-ый элемент алфавита является свободным членом.
Т.к. текущее размещение cur передается по ссылке, то после выполнения функции оно заменится на следующее размещение в лексикографическом порядке.

Полная реализация: здесь

Немного подумав, можно смело заменить массив меток на множество(set) свободных членов, улучшив асимптотику до O(N*log(N)):

1. bool next_placement(string &cur, set<char> &vac, int n, int m) {
2.   set<char>::iterator it;
3.   for (int i=cur.size()-1;i>=0;--i) {
4.     it = vac.lower_bound(cur[i]);
5.     if (it != vac.end()) {
6.       char tmp = cur[i];
7.       cur[i] = *it;
8.       vac.erase(it);
9.       vac.insert(tmp);
10.       for (int pos = i+1; pos < m; ++pos) {
11.         cur[pos] = *vac.begin();
12.         vac.erase(vac.begin());
13.       }
14.       return true;
15.     }
16.     vac.insert(cur[i]);
17.   }
18.   return false;
19. }

* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь