1213. Massive Numbers

A number is called massive if it can be written in the form aⁿ, that is, a raised to the power of n.

You are given two massive numbers a^b and c^d, each written in the format “base^exponent”. Your task is to compare these two numbers.

Input. Two massive numbers in the format “<base>^<exponent>” (1 ≤ base, exponent ≤ 1000). It is guaranteed that the two numbers are different.

Output. Print the greater of the two given massive numbers.

Sample input	Sample output
3^100 2^150	3^100

SOLUTION

mathematics

Algorithm analysis

A logarithm is a monotonically increasing function, so if x < y, then log(x) < log(y).

Let’s take the logarithm of the inequality: a^b < c^d. For example, using the common logarithm (or natural logarithm, it doesn’t matter):

b lg a < d lg c

Therefore, comparing two large numbers reduces to comparing the two values b lg a and d lg c. The values of b lg a and d lg c fit into a double type, so they can be easily compared.

Algorithm implementation

Read the input data. Extract the bases and exponents for each number.

scanf("%d^%d %d^%d",&a,&b,&c,&d);

Compare the values of the logarithmized expressions b lg a and d lg c. Then print the answer.

if (b * log(1.0 * a) < d * log(1.0 * c)) printf("%d^%d\n",c,d);

else printf("%d^%d\n",a,b);

Java implementation

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

String s = con.nextLine();

StringTokenizer st = new StringTokenizer(s," ^");

int a = Integer.valueOf(st.nextToken()),

b = Integer.valueOf(st.nextToken()),

c = Integer.valueOf(st.nextToken()),

d = Integer.valueOf(st.nextToken());

if(b * Math.log(a) > d * Math.log(c))

System.out.println(a + "^" + b);

else

System.out.println(c + "^" + d);

}

}