1213. Массивные числа

Число называется массивным, если его можно записать в виде aⁿ, то есть a, возведённое в степень n.

Вам даны два массивных числа a^b и c^d, каждое записано в формате “основание^показатель степени”. Ваша задача – сравнить эти два числа.

Вход. Два массивных числа в формате “основание^показатель степени” (1 ≤ основание, показатель степени ≤ 1000). Гарантируется, что эти два числа различны.

Выход. Выведите большее из двух заданных массивных чисел.

Пример входа	Пример выхода
3^100 2^150	3^100

РЕШЕНИЕ

математика

Анализ алгоритма

Логарифм – это монотонно возрастающая функция, поэтому если x < y, то log(x) < log(y).

Прологарифмируем неравенство: a^b < c^d. Возьмем, например, десятичный логарифм (или натуральный, разницы нет):

b lg a < d lg c

Следовательно, сравнение двух больших чисел сводится к сравнению двух чисел b lg a и d lg c. Значения выражений b lg a и d lg c помещаются в тип double, поэтому их можно легко сравнить.

Реализация алгоритма

Читаем входные данные, выделяя основания и показатели степеней для каждого числа.

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

Сравним значения прологарифмированных выражений b lg a и d lg c, после чего выведем ответ.

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 реализация

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);

con.close();

}

}