Türkçe

Problemde yakıtı hesaplarken, yakıtın miktarını sayı olarak düşünüp her bit'ini 0 ya da 1 yapmak için ayrı ayrı düşünmeliyiz. Bu durumda yakıt miktarının büyük olması için olabilecek en büyük bitlerin 1 olması gerekiyor.

Başlangıçta süt miktarını olabildiğince az yapmak için yakıt miktarının kaç olması gerektiğinizi hesaplayabiliriz. Yakıt miktarındaki her bit için daha az süte karşılık olan biti seçerek yakıt miktarının karşılık geleceği süt miktarını minizimize edebiliriz. Yakıt miktarındaki \(x\)'inci bitin 0 ya da 1 olduğunu seçmek için tüm \(A_i\)'ler için \(x\)'inci bitlerindeki 1 ve 0 sayılarını saymalıyız. Eğer 1 miktarı daha fazla ise bu durumda \(x\)'inci biti 1 seçmeliyiz ki süt miktarı daha az olsun. Eğer 0 miktarı 1 miktarından daha fazlaysa da bu durumda 0 seçmeliyiz. Eğer iki sayı birbirine eşitse de bu durumda hangi sayı seçildiği fark etmediği için yakıt miktarının fazla olması için 1 seçmeliyiz.

Bu şekilde bulduğumuz yakıt miktarı ile en az kullanabileceğimiz süt miktarını bulduk. Eğer bu süt miktarı \(\mathbf{M}\)'e küçük eşit değilse, herhangi bir çözüm yok. Bu durumda "-1" yazdırabiliriz.

Son olarak da, en büyük bitlerden başlayarak, tüm bitler için "eğer bu bitin karşılık geldiği sayıyı bu sayıya eklersek, sonuçtaki süt miktarı \(\mathbf{M}\)'i geçer mi?" diye kontrol etmeliyiz. En az olabilecek süt miktarı için yaptığımız gibi yine her bit için eğer o bit 0 ise 1 yapmayı deneyeceğiz. (1 olan bitleri olduğu gibi bırakabiliriz, çünkü değiştirmemiz sadece yakıt miktarını azaltır) 0 olan bitler eğer 1 olduğunda da süt miktarı \(\mathbf{M}\)'e küçük eşit oluyorsa, sayımızdaki bu biti 0'dan 1'e değiştirmeliyiz. Bitleri deneme sıramız büyükten küçüğe olduğu için bu şekilde koşulları sağlayabilecek en büyük yakıt miktarını buluruz.

English

While calculating the fuel in the problem, we need to think of the amount of fuel as a number and consider its each bit individually, whether it should be a 0 or a 1. In this case, the most significant bits need to be 1 in order for the fuel amount to be maximal.

In the beginning, we can calculate the amount of fuel needed to make the amount of milk as little as possible. For each bit in the fuel, we can minimize the amount of milk by choosing the option (1 or 0) that corresponds to the less amount of milk. Namely, to choose whether the \(x\)th bit in the fuel is 1 or 0, we need to count the 1s and 0s of \(x\)th bits for every \(A_i\). If there are more 1s, then we will choose the \(x\)th bit to be 1 and we will choose 0 otherwise. If they happen to be equal, our choice does not affect the milk amount. In such a case we will choose 1 to make the fuel amount greater.

Doing this, we have found the minimum amount of milk. If it is greater than \(\mathbf{M}\), there are no possible solutions. We can print "-1".

Lastly, we need to look at each bit starting from the most significant and check "if I add the number corresponding to this bit, will the result exceed \(\mathbf{M}\)?". We will try to change the 0s to 1s. (We can leave the 1s because changing them would result in a lesser amount of fuel.) If the amount of milk is still less than or equal to \(\mathbf{M}\), we will change the 0 to 1 so that the result becomes greater. Since we have started from the most significant bit, we will find the exact maximum point that the amount of milk does not exceed \(\mathbf{M}\).

Örnek Çözüm / Sample Solution

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second

const int md = (int) 1e9 + 7;
const int siz = 300005;

ll arr[siz];
int orr[siz][60];
ll a2[60];
ll n, m, k, l, t, tt, res;
unsigned ll sum[60], sum2[60], don[60];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    for(int i=0;i<=51;i++){
        a2[i]=pow(2,i);
    }

    cin>>n>>m;
    res=0;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        for(int j=0;j<=51;j++){
            ll b=a2[j]^arr[i];
            orr[i][j]=0;
            if(b<=arr[i]) orr[i][j]=1;
        }
    }


    for(int i=51;i>=0;i--){
        don[i]=1;
        for(int j=0;j<n;j++){
            if(!orr[j][i]) sum[i]+=a2[i];
            else sum2[i]+=a2[i];
        }
        if(sum[i]<=sum2[i]){
            don[i]=0;
            res+=a2[i];
            m-=sum[i];
        }
        else m-=sum2[i];
        // cout<<m<<' '<<sum[i]<<' '<<sum2[i]<<endl;
        if(m<0) break;
    }

    for(int i=51;i>=0;i--){
        if(m<0) break;
        if(don[i] && (sum[i]-sum2[i])<=m){
            res+=a2[i];
            m-=(sum[i]-sum2[i]);
        }
    }
    if(m<0) res=-1;

    cout<<res<<endl;
}