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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
use std::io::{self, BufRead, Write};

fn parse_lines(line: &str) -> Vec<i64> {
    line.split("")
        .filter(|c| !c.is_empty())
        .map(|part| part.parse().unwrap())
        .collect()
}

fn main() {
    let stdin = io::stdin().lock();
    let mut stdout = io::stdout().lock();

    let mut lines = stdin.lines();
    let first_line = lines.next().unwrap().unwrap();
    let second_line = lines.next().unwrap().unwrap();
    let third_line = lines.next().unwrap().unwrap();

    let first_num = parse_lines(&first_line);
    let second_num = parse_lines(&second_line);
    let third_num = parse_lines(&third_line);

    let n = first_num.len();

    let mut dp: Vec<Vec<i64>> = vec![vec![0; n]; 2];
    // dp[d][i] - how many good additions end at index `i`, if we add additional `d`
    // result = sum_{i=0 to n} dp[0][i]

    for (i, (a, (b, c))) in first_num
        .into_iter()
        .zip(second_num.into_iter().zip(third_num))
        .enumerate()
    {
        for d in 0..=1 {
            let mut sum = a + b + d;
            let mut carry = 0;
            if sum >= 10 {
                sum -= 10;
                carry += 1;
            }

            if sum == c {
                if carry == 0 {
                    dp[d as usize][i] += 1;
                }

                if i > 0 {
                    dp[d as usize][i] += dp[carry][i - 1]
                }
            }
        }

        // for d in 0..=9 {
        //     let mut sum = a + b + d;
        //     let mut carry = 0;
        //     while sum >= 10 {
        //         sum -= 10;
        //         carry += 1;
        //     }

        //     if sum == c {
        //         if carry == 0 {
        //             dp[d as usize][i] += 1;
        //         }
        //         if i > 0 {
        //             dp[d as usize][i] += dp[carry][i - 1]
        //         }
        //     }
        // }

        // if i == 0 {
        //     for d in 0..=9 {
        //         if a + b + d == c {
        //             dp[d as usize][0] = 1;
        //         }
        //     }
        // } else {
        //     for d in 0..=9 {
        //         let mut sum = a + b + d;
        //         let mut carry = 0;
        //         while sum > 10 {
        //             sum -= 10;
        //             carry += 1;
        //         }

        //         if sum == c {
        //             if carry == 0 {
        //                 dp[d as usize][i] += 1;
        //             }
        //             dp[d as usize][i] += dp[carry][i - 1]
        //         }
        //     }
        // }
    }

    let result: i64 = dp[0].iter().sum();
    writeln!(stdout, "{}", result).expect("write stdout");
}