Center Alignment

Core idea

This is implementation, not black magic. But there are two easy ways to punt this into WA:

1. reading the input wrong;
2. alternating the odd paddings wrong.

Since lines may contain spaces and may even be empty, getline is mandatory. If you use cin >>, congratulations, you just deleted half the input.

Also, you cannot print on the fly, because the frame width depends on the longest line. So first store every line, then compute $W = \max_i |s_i|.$

The inside width of the framed text must be exactly $W$:

• anything smaller and the longest line does not fit;
• anything larger is not the minimum size.

So the top and bottom borders are simply strings of length $W+2$ made of *.

How to center one line

For a line $s_i$, let $d_i = W - |s_i|$ be the number of spaces we still need to add.

We want left padding $L_i$ and right padding $R_i$ such that $L_i + |s_i| + R_i = W.$

Case 1: $d_i$ is even

Then life is easy: $L_i = R_i = \frac{d_i}{2}.$ Perfectly centered. No drama.

Case 2: $d_i$ is odd

Now perfect centering is impossible, because one side must get the extra space. The statement says these lines should be moved alternately closer to the left and right edge, starting with left.

That means:

• closer to the left edge: $L_i = \left\lfloor \frac{d_i}{2} \right\rfloor, \quad R_i = \left\lceil \frac{d_i}{2} \right\rceil$
• closer to the right edge: $L_i = \left\lceil \frac{d_i}{2} \right\rceil, \quad R_i = \left\lfloor \frac{d_i}{2} \right\rfloor$

So for odd $d_i$, we just keep a boolean toggle:

• first odd line: closer left;
• second odd line: closer right;
• third odd line: closer left;
• and so on.

The trap is stupid but deadly: toggle only for odd $d_i$. Even-difference lines are already perfectly centered, so they should not affect the alternation.

Algorithm

1. Read all lines with getline into a vector.
2. Compute $W = \max |s_i|$.
3. Print a border of * repeated $W+2$ times.
4. Keep bool closerLeft = true.
5. For each line:
   • compute $d = W - |s|$;
   • start with $L = R = \lfloor d/2 \rfloor$;
   • if $d$ is odd:
     • if closerLeft, add the extra space to the right;
     • otherwise add it to the left;
     • flip closerLeft.
   • print * + left spaces + line + right spaces + *.
6. Print the same border again.

Empty lines are handled automatically: they are just strings of length $0$. No special case needed. Nice when a problem lets you be lazy for the right reasons.

Why this is correct

Let $W = \max_i |s_i|$.

• Any valid framed text needs inner width at least $W$, otherwise the longest line cannot fit.
• Our construction uses inner width exactly $W$, so the frame is minimum possible.
• For every line, we choose $L_i$ and $R_i$ with $L_i + |s_i| + R_i = W$, so every printed row has the same width.
• If $d_i$ is even, then $L_i = R_i$, so the line is perfectly centered.
• If $d_i$ is odd, then $|L_i - R_i| = 1$, which is the best possible. Our toggle makes these imperfect cases alternate left/right exactly as required, starting with closer left.

So the output matches the statement, and nothing sketchy is happening behind the curtain.

Complexity

Let $n$ be the number of lines and $W$ the maximum line length.

• Reading/storing input costs $O\left(\sum |s_i|\right)$.
• Printing costs $O(nW)$, which is also the size of the produced output.
• Memory usage is $O\left(\sum |s_i|\right)$.

With the given limits, this is absurdly safe.