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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
| #include <bits/stdc++.h>
#define int long long
using namespace std;
class bigint
{
private:
string value;
int cmp(const bigint & other) const
{
if(value.length() != other.value.length()) return value.length() < other.value.length() ? -1 : 1;
return value.compare(other.value);
}
public:
bigint(string s = "0")
{
value = s;
}
static bool smaller(const bigint &a, const bigint &b)
{
if(a.cmp(b) > 0) return false;
return true;
}
bigint operator+(const bigint& other)
{
int carry = 0;
int i = value.length() - 1, j = other.value.length() - 1;
string result;
while(i >= 0 || j >= 0 || carry > 0)
{
int sum = carry;
if(i >= 0) sum += value[i--] - '0';
if(j >= 0) sum += other.value[j--] - '0';
result.push_back(sum % 10 + '0');
carry = sum / 10;
}
reverse(result.begin(), result.end());
result.erase(0, result.find_first_not_of('0'));
if(result.empty()) return bigint("0");
return bigint(result);
}
bigint operator-(const bigint & other)
{
int borrow = 0;
string result;
int i = value.length() - 1, j = other.value.length() - 1;
while(i >= 0 || j >= 0)
{
int diff = borrow;
if(i >= 0) diff += value[i--] - '0';
if(j >= 0) diff -= other.value[j--] - '0';
if(diff < 0)
{
diff += 10;
borrow = -1;
}
else borrow = 0;
result.push_back(diff % 10 + '0');
}
reverse(result.begin(), result.end());
result.erase(0, result.find_first_not_of('0'));
if(result.empty()) return bigint("0");
return bigint(result);
}
bigint operator*(const bigint & other)
{
string result(value.length() + other.value.length(), '0');
for(int i = value.length() - 1; i >= 0; i--)
{
int carry = 0;
for(int j = other.value.length() - 1; j >= 0; j--)
{
int sum = carry + (result[i + j + 1] - '0') + (value[i] - '0') * (other.value[j] - '0');
result[i + j + 1] = sum % 10 + '0';
carry = sum / 10;
}
result[i] += carry;
}
result.erase(0, result.find_first_not_of('0'));
if(result.empty()) return bigint("0");
return bigint(result);
}
bigint operator/(const bigint& other)
{
if(other.value == "0")
{
throw runtime_error("Division by zero");
}
if(cmp(other) < 0)
{
return bigint("0");
}
string result;
bigint temp("0");
for(auto digit: value)
{
temp = temp * bigint("10") + bigint(string(1, digit));
int count = 0;
while(temp.cmp(other) >= 0)
{
temp = temp - other;
count ++;
}
result.push_back(count + '0');
}
result.erase(0, result.find_first_not_of('0'));
if(result.empty()) return bigint("0");
return bigint(result);
}
friend ostream& operator<<(ostream& os, const bigint& num)
{
os << num.value;
return os;
}
};
bool cmp(pair<int, int> a, pair<int, int> b)
{
return a.first * a.second < b.first * b.second;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
n = n + 1;
vector<pair<int, int>> v(n);
for(int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
sort(v.begin() + 1, v.end(), cmp);
bigint ans(to_string(v[0].first)), res("0");
for(int i = 1; i < n; i++)
{
bigint tmp = ans / bigint(to_string(v[i].second));
ans = ans * bigint(to_string(v[i].first));
if(bigint::smaller(res, tmp)) res = tmp;
}
cout << res;
return 0;
}
|
