Branch data     Line data    Source code

       1                 :             : #include <iostream>
       2                 :             : #include <fstream>
       3                 :             : #include <sstream>
       4                 :             : #include <vector>
       5                 :             : #include <cstdint>
       6                 :             : #include <iterator>
       7                 :             : 
       8                 :             : using namespace std;
       9                 :             : 
      10                 :       14252 : bool isValid(uint64_t target, const vector<uint64_t>& nums, size_t idx) {
      11         [ +  + ]:       14252 :   if (idx == 0) {
      12                 :        3058 :     return nums[0] == target;
      13                 :             :   }
      14                 :             : 
      15                 :       11194 :   uint64_t curr = nums[idx];
      16                 :             : 
      17   [ +  +  +  +  :       21677 :   return (target % curr == 0 && isValid(target / curr, nums, idx - 1)) ||
                   +  + ]
      18         [ +  + ]:       21677 :          (target > curr && isValid(target - curr, nums, idx - 1));
      19                 :             : }
      20                 :             : 
      21                 :           2 : int main() {
      22                 :           2 :   ifstream in("input.txt");
      23         [ +  + ]:           2 :   if (!in) {
      24                 :           1 :     cerr << "Error: Could not open input file.\n";
      25                 :           1 :     return 1;
      26                 :             :   }
      27                 :           1 :   uint64_t total = 0;
      28                 :             : 
      29         [ +  + ]:         851 :   for (string line; getline(in, line); ) {
      30                 :         850 :     stringstream ss(line);
      31                 :             :     uint64_t target;
      32                 :             :     char colon;
      33                 :         850 :     ss >> target >> colon;
      34                 :        1700 :     vector<uint64_t> nums{istream_iterator<uint64_t>{ss}, {}};
      35         [ +  + ]:         850 :     total += isValid(target, nums, nums.size() - 1) ? target : 0;
      36                 :         851 :   }
      37                 :             : 
      38                 :           1 :   cout << total << endl;
      39         [ +  + ]:           3 : }