Problem link: contest practice
Difficulty: CakeWalk
Pre-requisites: Numeral systems
Problem: You’re given a lot of statements of the form “A+B=C” (quotes for clarity). How many statements has a numeral system Q between 2 and 16 inclusive such that “A+B=C” is a true statement in the numeral system with a base Q.
Explanation:
This problem was actually the easiest in the set. The solution is simply checking all the possible 15 bases, namely from two to sixteen, inclusive. Here’s a description of it’s implementation in a little more details:
It comes obviously from the task description that there is exactly one “plus” sign in every statement. There’s also exactly one “equal” sign in every statement. If we find them, everything that comes before the “plus” sign is the string A. Anything that is between “plus” and “equal” signs is the string B. The string C is formed by the symbols that are after “equal” sign. Such approach allows to parse the input easily.
Then, if you would like to get 50 points, you can convert these strings into decimal integers (int in C++) and check that A+B=C. If you solve the problem this way, you should not also forget to check before that A, B and C consist only of decimal digits.
In the general case you can just iterate through all the possible bases - as it was already written in the beginning, there are only 15 of them. Like in the previous solution, when you check the base Q, you should check that all the strings consist only of that base’s symbols. For example, if you check the base of 7, A, B and C should consist only of symbols 0 to 6. You shouldn’t also forget to use 64-bit integer type during the checking.
At last, you should not forget to break the cycle loop after finding a suitable base, because a few bases might be fit for a single statement, but we’re interested in the number of statements that has at least one suitable base, not in the total number of suitable bases for each of the statements.
Setter’s solution: link
Tester’s solution: link