DFS优化，数学题，时间复杂度计算题

In one of the games Arkady is fond of the game process happens on a rectangular field. In the game process Arkady can buy extensions for his field, each extension enlarges one of the field sizes in a particular number of times. Formally, there are n extensions, the i-th of them multiplies the width or the length (by Arkady's choice) by ai. Each extension can't be used more than once, the extensions can be used in any order.

Now Arkady's field has size h × w. He wants to enlarge it so that it is possible to place a rectangle of size a × b on it (along the width or along the length, with sides parallel to the field sides). Find the minimum number of extensions needed to reach Arkady's goal.

Input

The first line contains five integers a, b, h, w and n (1 ≤ a, b, h, w, n ≤ 100 000) — the sizes of the rectangle needed to be placed, the initial sizes of the field and the number of available extensions.

The second line contains n integers a1, a2, ..., an (2 ≤ ai ≤ 100 000), where ai equals the integer a side multiplies by when the i-th extension is applied.

Output

Print the minimum number of extensions needed to reach Arkady's goal. If it is not possible to place the rectangle on the field with all extensions, print -1. If the rectangle can be placed on the initial field, print 0.

Examplesinput

3 3 2 4 4
2 5 4 10

output

input

3 3 3 3 5
2 3 5 4 2

output

input

5 5 1 2 3
2 2 3

output

-1

input

3 4 1 1 3
2 3 2

output

Note

In the first example it is enough to use any of the extensions available. For example, we can enlarge h in 5 times using the second extension. Then h becomes equal 10 and it is now possible to place the rectangle on the field.

个人感觉这道题相当好，我自己做的时候仅仅只是排了个序，然后第四个测试点就过不了，瞬间感觉自己很操蛋。这道题的a,b的范围是小于1000000的，也就是说当Ai>=2时只需要log2（1000000）次运算就可以，但这样的话时间复杂度太高！看别人题解说到最后只剩2的时候就特判一下，这句话把我搞懵逼了，为什么2的时候就得特判？然后才发现并不是2这个数的原因，而是范围最小就是2，所以这样的话log3（1000000）时间复杂度就瞬间降低，解决这道题。

再总结这道题，其实感觉对于我这种水平的人来说就得多做这种题，锻炼思维，锻炼计算时间复杂度的能力。

#include<bits/stdc++.h>
using namespace std;
int a, b, h, w, n, A[100010];
int dfs(long long h, long long w, int idx)
{
    if(h>=a&&w>=b)    return n-idx;
    if(idx==0)  return -1;
    if(A[idx] == 2)
    {
        if(h<a) return dfs(h*2, w, idx-1);
        return dfs(h, w*2, idx-1);
    }
    else
    {
        int ansh = -1, answ = -1;
        if(h<a)
            ansh = dfs(h*A[idx], w, idx-1);
        if(w<b)
            answ = dfs(h, w*A[idx], idx-1);
        if(ansh==-1 || answ==-1)    return max(ansh, answ);
        return min(ansh, answ);
    }
}
int main()
{
    scanf("%d %d %d %d %d",&a,&b,&h,&w,&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&A[i]);
    sort(A+1, A+n+1);
    int ansl, ansr;
    ansl = dfs(h, w, n);
    swap(a, b);
    ansr = dfs(h, w, n);
    if(ansl==-1 || ansr==-1)    printf("%d\n", max(ansl, ansr));
    else    printf("%d\n", min(ansl, ansr));
}

秒客网

DFS优化，数学题，时间复杂度计算题

相关文章