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

F. Glenbow Museum

Input file: museum.in The famous Glenbow Museum in Calgary is Western Canada’s largest museum, with exhibits ranging from art to cultural history to mineralogy. A brand new section is being planned, devoted to brilliant computer programmers just like you. U...

Updated May 21, 2026
Track ICPC
Year 2008
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
Input file museum.in

The famous Glenbow Museum in Calgary is Western Canada’s largest museum, with exhibits ranging from art to cultural history to mineralogy. A brand new section is being planned, devoted to brilliant computer programmers just like you. Unfortunately, due to lack of space, the museum is going to have to build a brand new building and relocate into it.

The size and capacity of the new building differ from those of the original building. But the floor plans of both buildings are orthogonal polygons. An orthogonal polygon is a polygon whose internal angles are either 90° or 270°. If 90° angles are denoted as R (Right) and 270° angles are denoted as O (Obtuse) then a string containing only R and O can roughly describe an orthogonal polygon. For example, a rectangle (Figure 1) is the simplest orthogonal polygon and it can be described as RRRR (the angles are listed in counter-clockwise order, starting from any corner). Similarly, a cross-shaped orthogonal polygon (Figure 2) can be described by the sequence RRORRORRORRO, RORRORRORROR, or ORRORRORRORR. These sequences are called angle strings.

Figure 1: A rectangle                               Figure 2: A cross-shaped polygon

Of course, an angle string does not completely specify the shape of a polygon – it says nothing about the length of the sides. And some angle strings cannot possibly describe a valid orthogonal polygon (RRROR, for example).

To complicate things further, not all orthogonal polygons are acceptable floor plans for the museum. A museum contains many valuable objects, and these objects must be guarded. Due to cost considerations, no floor can have more than one guard. So a floor plan is acceptable only if there is a place within the floor from which one guard can see the entire floor. Similarly, an angle string is acceptable only if it describes at least one acceptable polygon. Note that the cross-shaped polygon in Figure 2 can be guarded by someone standing in the center, so it is acceptable. Thus the angle string RRORRORRORRO is acceptable, even though it also describes other polygons that cannot be properly guarded by a single guard.

Help the designers of the new building determine how many acceptable angle strings there are of a given length.

Input

The input file contains several test cases. Each test case consists of a line containing a positive integer L (1≤L≤1000), which is the desired length of an angle string.

The input will end with a line containing a single zero.

Output

For each test case, print a line containing the test case number (beginning with 1) followed by the number of acceptable angle strings of the given length. Follow the format of the sample output.

Sample Tests

Sample
Sample Input 
4
6
0
Sample Output 
Case 1: 1
Case 2: 6
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/2008/F-glenbow-museum/solution.texC++ implementationcompetitive_programming/icpc/2008/F-glenbow-museum/solution.cppStatement textcompetitive_programming/icpc/2008/F-glenbow-museum/statement.txtStatement PDFcompetitive_programming/icpc/2008/F-glenbow-museum/statement.pdfMetadatacompetitive_programming/icpc/2008/F-glenbow-museum/meta.jsonYear packetcompetitive_programming/icpc/2008/contest_problems.pdf