Problem A

Given a string (S), produce a new string by appending "pp" to (S).

Simply use std::string in C++:

std::string s;
std::cin >> s;
s += "pp";
std::cout << s << "\n";

Problem B

There are (n) flowers with petal counts (a_1, a_2, \dots, a_n). Two counting cycles exist:

• "like, disugsting"
• "like, disgusting, like very much"

Your girlfriend picks a flower and one of the cycles. To ensure the result is always "like" or "like very much", you must remove petals so that for every (i): [ (a_i \equiv 1 \pmod 2) \land (a_i \equiv 1 \lor a_i \equiv 0 \pmod 3). ] This simplifies to (a_i \equiv 1 \pmod 6) or (a_i \equiv 3 \pmod 6).

O((n)) brute force:

int c = 0;
for (int i = 0; i < n; ++i) {
    int x; std::cin >> x;
    while (x % 6 != 1 && x % 6 != 3 && x > 0) {
        --x;
        ++c;
    }
}
std::cout << c << "\n";

A constant-time version using integer division:

i64 floordiv(i64 a, i64 b) {
    if (a % b == 0) return a / b;
    else if ((a ^ b) > 0) return a / b;
    else return a / b - 1;
}

void solve() {
    int n; std::cin >> n;
    i64 c = 0;
    for (int i = 0; i < n; ++i) {
        i64 x; std::cin >> x;
        i64 p1 = floordiv(x - 1, 6) * 6 + 1;
        i64 p2 = floordiv(x - 3, 6) * 6 + 3;
        i64 p = std::max({0LL, p1, p2});
        c += x - p;
    }
    std::cout << c << "\n";
}

Solving congruences: For a system [ \begin{cases} X \equiv a \pmod b \ X \equiv c \pmod d \end{cases} ] we combine by solving (a + bx = c + dy), which gives (x = x_0 + \frac{d}{(b,d)}t) and [ X \equiv a + b x_0 \pmod{[b,d]}. ] We can iterate to combine (n) congruences.

To solve (ax + by = p), if ((a,b)\mid p), reduce to (a'x + b'y = p'). Solve (a'x' + b'y' = 1) via extended Euclidean algorithm, then (x_0 = x' \cdot p' \bmod b').

The extended Euclidean algorithm:

def extended_gcd(a, b):
    if b == 0:
        return (1, 0, a)
    else:
        x1, y1, g = extended_gcd(b, a % b)
        return (y1, x1 - (a // b) * y1, g)

Problem C

Start ((sx,sy)), end ((tx,ty)), (T) minutes, speed (V), (n) intermediate points. Check if any intermeidate point allows reaching within (T\cdot V): [ \sqrt{(sx-x_i)^2+(sy-y_i)^2}+\sqrt{(tx-x_i)^2+(ty-y_i)^2} \le T\cdot V. ] Use a small epsilon to avoid floating point errors:

const double EPS = 1e-9;

int dist2(int x1, int y1, int x2, int y2) {
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

void solve() {
    int sx,sy,tx,ty; std::cin >> sx >> sy >> tx >> ty;
    int T,V; std::cin >> T >> V;
    int n; std::cin >> n;
    bool ok = false;
    while (n--) {
        int x,y; std::cin >> x >> y;
        double d = std::sqrt(dist2(sx,sy,x,y)) + std::sqrt(dist2(x,y,tx,ty));
        if (d - T*V < EPS) ok = true;
    }
    std::cout << (ok ? "YES" : "NO") << "\n";
}

Alternatively, check ellipse containment without floating point by squaring, but the above is simpler for contest.

Problem D

Undirected graph with (n) nodes (0 = you). You can talk to people you meet; meeting propagates through friends. Girlfriend can:

• Delete an edge (cut friendship)
• Delete a node (forbid a person to talk to you, but they still connect others)

Goal: disconnect all "girl" nodes (input given) from node 0 with minimum operations.

This is a minimum cut problem. Construct flow network:

• Source (s = n+1), sink (t = n+2).
• For edges from source (node 0): add directed edge (s \to v) with capacity 1 (because cutting this edge corresponds to deleting the friendship).
• For other edges: add undirected edge with capacity 1.
• For each girl node (g): add edge (g \to t) with capacity 1 (cutting this edge means forbidding that person).

Minimum cut = maximum flow (Dinic). Complexity (O(n^2 m) = O(n^4)).

// Dinic implementation
template<typename T, int V=110, int E=2010>
struct FlowGraph {
    int s,t,vtot;
    int head[V],etot;
    int dist[V],cur[V];
    struct Edge { int v,nxt; T f; } e[E*2];

    void init(int _s,int _t,int _vtot) {
        s=_s; t=_t; vtot=_vtot;
        for(int i=1;i<=vtot;++i) head[i]=-1;
        etot=0;
    }
    void add_edge(int u,int v,T f1,T f2=0) {
        e[etot]={v,head[u],f1}; head[u]=etot++;
        e[etot]={u,head[v],f2}; head[v]=etot++;
    }
    bool bfs() {
        for(int i=1;i<=vtot;++i) dist[i]=0,cur[i]=head[i];
        std::queue<int> q; q.push(s); dist[s]=1;
        while(!q.empty()) {
            int u=q.front(); q.pop();
            for(int i=head[u];~i;i=e[i].nxt) if(e[i].f && !dist[e[i].v]) {
                int v=e[i].v; dist[v]=dist[u]+1;
                if(v==t) return true;
                q.push(v);
            }
        }
        return false;
    }
    T dfs(int u,T flow) {
        if(u==t) return flow;
        T used=0;
        for(int &i=cur[u];~i;i=e[i].nxt) if(e[i].f && dist[e[i].v]==dist[u]+1) {
            int v=e[i].v;
            T f=dfs(v,std::min(flow-used,e[i].f));
            e[i].f-=f; e[i^1].f+=f;
            used+=f;
            if(used==flow) break;
        }
        if(!used) dist[u]=-1;
        return used;
    }
    T dinic() {
        T flow=0;
        while(bfs()) flow+=dfs(s,std::numeric_limits<T>::max());
        return flow;
    }
};

FlowGraph<int> g;

void solve() {
    int N,G,E; std::cin >> N >> G >> E;
    int s=N+1, t=N+2;
    g.init(s,t,N+2);
    for(int i=0;i<G;++i) {
        int x; std::cin >> x;
        g.add_edge(x,t,1);
    }
    for(int i=0;i<E;++i) {
        int u,v; std::cin >> u >> v;
        if(u>v) std::swap(u,v);
        if(u==0) g.add_edge(s,v,1,1);
        else g.add_edge(u,v,1,1);
    }
    std::cout << g.dinic() << "\n";
}

Variations:

• If only edge deletion allowed: collapse all girl nodes into one, then min cut.
• If different costs for node/edge deletion: split each node into in/out with weight, use standard node-splitting technique.