Mercari OA

// lcs

#include<bits/stdc++.h>
using namespace std;

int longestCommonSubsequence(string& str1, string& str2, int maxCost) {
    int len1 = str1.size();
    int len2 = str2.size();
    vector<vector<vector<int>>> dp(len1 + 1, vector<vector<int>>(len2 + 1, vector<int>(maxCost + 1, 0)));
    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            if (str1[i - 1] == str2[j - 1])
                for(int cost=maxCost; cost >=0; cost-- ){
                    dp[i][j][cost] = dp[i - 1][j - 1][cost] + 1;
                }
            else{
                for(int cost=maxCost; cost>=0; cost-- ){
                    dp[i][j][cost] = max(dp[i - 1][j][cost], dp[i][j - 1][cost]);
                    int diff = abs((int)str1[i-1] - (int)str2[j-1]);
                    diff = min(diff, 26 - diff);
                    if(cost+diff<=maxCost){
                        dp[i][j][cost] = max(dp[i][j][cost], dp[i-1][j-1][cost+diff] + 1);
                    }
                }
            }
        }
    }
    return *max_element(dp[len1][len2].begin(), dp[len1][len2].end());
}

int main(){
    int k;
    string s1, s2;
    cin>>s1;
    cin>>s2;
    cin>>k;
    cout<<longestCommonSubsequence(s1, s2, k);
    return 0;
}

// process tree:
#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    int p = 1, child = 2;
    while(child<n) {
        p++;
        child+=p;
    }
    return p;
}
int main(){
    int n; cin>>n;
    cout<<solve(n)<<endl;
    return 0;
}

// optimal subarray:

#include <bits/stdc++.h>
using namespace std;

long long int find(int n, vector<int> a){
    int count = 0;
    vector<int> v;
    for(int i = 2; i<=200; i++) {
        bool f = false;
        for(int j = 2; j*j<=i; j++) {
            if(i%j==0) {
                f=true;
                break;
            }
        }
        if(f)continue;
        count++;
        v.push_back(i);
    }


    int ans = 0;
    bool f = true;
    map<long long int , int> m;
    string s;
    for(int i = 0; i<count; i++)s.push_back('0');
    m[0]++;
    for(int i=0; i < n; i++){
        for(int j = 0; j<count; j++) {
            int cnt = 0;
            while(a[i]%v[j]==0) {
                cnt++;
                a[i]/=v[j];
            }
            if(s[j]=='1')cnt++;
            s[j] = cnt%2+'0';
        }
        long long int temp = 0;
        for(auto &x : s) {
            temp*=2;
            if(x=='1')temp++;
        }
        ans+=m[temp];
        m[temp]++;
    }
    return ans;
}
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(auto &x : a)cin>>x;
    cout<<find(n, a);
    return 0;
}

// #include <bits/stdc++.h>
// using namespace std;

// long long int countGoodSubarrays(int n, vector<int>& arr) {
//     vector<int> primes;
//     for (int i = 2; i <= 200; i++) {
//         bool isPrime = true;
//         for (int j = 2; j * j <= i; j++) {
//             if (i % j == 0) {
//                 isPrime = false;
//                 break;
//             }
//         }
//         if (isPrime) {
//             primes.push_back(i);
//         }
//     }

//     int primeCount = primes.size();
//     map<long long int, int> bitmaskFrequency;
//     string bitmask(primeCount, '0');
//     bitmaskFrequency[0]++;

//     long long int goodSubarrays = 0;

//     for (int i = 0; i < n; i++) {
//         for (int j = 0; j < primeCount; j++) {
//             int exponent = 0;
//             while (arr[i] % primes[j] == 0) {
//                 exponent++;
//                 arr[i] /= primes[j];
//             }

//             if (bitmask[j] == '1') exponent++;
//             bitmask[j] = (exponent % 2) + '0';
//         }

//         long long int bitmaskValue = 0;
//         for (auto& bit : bitmask) {
//             bitmaskValue *= 2;
//             if (bit == '1') bitmaskValue++;
//         }

//         goodSubarrays += bitmaskFrequency[bitmaskValue];
//         bitmaskFrequency[bitmaskValue]++;
//     }

//     return goodSubarrays;
// }

// int main() {
//     int n;
//     cin >> n;
//     vector<int> arr(n);
//     for (auto& x : arr) cin >> x;

//     cout << countGoodSubarrays(n, arr);
//     return 0;
// }


// ttl cache:
#include <bits/stdc++.h>
using namespace std;

vector<int> processEventIntervals(vector<vector<int>> &data, vector<int> &queries){
    map<int, int> m;
    for(auto &x : data){
        m[x[0]]++;
        m[x[1]+x[0]+1]--;
    }
    int curr=0;
    vector<int> keys;
    for(auto &x : m){
        keys.push_back(x.first);
        curr+=x.second;
        m[x.first]=curr;
    }
    vector<int> ans;
    for(auto &x : queries){
        int lo=0 , hi=keys.size()-1 , mid;
        while(lo<=hi)
        {
            mid=(lo+hi)/2;
            if(keys[mid]<=x)
            {
                lo=mid+1;
            }
            else
            {
                hi=mid-1;
            }
        }
        if(hi==-1){
            ans.push_back(0);
        }else{
            ans.push_back(m[keys[hi]]);
        }
    }

    // cout<<m[keys.back()-2];
    return ans;
}
int main(){
    int n;
    cin>>n;
    vector<vector<int>> data(n, vector<int>(2));
    for(auto &x : data){
        cin>>x[0]>>x[1];
    }
    int m;
    cin>>m;
    vector<int> q(m);
    for(auto &x : q)cin>>x;
    auto ans =processEventIntervals(data, q);
    for(auto &x : ans)cout<<x<<" ";
    return 0;
}


// Women in tech
// C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

// Function to count minimum number
// of bits required to be flipped
// to make all array elements equal
int makeEqual(int* arr, int n)
{
    // Stores the count of unset bits
    int fre0[33] = { 0 };

    // Stores the count of set bits
    int fre1[33] = { 0 };

    // Traverse the array
    for (int i = 0; i < n; i++) {

        int x = arr[i];

        // Traverse the bit of arr[i]
        for (int j = 0; j < 33; j++) {

            // If current bit is set
            if (x & 1) {

                // Increment fre1[j]
                fre1[j] += 1;
            }

            // Otherwise
            else {

                // Increment fre0[j]
                fre0[j] += 1;
            }

            // Right shift x by 1
            x = x >> 1;
        }
    }

    // Stores the count of total moves
    int ans = 0;

    // Traverse the range [0, 32]
    for (int i = 0; i < 33; i++) {

        // Update the value of ans
        ans += min(fre0[i], fre1[i]);
    }

    // Return the minimum number of
    // flips required
    return ans;
}

// Driver Code
int main()
{
    int arr[] = { 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << makeEqual(arr, N);

    return 0;
}