EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2011
ICPC 2011

G. Magic Sticks

Problem ID: magicsticks Magic was accepted by all ancient peoples as a technique to compel the help of divine powers. In a well-known story, one group of sorcerers threw their walking sticks on the floor where they magically appeared to turn into live serpe...

Updated May 21, 2026
Track ICPC
Year 2011
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

Magic was accepted by all ancient peoples as a technique to compel the help of divine powers. In a well-known story, one group of sorcerers threw their walking sticks on the floor where they magically appeared to turn into live serpents. In opposition, another person threw his stick on the floor, where it turned into a serpent which then consumed the sorcerers’ serpents! The only magic required for this problem is its solution. You are given a magic stick that has several straight segments, with joints between the segments that allow the stick to be folded. Depending on the segment lengths and how they are folded, the segments of the stick can be arranged to produce a number of polygons. You are to determine the maximum area that could be enclosed by the polygons formed by folding the stick, using each segment in at most one polygon. Segments can touch only at their endpoints. For example, the stick shown below on the left has five segments and four joints. It can be folded to produce a polygon as shown on the right.

Input

The input contains several test cases. Each test case describes a magic stick. The first line in each test case contains an integer n (1 ≤ n ≤ 500) which indicates the number of the segments in the magic stick. The next line contains n integers S1 , S2 , . . . , Sn (1 ≤ Si ≤ 1000) which indicate the lengths of the segments in the order they appear in the stick. The last test case is followed by a line containing a single zero.

Output

For each case, display its case number followed by the maximum total enclosed area that can be obtained by folding the magic stick at the given points. Answers within an absolute or relative error of 10−4 will be accepted. Follow the format of the sample output.

Sample Tests

Sample
Sample Input 
  4
  1 2 3 4
  8
  3 4 5 33 3 4 3 5
  0

ICPC 2011 World Finals Problem G: Magic Sticks
Sample Output 
Case 1: 4.898979
Case 2: 19.311
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • Write the structural observations that make the problem tractable.

  • State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.

  • If the constraints matter, explain exactly which part of the solution they enable.

Algorithm

  1. Describe the data structures and the state maintained by the algorithm.

  2. Explain the processing order and why it is sufficient.

  3. Mention corner cases explicitly if they affect the implementation.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

State the first key claim.

Proof.

Provide a concise proof.

Lemma 2.

State the next claim if needed.

Proof.

Provide a concise proof.

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

Combine the lemmas and finish the argument.

Complexity Analysis

State the running time and memory usage in terms of the input size.

Implementation Notes

  • Mention any non-obvious implementation detail that is easy to get wrong.

  • Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

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

namespace {

void solve() {
    // Fill in the full solution logic for the problem here.
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2011/G-magic-sticks/solution.texC++ implementationcompetitive_programming/icpc/2011/G-magic-sticks/solution.cppStatement textcompetitive_programming/icpc/2011/G-magic-sticks/statement.txtStatement PDFcompetitive_programming/icpc/2011/G-magic-sticks/statement.pdfMetadatacompetitive_programming/icpc/2011/G-magic-sticks/meta.jsonYear packetcompetitive_programming/icpc/2011/contest_problems.pdf