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

How to deal with problems that require high precision ?
Автор im__skp, история, 4 года назад, По-английски

I was doing a problem in which you are given a number P and a number N. You have to find a number K such that K^N is equal to P.

CONSTRAINTS ARE : 1 ≤ n ≤ 200, 1 ≤ p < 10^101

PROBLEM LINK

The python code that got AC : 

while True:
    try:
        n = int(input())
        p = int(input())
        print(round(p**(1/n)))

    except:
        break

Why do I have to use the round function why can't I use ceil or floor?

When should I use round?

These kinds of questions cost me a lot of WAs. Can someone tell me how to deal with these kinds of questions?

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

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

My guess would be that round is more accurate than ceil or floor since round rounds to the nearest integer. However, to be safe, I wouldn't use round or any floating-points here at all. Instead, you should do binary search on k in order to find the exact integer answer. This requires using big integers, but big integers are built into Python anyway and it does not give you the precision problems that floating-points will give you.

import sys

# I/O boilerplate:
lines = (line for line in sys.stdin.read().split("\n"))
def next_int():
    next_line = next(lines)
    # Exit once we hit empty line
    if next_line == "":
        sys.exit(0)
    return int(next_line)

while True:
    n = next_int()
    p = next_int()
    
    min_possible_value_of_k = 1
    max_possible_value_of_k = 10**9
    # This is the part where we do binary search on k:
    while min_possible_value_of_k <= max_possible_value_of_k:
        mid = (min_possible_value_of_k + max_possible_value_of_k) // 2
        mid_to_nth_power = mid**n
        
        if mid_to_nth_power == p:
            print(mid)
            break
        elif mid_to_nth_power < p:
            min_possible_value_of_k = mid + 1
        else:
            max_possible_value_of_k = mid - 1
→ Ответить