This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
$x$と$y$の大小関係を答える．しかし階乗の階乗の…とまであるので愚直に計算すると大変なことになる．しかし階乗の個数が大きい方から階乗の計算をしていき，個数が少ない方の値を超えたら既にその値よりも下回ることは無くなるので，実際はlong longに収まる中で大小関係を求めることができる．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
class ExtraordinarilyLarge {
public :
string compare ( string x , string y ) {
ll a = 0 , b = 0 ;
int ac = 0 , bc = 0 ;
stringstream ss ;
rep ( i , x . size ()) {
if ( x [ i ] == '!' ) {
ac ++ ;
continue ;
}
ss << x [ i ];
}
ss >> a ;
if ( a == 0 && ac > 0 ) {
a = 1 ;
ac -- ;
}
stringstream ss2 ;
rep ( i , y . size ()) {
if ( y [ i ] == '!' ) {
bc ++ ;
continue ;
}
ss2 << y [ i ];
}
ss2 >> b ;
if ( b == 0 && bc > 0 ) {
b = 1 ;
bc -- ;
}
vector < string > ans ( 3 );
ans [ 0 ] = "x<y" ; ans [ 1 ] = "x>y" ; ans [ 2 ] = "x=y" ;
if ( ac > bc ) {
swap ( ac , bc );
swap ( a , b );
swap ( ans [ 0 ], ans [ 1 ]);
}
while ( ac < bc ) {
bc -- ;
ll nb = 1 ;
for ( int i = b ; i >= 1 ; i -- ) {
nb *= i ;
if ( nb > a ) break ;
}
b = nb ;
if ( b > a ) break ;
}
if ( a == b ) {
return ans [ 2 ];
} else if ( a < b ) {
return ans [ 0 ];
} else {
return ans [ 1 ];
}
}
};