codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

30.md (1764B)


      1 Source: https://codeforces.com/blog/entry/696
      2 
      3 # Tutorial for problem "A. Accounting"
      4 
      5 ### First solution: naive brute
      6 
      7 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).
      8 
      9 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.
     10 
     11 ### Second solution: formula
     12 
     13 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.
     14 
     15 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).
     16 
     17 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 :)