1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <queue>

#define ULL unsigned long long int

using namespace std;

// number of possible combinations in adding to numbers that equals index of array
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	string s;
	queue<pair<int, ULL>> q;

	cin >> s;

	q.push(make_pair(0, 1ULL));

	ULL total_sum = 0ULL;

	while (!q.empty())
	{
		int idx = q.front().first;
		ULL sum = q.front().second;
		q.pop();

		if (idx >= s.length())
		{
			total_sum += sum;
		}

		if (idx >= s.length())
		{
			continue;
		}

		q.push(make_pair(idx + 1, sum * (ULL)arr[s[idx] - '0']));

		if (s[idx] == '1' && idx != s.length() - 1 && s[idx + 1] != '9')
		{
			q.push(make_pair(idx + 2, sum * (ULL)arr[(s[idx] - '0') * 10 + (s[idx + 1] - '0')]));
		}
	}

	cout << total_sum;
}