ICPC 2011

Problem ID: addmul The Industrial Computer Processor Company offers very fast, special purpose processing units tailored to customer needs. Processors of the a-C-m family (such as the 1-C-2 and the 5-C-3) have an instruction set with only two different oper...

Problem ID: affine Tess L. Ation ran into a little problem last week when she demonstrated the beta version of her new drawing software. On the screen she had an elegant demonstration design that illustrated every feature of her program; it had taken her ho...

Problem ID: ancient In order to understand early civilizations, archaeologists often study texts written in ancient languages. One such language, used in Egypt more than 3000 years ago, is based on characters called hieroglyphs. Figure C.1 shows six hierogl...

Problem ID: chips A prominent microprocessor company has enlisted your help to lay out some interchangeable components (widgets) on some of their computer chips. Each chip’s design is an N ×N square of slots. One slot can hold a single component, and you ar...

Problem ID: coffee Is it just a fad or is it here to stay? You’re not sure, but the steadily increasing number of coffee shops that are opening in your hometown has certainly become quite a draw. Apparently, people have become so addicted to coffee that apa...

Problem ID: works You are the director of Arbitrarily Complex Machines (ACM for short), a company producing advanced machinery using even more advanced machinery. The old production machinery has broken down, so you need to buy new production machines for t...

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...

Problem ID: mining John Digger is the owner of a large illudium phosdex mine. The mine is made up of a series of tunnels that meet at various large junctions. Unlike some owners, Digger actually cares about the welfare of his workers and has a concern about...

Problem ID: mummy During an excursion to the desert at the 2011 ACM-ICPC World Finals, you come across an old Egyptian tomb. Unfortunately, opening the tomb turns out to be a bad idea: all of a sudden, what was just a few moments ago an empty desert has now...

Problem ID: pyramids It is not too hard to build a pyramid if you have a lot of identical cubes. On a flat foundation you lay, say, 10 × 10 cubes in a square. Centered on top of that square you lay a 9 × 9 square of cubes. Continuing this way you end up wit...

Problem ID: trash Allied Chute Manufacturers is a company that builds trash chutes. A trash chute is a hollow tube installed in buildings so that trash dropped in at the top will fall down and be collected in the basement. Designing trash chutes is actually...