Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

e-maxx's blog

By e-maxx, 14 years ago, translation, In English

Tutorial for problem "A. Accounting"

First solution: naive brute

Let's brute all possible values of X, and check each of them. It's easy to understand, that X will be constrained in the same limits as values A and B, that is, from -1000 to 1000 inclusive (obviously, there exists a test for each such X, so we can't decrease these limits).

When we have some fixed value of X, we check it simply by multiplying A by X n times. But, you should be careful with possible integer (and even 64-bit integer :) ) overflow. For example, you should stop multiplying by X if the currect result exceeds 1000 by absolute value already.

Second solution: formula

It's easy to note, that if solution exists, then it is n-th root from |B| / |A| fraction, with changed sign if A and B have different signs and if n is odd (if n is even, then no solution exists). That's why we could just use pow() function (or some analog in your language) to calculate 1 / n-th power of the fraction, and after that we just have to check - is the result integer number or not. Of course, we have to check it with taking into account precision errors: that is, number is integer if it is within 10 - 9 (or some another number) from nearest integer.

Moreover, in this solution you should be careful with zeroes. The worst case is when A = 0, and this case should be checked manually (you should note the difference between B = 0 and B ≠ 0 cases).



It should be told that many of the solutions failed on tests with A = 0, or B = 0, and if these tests were not included in the pretestset, I think, about half of participants would fail to solve this problem :)

  • Vote: I like it
  • +4
  • Vote: I do not like it