سوال ۶۱ کنکور ارشد علوم کامپیوتر ۱۴۰۴

The list holds the values $1,2,\dots,n$ in order. The outer loop walks cur over every node $i$, and for each starting position the inner loop adds up info from node $i$ all the way to the last node $n$.

Inner loop from a start position $i$. When cur sits on node $i$, the inner loop accumulates $i + (i+1) + \cdots + n.$

Total over all start positions. Use the contribution technique: count how many times each value $j$ is added. Value $j$ is reached by the inner loop exactly when the outer loop starts at some position $i \le j$, i.e. for $i = 1, 2, \dots, j$ — that is $j$ times. Hence each value $j$ contributes $j \cdot j = j^{2}$, and $x = \sum_{j=1}^{n} j \cdot j = \sum_{j=1}^{n} j^{2} = 1^{2} + 2^{2} + 3^{2} + \cdots + n^{2}.$

This is exactly option 3 (its first term $1$ is $1^{2}$).

Sanity check with $n=2$. Start at node $1$: $1+2=3$. Start at node $2$: $2$. Total $x=5$. Compare: option 3 gives $1^{2}+2^{2}=5$ ✓; option 1 gives $\tfrac{2\cdot 3}{2}=3$ ✗; option 4 gives $1+2(1)=3$ ✗.

The closed form equals $\dfrac{n(n+1)(2n+1)}{6}$, but among the choices it appears as the explicit sum of squares.

Exam trick: A nested traversal where the inner loop runs from the outer pointer to the end means item $j$ is summed once for every outer start $i \le j$ — so it is counted $j$ times, turning a plain sum into $\sum j^{2}$.