Codeforces Round #218 (Div. 2)（好）

Two little greedy bears have found two pieces of cheese in the forest of weighta andb grams, correspondingly. The bears are so greedy that they are ready to fight for the larger piece. That's where the fox comes in and starts the dialog: "Little bears, wait a little, I want to make your pieces equal" "Come off it fox, how are you going to do that?", the curious bears asked. "It's easy", said the fox. "If the mass of a certain piece is divisible by two, then I can eat exactly a half of the piece. If the mass of a certain piece is divisible by three, then I can eat exactly two-thirds, and if the mass is divisible by five, then I can eat four-fifths. I'll eat a little here and there and make the pieces equal".

The little bears realize that the fox's proposal contains a catch. But at the same time they realize that they can not make the two pieces equal themselves. So they agreed to her proposal, but on one condition: the fox should make the pieces equal as quickly as possible. Find the minimum number of operations the fox needs to make pieces equal.

Input

The first line contains two space-separated integers a andb (1 ≤ a, b ≤ 10⁹).

Output

If the fox is lying to the little bears and it is impossible to make the pieces equal, print-1. Otherwise, print the required minimum number of operations. If the pieces of the cheese are initially equal, the required number is 0.

Sample test(s)

Input

15 20

Output

Input

14 8

Output

-1

Input

6 6

Output

0
 思路：将每个数都除以2,3,5直到不能再除，如果最后数不一样就返回-1，一样就根据除的次数返回，也可以先求最大公约数，然后看剩下的是不是能被2,3,5除尽。 下面是代码：

#include<iostream>
#include<cstring>
using namespace std;
int ans;
int x[5],y[5];
int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
bool cnt(int *num,int a)
{
    while(a%5==0)
        a/=5,num[2]++;
    while(a%3==0)
        a/=3,num[1]++;
    while(a%2==0)
        a/=2,num[0]++;
    if(a!=1)
        return false;
    return true;
}
int main()
{
    int a,b;
    cin>>a>>b;
    if(a==b)
    {
        cout<<0<<endl;
        return 0;
    }
    int g=gcd(a,b);
    a/=g;
    b/=g;
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    bool flag=true;
    int ans=0;
    if(cnt(x,a))
        ans+=x[0]+x[1]+x[2];
    else flag=false;
    if(cnt(y,b))
        ans+=y[0]+y[1]+y[2];
    else flag=false;
    if(flag)
        cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}

C. Hamburgers
思路：二分答案，INF开得不够大，wa了一次。
下面是代码：

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
const long long INF=2000000000000;
long long bnum,snum,cnum;
long long nb,ns,nc,pb,ps,pc;
long long r;
bool can(long long mid)
{
    long long sum=0;
    sum+=((bnum*mid>nb)?((bnum*mid-nb)*pb):0);
    sum+=((snum*mid>ns)?((snum*mid-ns)*ps):0);
    sum+=((cnum*mid>nc)?((cnum*mid-nc)*pc):0);
    return sum<=r;
}
int main()
{
    string a;
    cin>>a;
    cin>>nb>>ns>>nc>>pb>>ps>>pc;
    cin>>r;
    bnum=0,snum=0,cnum=0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]=='B') bnum++;
        else if(a[i]=='S') snum++;
        else cnum++;
    }
    long long l=0,r=INF,mid;
    long long ans=-1;
    while(l<r)
    {
        mid=(l+r)/2;
        if(can(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else r=mid;
    }
    cout<<ans<<endl;
    return 0;
}

There is a system of n vessels arranged one above the other as shown in the figure below. Assume that the vessels are numbered from 1 to n, in the order from the highest to the lowest, the volume of the i-th vessel is a_i liters.

$Codeforces Round #218 (Div. 2)（好）$

Initially, all the vessels are empty. In some vessels water is poured. All the water that overflows from the i-th vessel goes to the (i + 1)-th one. The liquid that overflows from the n-th vessel spills on the floor.

Your task is to simulate pouring water into the vessels. To do this, you will need to handle two types of queries:

Add x_i liters of water to the p_i-th vessel;
Print the number of liters of water in the k_i-th vessel.

When you reply to the second request you can assume that all the water poured up to this point, has already overflown between the vessels.

Input

The first line contains integer n — the number of vessels (1 ≤ n ≤ 2·10⁵). The second line contains n integers a₁, a₂, ..., a_n — the vessels' capacities (1 ≤ a_i ≤ 10⁹). The vessels' capacities do not necessarily increase from the top vessels to the bottom ones (see the second sample). The third line contains integer m — the number of queries (1 ≤ m ≤ 2·10⁵). Each of the next m lines contains the description of one query. The query of the first type is represented as "1 p_i x_i", the query of the second type is represented as "2 k_i" (1 ≤ p_i ≤ n, 1 ≤ x_i ≤ 10⁹, 1 ≤ k_i ≤ n).

Output

For each query, print on a single line the number of liters of water in the corresponding vessel.

Sample test(s)

Input

Output

4
5
8

Input

Output

7
10
5

思路：开一个c数组保存离当位置最近的，而且没有满的位置。
下面是代码：

#include <algorithm>
#include <cstdio>
using namespace std;
int a[202020], b[202020], c[202020];
int find(const int& x)
{
    if (a[x] == b[x])
    {
        c[x] = find(c[x]);
        return c[x];
    }
    return x;
}

int main()
{
    int n, m;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", a + i);
        c[i] = i + 1;
    }
    a[n + 1] = 1;
    scanf("%d", &m);
    int x, y, z;
    while (m--)
    {
        scanf("%d %d", &x, &y);
        if (x == 1)
        {
            scanf("%d", &z);
            while (z && y <= n)
            {
                int w =min(z, a[y] - b[y]);
                z -= w;
                b[y] += w;
                y = find(y);
            }
        }
        else
            printf("%d\n", b[y]);
    }
    return 0;
}

秒客网

Codeforces Round #218 (Div. 2)（好）

相关文章