Блог пользователя Zakaas

186 (Div. 2) A — Power function failure
Автор Zakaas, 11 лет назад, По-английски

During the round I got 6 WA for problem A. This is my solution 3804729.

I was using math pow function for generating a number from it's digits. Simply like this - pow(10, j), 0 < j < number of digits.

After the contest I found that each time pow was returning floor results. So I used for loop instead of pow and it worked 3804738.

And most frustrating thing is that first solution is giving correct result for each test case on my PC. Can anyone please tell me why pow function failed in this case?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You should notice that you can only remove the last digit and the one before it. Math is a great solution if we can remove anyone all digits.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually problem is not about removal of digits, it is about failure of power function. I am removing last digit by this 'n/10' and using power function to remove the digit before last.

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The pow function works as it should. It doesn't compute precise integer powers, but rather a floating point result, which may differ slightly from the true value.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Okay, got it!

    Then what will be the alternative for pow function to calculate integer powers? for loop is not always efficient.

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      There is no standard alternative. A for loop is good enough, because with standard integer types you can't do too many iterations without overflow. If you use long arithmetic or have to compute large powers modulo something, then use binary exponentiation: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

      → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Fast exponentiation or precalculation should work for you. The latter, for example, can help in polynomial hashing.

      Here is an example of non-recursive implementation of binary exponentiation:

      int a = 10, b = 5;
int res = 1;
for (; b; b >>=1, a *= a)
  if (b & 1) res *= a;
printf("10^5=%d", res);
      → Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Instead of pow function , you should use powf function and you will then see that it will work absolutely fine..

→ Ответить