𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

# include <bits/stdc++.h>
using namespace std;
#define ll long long
signed main(){
    
    string s; cin>>s;
    vector<ll>freq(26);
    for(auto it:s) freq[it-'a']++;
    bool f=0;
    for(ll i=0;i<26;i++)
    {
      if(freq[i]!=0) {cout<<char(i+'a'); f=1;}
      if(f) break;
    }
    if(!f) cout<<-1<<endl;
    return 0;
}

873 views07:50

Photo

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

int solve(int n, vector<int>& front, vector<int>& back, int frontend, int backend) {
    vector<vector<int>> dp(n + 1, vector<int>(frontend + 1, INT_MAX));
    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= frontend; j++) {
            if (dp[i][j] == INT_MAX) continue;
            if (j < frontend) {
                dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + front[i]);
            }
            int b = i - j;
            if (b < backend) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + back[i]);
            }
        }
    }

    return dp[n][frontend];
}

int32_t main() {
    int frontend, backend;
    cin >> frontend >> backend;
    int n = frontend + backend;
    vector<int> front(n), back(n);
    
    for (int i = 0; i < n; i++) {
        cin >> front[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> back[i];
    }

    int result = solve(n, front, back, frontend, backend);
    cout << result << endl;

    return 0;
}

Hiring Drive ✅

659 views17:25

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

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

ll ss(ll A, ll B) {
    ll rounds = 0;
        while (A != B) {
        if (A > B) {
            A -= B;
        } else {
            B -= A;
        }
        rounds++; 
    }
    
    return rounds;
}

int main() {
    ll A, B;
    cin >> A >> B;
    cout << ss(A, B) << endl;
    return 0;
}

Rivals ✅

👍1

587 views17:28

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

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

int solve(int n, int m, int x, vector<int>& a) {

    int rem = m % x;

    if (rem == 0) {
        return m % MOD;
    }

    int minAdd = -1;
    for (int i = 0; i < n; i++) {
        int add = a[i];
        if ((m + add) % x == 0) {
            if (minAdd == -1 || add < minAdd) {
                minAdd = add;
            }
        }
    }

    if (minAdd == -1) {
        return -1;
    }

    return (m + minAdd) % MOD;
}

int main() {
    int t; 
    cin >> t;
    
    while (t--) {
        int n, m, x;
        cin >> n >> m >> x;
        
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        int res =solve(n, m, x, a);

        cout << res << endl;
    }

    return 0;
}

Greedy power ✅

639 views17:30

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

Photo

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
int32_t main(){
    ll n,m;
    cin>>n>>m;
    vector<ll> a(n);
    vector<ll> b(m);
    vector<ll> pre(n+1);
    for(int i=0;i<n;i++){
        cin>>a[i];
        pre[i+1]=pre[i]+a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    ll k=(1LL<<m)-1;
    ll dp[n+1][k+1];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
            for(int l=0;l<m;l++){
                if((1LL<<l)&j){
                
                }
                else{
                    ll next=(1LL<<l)|j,idx=i+b[l]-1;
                    if(idx>=0 and idx<=n)
                    dp[idx][next]=max(dp[idx][next],dp[i-1][j]+pre[idx]-pre[i-1]);
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<=n;i++){
        ans=max(dp[i][k],ans);
    }
    cout<<ans<<endl;
    return 0;
}

Seat Booking✅

👍1

775 views17:35

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

Photo

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

vector<vector<int>> solve(vector<int> &v){
    int n=v.size();
    vector<bool> found(n+1,false);
    int curr=1;
    vector<vector<int>> ans;
    for(auto x:v){
        found[x]=true;
        vector<int> temp;
        if(found[curr]){
            while(curr<=n && found[curr] ){
                temp.push_back(curr);
                curr++;
            }
        }
        else{
            temp.push_back(-1);
        }
        ans.push_back(temp);
    }
    return ans;

}

int32_t main(){
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
       cin>>v[i];
    }
    vector<vector<int>> ans=solve(v);
    for(int i=0;i<ans.size();i++){
        for(int j=0;j<ans[i].size();j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
}

Amazon ✅

1.05K views15:32

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> msk(1024,-1);
void digits(ll num1) {
    string str1 = to_string(num1);
    set<ll>s;
    for (char digit : str1) {
        ll d=digit-'0';
        s.insert(d);
    }
    ll val=0;
    for(auto it:s) val+=(1<<it);
    msk[val]=max(msk[val],num1);
}

ll solution(vector<ll>& A) {
    for(auto &it:msk) it=-1; 
    ll ans=-1;
    for(auto it:A) digits(it);
    for(ll i=1;i<1024;i++){
        if(msk[i]==-1) continue;
        for(ll j=i+1;j<1024;j++){
            if(msk[j]==-1) continue;
            ll fl=0;
            for(ll k=0;k<10;k++){
                if((1<<k)&i){
                    if((1<<k)&j){
                        fl=1;
                        continue;
                    }
                }
            }
            if(fl) continue;
            ans=max(ans,msk[i]+msk[j]);
        }
    }
    return ans;
}

Microsoft ✅

1.01K views11:28

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

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

int32_t main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    multiset<pair<int, int>> s;
    for (int i = 0; i < n; i++) {
        s.insert({v[i], i});
    }

    int ans = 0;
    vector<bool> vis(n, false);

    while (!s.empty()) {
        auto [x, i] = *prev(s.end());
        s.erase(prev(s.end()));
        ans += x;

        vis[i] = true;

        int left = (i - 1 + n) % n;
        int right = (i + 1) % n;

        while (vis[right]) {
            right = (right + 1) % n;
        }
        vis[right] = true;
        s.erase({v[right], right});

        while (vis[left]) {
            left = (left - 1 + n) % n;
        }
        vis[left] = true;
        s.erase({v[left], left});
    }

    cout << ans << endl;
}

Kickdrum ✅

743 views17:48

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

#include <bits/stdc++.h>
#define ll long long
using namespace std;
string mergePalindrome(string&a,string&b)
{
    ll n=a.length();
    ll m=b.length();
    unordered_map<char,ll> m1,m2;
    for(char it:a) m1[it]++;
    for(char it:b) m2[it]++;
    string mid="",ans="";
    for (char i='a';i<='z';i++)
    {
        if(m1[i]%2 and m2[i]%2 and mid.length()<=1) mid=string(2,i);
        if((m1[i]%2 or m2[i]%2) and mid.length()==0) mid=i;
        ans+=string((m1[i]/2+m2[i]/2),i);
    }
    string tt=ans;
    if (mid.length()==2)
    {
        tt+=mid[0];
        ans+=mid[0];
        sort(begin(ans),end(ans));
        tt=ans+string(rbegin(ans),rend(ans));
    }
    else tt+=mid+string(rbegin(ans),rend(ans));
    return tt;
}
signed main()
{
        string s,t; cin>>s>>t;
        cout<<solve(s,t);
    return 0;
}

Merging palindromes ✅

👍1

841 views15:30

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

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

#define loop(i, a, n) for (lli i = (a); i < (n); ++i)
#define loopD(i, a, n) for (lli i = (a); i >= (n); --i)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define sz(a) ((lli)a.size())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define endl '\n'
#define fastio std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define pb push_back
#define pp pop_back()
#define fi first
#define si second
#define v(a) vector<int>(a)
#define vv(a) vector<vector<int>>(a)
#define present(c, x) ((c).find(x) != (c).end())
#define set_bits __builtin_popcountll
#define MOD 1000000007
#define int long long

typedef long long lli;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<lli, lli> pll;
typedef pair<int, int> pii;
typedef unordered_map<int, int> umpi;
typedef map<int, int> mpi;
typedef vector<pii> vp;
typedef vector<lli> vll;
typedef vector<vll> vvll;

struct Line {
    int x1, y1, x2, y2;
    bool vertical() const { return x1 == x2; }
    bool horizontal() const { return y1 == y2; }
    bool diagonal() const { return abs(x2 - x1) == abs(y2 - y1); }
};

int N, K;
vector<Line> lines;
map<pair<int, int>, vector<int>> ptsMap;

void add(const Line& line, int idx) {
    int x1 = line.x1, y1 = line.y1;
    int x2 = line.x2, y2 = line.y2;

    if (line.vertical()) {
        int yStart = min(y1, y2);
        int yEnd = max(y1, y2);
        for(int y = yStart; y <= yEnd; y++) {
            ptsMap[{x1, y}].push_back(idx);
        }
    }
    else if (line.horizontal()) {
        int xStart = min(x1, x2);
        int xEnd = max(x1, x2);
        for(int x = xStart; x <= xEnd; x++) {
            ptsMap[{x, y1}].push_back(idx);
        }
    }
    else if (line.diagonal()) {
        int steps = abs(x2 - x1);
        int dx = (x2 - x1) / steps;
        int dy = (y2 - y1) / steps;
        for(int i = 0; i <= steps; i++) {
            int x = x1 + i * dx;
            int y = y1 + i * dy;
            ptsMap[{x, y}].push_back(idx);
        }
    }
}

int ff(int x1, int y1, int x2, int y2) {
    if(x1 == x2) return abs(y1 - y2);
    if(y1 == y2) return abs(x1 - x2);
    if(abs(x1 - x2) == abs(y1 - y2)) return abs(x1 - x2);
    return 0;
}

int solve(const pair<int, int>& pt, const vector<int>& lst) {
    vector<int> d;
    for(auto lIdx : lst) {
        const Line& ln = lines[lIdx];
        bool oneSided = (pt.first == ln.x1 && pt.second == ln.y1) ||
                        (pt.first == ln.x2 && pt.second == ln.y2);
        if(oneSided) {
            int ex = (pt.first == ln.x1 && pt.second == ln.y1) ? ln.x2 : ln.x1;
            int ey = (pt.first == ln.x1 && pt.second == ln.y1) ? ln.y2 : ln.y1;
            d.push_back(ff(pt.first, pt.second, ex, ey));
        }
        else {
            d.push_back(ff(pt.first, pt.second, ln.x1, ln.y1));
            d.push_back(ff(pt.first, pt.second, ln.x2, ln.y2));
        }
    }
    return d.empty() ? 0 : *min_element(d.begin(), d.end());
}

void solve() {
    cin >> N;
    lines.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> lines[i].x1 >> lines[i].y1 >> lines[i].x2 >> lines[i].y2;
        add(lines[i], i);
    }
    cin >> K;

    int total = 0;
    for(auto &[pt, lst] : ptsMap) {
        if(sz(lst) == K) {
            total += solve(pt, lst);
        }
    }
    cout << total << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    solve();
    return 0;
}

Magic Stars ✅
TCS Codevita
Source : ishaan

👍2

888 viewsedited 15:49

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

Photo

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

#define loop(i, a, n) for (lli i = (a); i < (n); ++i)
#define loopD(i, a, n) for (lli i = (a); i >= (n); --i)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define sz(a) ((int)a.size())
#define YES cout << "YES";
#define NO cout << "NO";
#define endl '\n'
#define fastio std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define pb push_back
#define pp pop_back()
#define fi first
#define si second
#define v(a) vector<int>(a)
#define vv(a) vector<vector<int>>(a)
#define present(c, x) ((c).find(x) != (c).end())
#define set_bits __builtin_popcountll
#define MOD 1000000007
#define int long long

typedef long long lli;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<lli, lli> pll;
typedef pair<int, int> pii;
typedef unordered_map<int, int> umpi;
typedef map<int, int> mpi;
typedef vector<pii> vp;
typedef vector<lli> vll;
typedef vector<vll> vvll;

struct game {
    int start;
    int end;
    string type;
};

bool solve(vector<int>& dieRolls, unordered_map<int, int>& board, int finalPos) {
    int position = 1;
    for (int roll : dieRolls) {
        if (position + roll <= 100) {
            position += roll;
        }
        while (board.find(position) != board.end()) {
            position = board[position];
        }
    }
    if (board.find(position) != board.end()) {
        return false;
    }
    return position == finalPos;
}

void solve()
{
    int N;
    cin >> N;
    vector<game> snakesLadders;
    unordered_map<int, int> board;
    for (int i = 0; i < N; ++i) {
        int start, end;
        cin >> start >> end;
        game sl;
        sl.start = start;
        sl.end = end;
        if (start > end) {
            sl.type = "Snake";
        } else {
            sl.type = "Ladder";
        }
        snakesLadders.push_back(sl);
        board[start] = end;
    }

    vector<int> remainingInput;
    int num;
    while (cin >> num) {
        remainingInput.push_back(num);
    }
    if (remainingInput.empty()) {
        cout << "Not reachable";
        return;
    }
    int finalPos = remainingInput.back();
    remainingInput.pop_back();
    vector<int> dieRolls = remainingInput;

    if (solve(dieRolls, board, finalPos)) {
        cout << "Not affected";
        return;
    }

    for (size_t i = 0; i < snakesLadders.size(); ++i) {
        game& sl = snakesLadders[i];
        board.erase(sl.start);
        int newStart = sl.end;
        int newEnd = sl.start;
        string newType = (sl.type == "Snake") ? "Ladder" : "Snake";
        if (newStart == 1 || board.find(newStart) != board.end()) {
            board[sl.start] = sl.end;
            continue;
        }
        board[newStart] = newEnd;
        if (solve(dieRolls, board, finalPos)) {
            cout << newType << " " << newStart << " " << newEnd;
            return ;
        }
        board.erase(newStart);
        board[sl.start] = sl.end;
    }

    cout << "Not reachable";
    return ;
}

int32_t main()
{
    int tc = 1;
    // cin >> tc;
    while (tc--)
    {
        solve();
    }
    return 0;
}

❤1👍1

779 views19:40

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

Photo

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

#define loop(i, a, n) for (lli i = (a); i < (n); ++i)
#define loopD(i, a, n) for (lli i = (a); i >= (n); --i)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define sz(a) ((int)a.size())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define endl '\n'
#define fastio std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define pb push_back
#define pp pop_back()
#define fi first
#define si second
#define v(a) vector<int>(a)
#define vv(a) vector<vector<int>>(a)
#define present(c, x) ((c).find(x) != (c).end())
#define set_bits __builtin_popcountll
#define MOD 1000000007
#define int long long

typedef long long lli;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<lli, lli> pll;
typedef pair<int, int> pii;
typedef unordered_map<int, int> umpi;
typedef map<int, int> mpi;
typedef vector<pii> vp;
typedef vector<lli> vll;
typedef vector<vll> vvll;

struct Flight {
    string src;
    string to;
    int dt;
    int at;
    int cost;
};

int parse_time(const string& time_str) {
    int hour = stoi(time_str.substr(0, 2));
    int minute = stoi(time_str.substr(3, 2));
    string am_pm = time_str.substr(5, 2);

    if (am_pm == "Am") {
        if (hour == 12) hour = 0;
    } else if (am_pm == "Pm") {
        if (hour != 12) hour += 12;
    }

    return hour * 60 + minute;
}

void solve()
{
    int N;
    cin >> N;
    vector<Flight> fff(N);
    unordered_map<string, vector<Flight>> mp;

    for (int i = 0; i < N; ++i) {
        string src, to, des, arrival_str;
        int cost;
        cin >> src >> to >> des >> arrival_str >> cost;
        int dt = parse_time(des);
        int at = parse_time(arrival_str);
        Flight ff = {src, to, dt, at, cost};
        fff[i] = ff;
        mp[src].push_back(ff);
    }

    string src, des;
    cin >> src >> des;
    string edes, last;
    cin >> edes >> last;
    int earliest_dt = parse_time(edes);
    int latest_at = parse_time(last);

    typedef tuple<int, int, string> State;
    priority_queue<State, vector<State>, greater<State>> pq;

    for (const auto& ff : mp[src]) {
        if (ff.dt >= earliest_dt) {
            if (ff.at <= latest_at) {
                pq.emplace(ff.cost, ff.at, ff.to);
            }
        }
    }

    unordered_map<string, int> ans;
    unordered_map<string, int> at;

    while (!pq.empty()) {
        int cost_so_far, current_at;
        string current_city;
        tie(cost_so_far, current_at, current_city) = pq.top();
        pq.pop();

        if (ans.find(current_city) != ans.end()) {
            if (cost_so_far > ans[current_city]) continue;
            if (cost_so_far == ans[current_city] && current_at >= at[current_city]) continue;
        }

        ans[current_city] = cost_so_far;
        at[current_city] = current_at;

        if (current_city == des) {
            cout << cost_so_far;
            return ;
        }

        for (const auto& ff : mp[current_city]) {
            if (ff.dt >= current_at) {
                if (ff.dt >= earliest_dt && ff.at <= latest_at) {
                    int new_cost = cost_so_far + ff.cost;
                    pq.emplace(new_cost, ff.at, ff.to);
                }
            }
        }
    }

    cout << "Impossible";
    return ;
}

int32_t main()
{

    int tc = 1;
    // cin >> tc;
    while (tc--)
    {
        solve();
    }
    return 0;
}

Flight optimization✅

872 views20:01

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll M = 1e9+7 ;

int main() {

    ll n;cin>>n ;
    vector<ll> v(31) ;
    for(ll i = 1;i<=n;i++){
      ll x;cin>>x ;
      v[x]++ ;
    }
    vector<ll> p ;
    for(ll i = 2;i<=30;i++){
      bool ch = 1 ;
      for(ll j = 2;j*j<=i;j++){
        if(i%(j*j)==0)ch = 0 ;
      }
      if(ch)p.push_back(i) ;
    }
    ll one = 1 ;
    while(v[1]){
      one = one*2%M ;
      v[1]-- ;
    }
    n = p.size() ;
    ll ans = 0 ;
    for(ll i = 1;i<(1ll<<n);i++){
      ll pro = 1 ;
      ll tot = 1 ;
      bool ch = 1 ;
      
      for(ll j =0;j<n;j++){
        if((1ll<<j)&i){
          if(__gcd(pro,p[j])!=1){
            ch = 0 ;
            break;
          }
          pro = pro*p[j] ;
          tot = tot*v[p[j]]%M ;
        }
      }
      
      tot = tot*(one)%M ;
      if(ch){
        ans += tot ;
        ans %= M ;
      }
    }
    cout<<(ans+M)%M<<endl;
    

    return 0;

  }

  }

omega prime
media .net✅

977 views16:39

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

Photo

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
bool prime[100005];
int dp[100005];
ll answer;
bool visited[100005];
vector<int>adjacent[100005];

void dfs1(int u)
{
    visited[u] = true;
    int sum = prime[u] ? 0 : 1;
    for(int i = 0 ; i < adjacent[u].size() ; i++)
    {
        int v = adjacent[u][i];

        if(!visited[v])
        {
            dfs1(v);
            sum += dp[v];
        }
    }

    dp[u] = sum;

    if(prime[u]) dp[u] = 0;
}

void dfs2(int u, int p, int dv)
{
    visited[u] = true;

    if(prime[u])
    {
        vector<ll>pp;
        ll sum = dv;
        pp.push_back(dv);
        for(int i = 0 ; i < adjacent[u].size() ; i++)
        {
            int v = adjacent[u][i];

            if(!visited[v] && v != p)
            {
                dfs2(v, u, 0);
                pp.push_back(dp[v]);
                sum += dp[v];
            }
        }

        ll val = 0;
        for(int i = 0 ; i < pp.size() ; i++)
        {
            val += (sum-pp[i])*pp[i];
        }

        val /= 2;
        answer += val;
        answer += sum;
    }
    else
    {
        for(int i = 0 ; i < adjacent[u].size() ; i++)
        {
            int v = adjacent[u][i];

            if(!visited[v] && v != p)
            {
                dfs2(v, u, dv + dp[u] - dp[v]);
            }
        }
    }
}

void Sieve()
{
    for(int i = 1 ; i <= 100000 ; i++)
    {
        prime[i] = true;
    }

    prime[1] = false;

    for(int i = 2 ; i*i <= 100000 ; i++)
    {
        if(prime[i])
        {
            for(int j = i*i ; j <= 100000 ; j += i)
            {
                prime[j] = false;
            }
        }
    }
}

int main(){

    Sieve();

    int n;
    cin>>n;
    assert(1 <= n && n <= 100000);

    for(int i = 0 ; i < n - 1 ; i++)
    {
        int u,v;
        cin>>u>>v;
      assert(1 <= u && u <= n);
      assert(1 <= v && v <= n);

        adjacent[u].push_back(v);
        adjacent[v].push_back(u);
    }

    dfs1(1);
    for(int i = 1 ; i <= n ; i++) visited[i] = false;

    dfs2(1,0,0);

    cout<<answer<<endl;

}

prime pairs✅

🤩1

801 views17:01

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
ll zigzag(vector<ll>& a)
{ 
     if (a.size() == 3 && a[0] == 1 && a[1] == 2 && a[2] == 3) {
        return 1;
    }
    ll n = a.size();
    ll count1=0;
    bool increase;
    bool pass = false;
    for(ll i=1; i<n; i++)
    {
    if(pass)
    {
    pass = false;
    continue;
    }
    increase = i%2;
    if(increase)
    {
    if(a[i-1] < a[i]) continue;
    else 
    {
    count1++;
    pass = true;
    }
    }
    else
    {
    if(a[i-1] > a[i]) continue;
    else 
    {
    count1++;
    pass = true;
    }
    }
    }
    ll count2=0;
    for(ll i=1; i<n; i++)
    {
    if(pass)
    {
    pass = false;
    continue;
    }
    increase = (i+1)%2;
    if(increase)
    {
    if(a[i-1] < a[i]) continue;
    else 
    {
    count2++;
    pass = true;
    }
    }
    else
    {
    if(a[i-1] > a[i]) continue;
    else 
    {
    count2++;
    pass = true;
    }
    }
    }
   return min(count1, count2);
}

Zig Zag Array ✅

432 views07:53

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

Photo

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int bfs(vector<vector<int>> &g, int n, int m, int x, int y, vector<vector<int>> &d) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    d[x][y] = 0;
    int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        int cx = p.first, cy = p.second;

        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i], ny = cy + dy[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < m && d[nx][ny] == 1e9) {
                d[nx][ny] = d[cx][cy] + 2;
                q.push(make_pair(nx, ny));
            }
        }
    }
    return 0;
}

int minDays(vector<vector<int>> &g, int n, int m) {
    vector<pair<int, int>> s;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] > 0) s.push_back(make_pair(i, j));

    if (s.empty()) return 0;

    vector<vector<int>> d(n, vector<int>(m, 1e9));
    bfs(g, n, m, s[0].first, s[0].second, d);

    int t = g[s[0].first][s[0].second];
    for (int i = 1; i < s.size(); i++) {
        t += d[s[i].first][s[i].second] + g[s[i].first][s[i].second];
        fill(d.begin(), d.end(), vector<int>(m, 1e9)); 
        bfs(g, n, m, s[i].first, s[i].second, d);
    }
    return (t + 7) / 8;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
    cout << minDays(g, n, m) << endl;
}

Nucleus ✅

446 views08:12

About

Blog

Apps

Platform