CORRCHK - Editorial

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.


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

1 Like

Why the solutions are not accesible ?

@block4o: Please mention which solutions?

I have created a code for this problem, I ran the code on the given sample test case (also using the command prompt and passing a file in.txt that have sample input and code has successfully generated output.txt with the output given in sample), then also while submitting the file it says wrong answer. Would you please tell me why this happened ? I have created the code in C# and logic is similar as mentioned above.