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
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6 + 9;
int potrzebuje[maxn], wysyla[maxn];
int wyn[maxn];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	string s1, s2, s3;
	s1='0'+s1;
	s2='0'+s2;
	s3='9'+s3;
	cin >> s1 >> s2 >> s3;
	int n = s1.size(), wyslane, a, b, c;
	long long wynik=0, wynteraz;
	potrzebuje[0]=-1;
	for(int i=1; i<=n; i++) {
		a=s1[i-1]-'0';
		b=s2[i-1]-'0';
		c=s3[i-1]-'0';
		if((a+b)%10 == c) {
			potrzebuje[i]=0;
			wysyla[i]=(int)((a+b)>9);
		}
		else if((a+b+1)%10 == c) {
			potrzebuje[i]=1;
			wysyla[i]=(int)((a+b+1)>9);
			continue;
		}	
		else {
			potrzebuje[i]=-1;
			continue;
		}		
		//idziemy forem do nastepnego potrzebuje = 0
		wyslane=0;
		wynteraz=0;
		for(int j=i; j>=0; j--) {
			if(potrzebuje[j]!=wyslane) {
				break;
			}
			if(potrzebuje[j]==0 && j!=i) {
				wynteraz+=wyn[j];
				break;
			}
			else if(wysyla[j]==1) {
				wyslane=1;
			}	
			else {
				wynteraz++;
				wyslane=0;
			}
		}	
		wyn[i]=wynteraz;
		wynik+=(long long)wyn[i];
	}	
	cout << wynik;
}