A - The Number of Even Pairs

Given (n) even numbers and (m) odd numbers, count the number of ways to choose two distinct numbers such that their sum is even. A sum is even only if both numbers have the same parity. The number of ways to pick two evens is (\binom{n}{2} = n(n-1)/2), and for two odds its (\binom{m}{2} = m(m-1)/2). The total is the sum of these two.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    cout<<n*(n-1)/2 + m*(m-1)/2;
    return 0;
}

B - String Palindrome

A string (a) of odd length is called "strong palindrome" if (a) itself, the prefix (a[1 \dots \frac{n-1}{2}]), and the suffix (a[\frac{n+3}{2} \dots n]) are all palindromes. Implement a function to check palindrome and verify the three conditions.

#include<bits/stdc++.h>
using namespace std;
const int N=99;
int n;
char a[N+5];
bool pal(int l,int r){
    while(l<=r){
        if(a[l]!=a[r]) return false;
        l++; r--;
    }
    return true;
}
int main(){
    cin>>a+1;
    n=strlen(a+1);
    int mid=(n-1)/2;
    if(pal(1,n) && pal(1,mid) && pal(mid+2,n))
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}

C - Maximum Volume

Given a real number (x), maximize the volume (abc) subject to (a+b+c=x) and (a,b,c \geq 0). By the AM-GM inequality, the product is maximized when (a=b=c=x/3), so the maximum volume is ((x/3)^3).

#include<bits/stdc++.h>
using namespace std;
int main(){
    double x;
    cin>>x;
    printf("%.10lf\n", pow(x/3,3));
    return 0;
}

D - Banned K

We have (n) integers (a_1,\dots,a_n) with (a_i \in [1,n]). For each (k), count the number of pairs of equal elements among the remaining (n-1) numbers (excluding (a_k)). Precompute frequency (b_i) for each value (i). The total number of pairs without exclusion is (\sum_i \binom{b_i}{2}). When (a_k) is removed, we lose all pairs involving (a_k). The number of pairs that include (a_k) is (b_{a_k}-1). Hence answer for each (k) is (\text{total} - (b_{a_k}-1)).

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200000;
int n,a[N+1];
int buc[N+1];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i], buc[a[i]]++;
    ll total=0;
    for(int i=1;i<=n;i++) total += 1LL*buc[i]*(buc[i]-1)/2;
    for(int i=1;i<=n;i++) cout << total - (buc[a[i]]-1) << "\n";
    return 0;
}

E - Dividing Chocolate

Given an (n \times m) binary matrix (a), we want to cut the chocolate horizontally and vertically so that each piece contains at most (s) ones. (n \leq 10), (m \leq 1000). Enumerate all (2^{n-1}) ways to make horizontal cuts. For each horizontal division, scan columns from left to right greedily: maintain the count of ones in each horizontal segment for the current column block. If adding a new column causes any segment to exceed (s), we must insert a vertical cut before this column. If even the new column alone makes a segment exceed (s), this horizontal division is invalid. Take the minimum total cuts (horizontal + vertical) across all valid divisions.

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,m,s;
char a[15][1005];
int main(){
    cin>>n>>m>>s;
    for(int i=0;i<n;i++) cin>>a[i];
    int ans=INF;
    for(int mask=0; mask<(1<<(n-1)); mask++){
        vector<int> cuts;
        cuts.push_back(0);
        for(int i=0;i<n-1;i++) if(mask>>i&1) cuts.push_back(i+1);
        cuts.push_back(n);
        int segs = cuts.size()-1;
        int cur_cuts = segs-1; // horizontal cuts count
        vector<int> cnt(segs,0);
        bool ok=true;
        for(int j=0;j<m;j++){
            vector<int> add(segs,0);
            for(int k=0;k<segs;k++){
                for(int r=cuts[k];r<cuts[k+1];r++) if(a[r][j]=='1') add[k]++;
                if(add[k]>s) { ok=false; break; }
            }
            if(!ok) break;
            bool need_cut=false;
            for(int k=0;k<segs;k++) if(cnt[k]+add[k]>s) { need_cut=true; break; }
            if(need_cut){
                cur_cuts++;
                cnt = add;
            } else {
                for(int k=0;k<segs;k++) cnt[k]+=add[k];
            }
        }
        if(ok) ans=min(ans,cur_cuts);
    }
    cout<<ans<<endl;
    return 0;
}

F - Knapsack for All Segments

We have (n) numbers (a_i). For a subset ({a_{x_1} < a_{x_2} < \cdots < a_{x_k}}) with sum (m), it contributes to the answer for every segment ([l,r]) that contains it: (l \in [1,x_1]) and (r \in [x_k,n]), so contribution = (x_1 \cdot (n-x_k+1)). We need the sum over all subsets that sum to (m), over all segments.

We use DP: let (dp_j) = sum of the leftmost index over all subsets (processed so far) that sum to (j). Initialize (dp_0=0), others 0. Process (i) from (1) to (n):

• Update answer: if (a_i == m), add (i \cdot (n-i+1)); if (a_i < m), add (dp_{m-a_i} \cdot (n-i+1)).
• Then update DP backwards: for (j=m) down to (a_i), (dp_j += dp_{j-a_i}), and if (j==a_i) also add (i). Modulo (998244353).

#include <bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<int> dp(m+1,0);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]==m) ans = (ans + 1LL*i*(n-i+1)%MOD) % MOD;
        else if(a[i]<m) ans = (ans + 1LL*dp[m-a[i]]*(n-i+1)%MOD) % MOD;
        for(int j=m;j>=a[i];j--){
            dp[j] = (dp[j] + dp[j-a[i]]) % MOD;
            if(j==a[i]) dp[j] = (dp[j] + i) % MOD;
        }
    }
    cout<<ans<<endl;
    return 0;
}