Task[edit]
Solve the "Impossible Puzzle":


X and Y are two different whole numbers greater than 1. Their sum is no greater than 100, and Y is greater than X. S and P are two mathematicians (and consequently perfect logicians); S knows the sum X+Y and P knows the product X*Y. Both S and P know all the information in this paragraph.
The following conversation occurs:

 S says "P does not know X and Y."
 P says "Now I know X and Y."
 S says "Now I also know X and Y!"
What are X and Y?


Guidance
It can be hard to wrap one's head around what the three lines of dialog between S (the "sum guy") and P (the "product guy") convey about the values of X and Y.

So for your convenience, here's a break-down:





 Quote

 Implied fact


 1)

 S says "P does not know X and Y."

 For every possible sum decomposition of the number X+Y, the product has in turn more than one product decomposition.


 2)

 P says "Now I know X and Y."

 The number X*Y has only one product decomposition for which fact 1 is true.


 3)

 S says "Now I also know X and Y."

 The number X+Y has only one sum decomposition for which fact 2 is true.

Terminology:

 "sum decomposition" of a number = Any pair of positive integers (A, B) so that A+B equals the number. Here, with the additional constraint 2 ≤ A < B.
 "product decomposition" of a number = Any pair of positive integers (A, B) so that A*B equals the number. Here, with the additional constraint 2 ≤ A < B.


Your program can solve the puzzle by considering all possible pairs (X, Y) in the range 2 ≤ X < Y ≤ 98, and then successively eliminating candidates based on the three facts. It turns out only one solution remains!

See the Python example for an implementation that uses this approach with a few optimizations.

See also
   Wikipedia:   Sum and Product Puzzle

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
 
std::ostream &operator<<(std::ostream &os, std::vector<std::pair<int, int>> &v) {
    for (auto &p : v) {
        auto sum = p.first + p.second;
        auto prod = p.first * p.second;
        os << '[' << p.first << ", " << p.second << "] S=" << sum << " P=" << prod;
    }
    return os << '\n';
}
 
void print_count(const std::vector<std::pair<int, int>> &candidates) {
    auto c = candidates.size();
    if (c == 0) {
        std::cout << "no candidates\n";
    } else if (c == 1) {
        std::cout << "one candidate\n";
    } else {
        std::cout << c << " candidates\n";
    }
}
 
auto setup() {
    std::vector<std::pair<int, int>> candidates;
 
    // numbers must be greater than 1
    for (int x = 2; x <= 98; x++) {
        // numbers must be unique, and sum no more than 100
        for (int y = x + 1; y <= 98; y++) {
            if (x + y <= 100) {
                candidates.push_back(std::make_pair(x, y));
            }
        }
    }
 
    return candidates;
}
 
void remove_by_sum(std::vector<std::pair<int, int>> &candidates, const int sum) {
    candidates.erase(std::remove_if(
        candidates.begin(), candidates.end(),
        [sum](const std::pair<int, int> &pair) {
            auto s = pair.first + pair.second;
            return s == sum;
        }
    ), candidates.end());
}
 
void remove_by_prod(std::vector<std::pair<int, int>> &candidates, const int prod) {
    candidates.erase(std::remove_if(
        candidates.begin(), candidates.end(),
        [prod](const std::pair<int, int> &pair) {
            auto p = pair.first * pair.second;
            return p == prod;
        }
    ), candidates.end());
}
 
void statement1(std::vector<std::pair<int, int>> &candidates) {
    std::map<int, int> uniqueMap;
 
    std::for_each(
        candidates.cbegin(), candidates.cend(),
        [&uniqueMap](const std::pair<int, int> &pair) {
            auto prod = pair.first * pair.second;
            uniqueMap[prod]++;
        }
    );
 
    bool loop;
    do {
        loop = false;
        for (auto &pair : candidates) {
            auto prod = pair.first * pair.second;
            if (uniqueMap[prod] == 1) {
                auto sum = pair.first + pair.second;
                remove_by_sum(candidates, sum);
 
                loop = true;
                break;
            }
        }
    } while (loop);
}
 
void statement2(std::vector<std::pair<int, int>> &candidates) {
    std::map<int, int> uniqueMap;
 
    std::for_each(
        candidates.cbegin(), candidates.cend(),
        [&uniqueMap](const std::pair<int, int> &pair) {
            auto prod = pair.first * pair.second;
            uniqueMap[prod]++;
        }
    );
 
    bool loop;
    do {
        loop = false;
        for (auto &pair : candidates) {
            auto prod = pair.first * pair.second;
            if (uniqueMap[prod] > 1) {
                remove_by_prod(candidates, prod);
 
                loop = true;
                break;
            }
        }
    } while (loop);
}
 
void statement3(std::vector<std::pair<int, int>> &candidates) {
    std::map<int, int> uniqueMap;
 
    std::for_each(
        candidates.cbegin(), candidates.cend(),
        [&uniqueMap](const std::pair<int, int> &pair) {
            auto sum = pair.first + pair.second;
            uniqueMap[sum]++;
        }
    );
 
    bool loop;
    do {
        loop = false;
        for (auto &pair : candidates) {
            auto sum = pair.first + pair.second;
            if (uniqueMap[sum] > 1) {
                remove_by_sum(candidates, sum);
 
                loop = true;
                break;
            }
        }
    } while (loop);
}
 
int main() {
    auto candidates = setup();
    print_count(candidates);
 
    statement1(candidates);
    print_count(candidates);
 
    statement2(candidates);
    print_count(candidates);
 
    statement3(candidates);
    print_count(candidates);
 
    std::cout << candidates;
 
    return 0;
}