首页 > 代码库 > Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem F (Codeforces 831F) - 数论 - 暴力

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem F (Codeforces 831F) - 数论 - 暴力

2024-10-28 10:17:39   211人阅读

<style></style>

Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are n bamboos in a row, and the i-th from the left is ai meters high.

Vladimir has just planted n bamboos in a row, each of which has height 0 meters right now, but they grow 1 meter each day. In order to make the partition nice Vladimir can cut each bamboo once at any height (no greater that the height of the bamboo), and then the bamboo will stop growing.

Vladimir wants to check the bamboos each d days (i.e. d days after he planted, then after 2d days and so on), and cut the bamboos that reached the required height. Vladimir wants the total length of bamboo parts he will cut off to be no greater than k meters.

What is the maximum value d he can choose so that he can achieve what he wants without cutting off more than k meters of bamboo?

Input

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1011) — the number of bamboos and the maximum total length of cut parts, in meters.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the required heights of bamboos, in meters.

Output

Print a single integer — the maximum value of d such that Vladimir can reach his goal.

Examples
input
3 4
1 3 5
output
3
input
3 40
10 30 50
output
32
Note

In the first example Vladimir can check bamboos each 3 days. Then he will cut the first and the second bamboos after 3 days, and the third bamboo after 6 days. The total length of cut parts is 2 + 0 + 1 = 3 meters.

　　题目大意 求这样一个最大的d使得技术分享

　　整理一下可以得到条件是技术分享

　　有注意到技术分享的取值个数为技术分享。

　　还是说明一下，设技术分享。

　　1)当技术分享时，显然至多技术分享个取值。

　　2)当技术分享时，显然有技术分享，这个的取值个数也是技术分享的。

　　因此可以发现当d等于一个值的时候可能和另一个d值的时候是等价的。

　　所以我们把所有技术分享的取值当成一个点，安插在数轴上，然后一段一段地进行枚举。因为每一段内的d都是等价的，所以只需要用每一段的左端点计算和，然后判断技术分享是否在区间内，如果是就用它去更新答案。

Code

  1 /**  2  * Codeforces  3  * Problem#831F  4  * Accepted  5  * Time:997ms  6  * Memory:100400k  7  */  8 #include <iostream>  9 #include <cstdio> 10 #include <ctime> 11 #include <cmath> 12 #include <cctype> 13 #include <cstring> 14 #include <cstdlib> 15 #include <fstream> 16 #include <sstream> 17 #include <algorithm> 18 #include <map> 19 #include <set> 20 #include <stack> 21 #include <queue> 22 #include <vector> 23 #include <stack> 24 #ifndef WIN32 25 #define Auto "%lld" 26 #else 27 #define Auto "%I64d" 28 #endif 29 using namespace std; 30 typedef bool boolean; 31 const signed int inf = (signed)((1u << 31) - 1); 32 const signed long long llf = (signed long long)((1ull << 63) - 1); 33 const double eps = 1e-6; 34 const int binary_limit = 128; 35 #define smin(a, b) a = min(a, b) 36 #define smax(a, b) a = max(a, b) 37 #define max3(a, b, c) max(a, max(b, c)) 38 #define min3(a, b, c) min(a, min(b, c)) 39 template<typename T> 40 inline boolean readInteger(T& u){ 41     char x; 42     int aFlag = 1; 43     while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 44     if(x == -1) { 45         ungetc(x, stdin);     46         return false; 47     } 48     if(x == ‘-‘){ 49         x = getchar(); 50         aFlag = -1; 51     } 52     for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 53     ungetc(x, stdin); 54     u *= aFlag; 55     return true; 56 } 57  58 #define LL long long 59  60 int n; 61 LL C; 62 int* a; 63 vector<LL> seg; 64  65 template<typename T> 66 T ceil(T a, T b) { 67     return (a + b - 1) / b; 68 } 69  70 inline void init() { 71     readInteger(n); 72     readInteger(C); 73     seg.push_back(1); 74     a = new int[(n + 1)]; 75     for(int i = 1, x; i <= n; i++) { 76         readInteger(a[i]); 77         for(int j = 1; j * j <= a[i]; j++) 78             seg.push_back(j), seg.push_back(ceil(a[i], j)); 79         C += a[i]; 80     } 81     seg.push_back(llf); 82 } 83  84 LL res = 1; 85 inline void solve() { 86     sort(seg.begin(), seg.end()); 87     int m = unique(seg.begin(), seg.end()) - seg.begin() - 1; 88     for(int i = 0; i < m; i++) { 89         LL l = seg[i], r = seg[i + 1], temp = 0; 90         for(int i = 1; i <= n; i++) 91             temp += ceil((LL)a[i], l); 92         LL d = C / temp; 93         if(d >= l && d < r && d > res) 94             res = d; 95     } 96     printf(Auto"\n", res); 97 } 98  99 int main() {100     init();101     solve();102     return 0;103 }

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem F (Codeforces 831F) - 数论 - 暴力


联系
我们