ICPC 2009
All 11 ICPC problems from 2009, each with a statement view, editorial, and C++ implementation.
Problem set
Each entry below goes straight to the public problem page, with the statement, editorial, code, and raw resources kept together.
A. A Careful Approach
Input: approach.in If you think participating in a programming contest is stressful, imagine being an air traffic controller. With human lives at stake, an air traffic controller has to focus on tasks while working under constantly changing conditions as we...
B. My Bad
Input file: bad.in A logic circuit maps its input through various gates to its output with no feedback loops in the circuit. The input and output are an ordered set of logical values, represented here by ones and zeros. The circuits we consider are comprise...
C. The Return of Carl
Input file: carl.in Carl the ant is back! When we last left him (Problem A, 2004 World Finals), Carl was a little mixed-up, always taking strange, zigzag paths when traveling. But now, Carl has straightened out his life – literally. He now always takes the...
D. Conduit Packing
Input File: conduit.in Allied Conduit Manufacturing (ACM) makes metal conduit tubes with round cross-sections that enclose many different types of wires. The circular cross-section of a wire can have a diameter up to 20 millimeters (20000 micrometers). ACM...
E. Fare and Balanced
Input: fare.in Handling traffic congestion is a difficult challenge for young urban planners. Millions of drivers, each with different goals and each making independent choices, combine to form a complex system with sometimes predictable, sometimes chaotic...
F. Deer-Proof Fence
Input: fence.in Uncle Magnus has planted some young saplings on his farm as part of his reforestation project. Unfortunately, deer like to eat tender sapling shoots and leaves, making it necessary to build protective fences around them. Since deer and other...
G. House of Cards
Input file: game.in Axel and Birgit like to play a card game in which they build a house of cards, gaining (or losing) credits as they add cards to the house. Since they both have very steady hands, the house of cards never collapses. They use half a deck o...
H. The Ministers’ Major Mess
Input file: major.in The ministers of the remote country of Stanistan are having severe problems with their decision making. It all started a few weeks ago when a new process for deciding which bills to pass was introduced. This process works as follows. Du...
I. Struts and Springs
Input file: springs.in Struts and springs are devices that determine the way in which rectangular windows on a screen are resized or repositioned when the enclosing window is resized. A window occupies a rectangular region of the screen, and it can enclose...
J. Subway Timing
Input: subway.in Like most modern cities, Stockholm has a well-developed public transportation system. The heart of public transportation in Stockholm is the subway. A topological map of the subway system illustrates the different subway lines and how they...
K. Suffix-Replacement Grammars
Input file: suffix.in As computer programmers, you have likely heard about regular expressions and context-free grammars. These are rich ways of generating sets of strings over a small alphabet (otherwise known as a formal language). There are other, more e...