ICPC 2016
All 13 ICPC problems from 2016, 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. Balanced Diet
Every day, Danny buys one sweet from the candy store and eats it. The store has m types of sweets, numbered from 1 to m. Danny knows that a balanced diet is important and is applying this concept to his sweet purchasing. To each sweet type i, he has assigne...
B. Branch Assignment
The Innovative Consumer Products Company (ICPC) is planning to start a top-secret project. This project consists of s subprojects. There will be b ≥ s branches of ICPC involved in this project and ICPC wants to assign each branch to one of the subprojects....
C. Ceiling Function
Advanced Ceiling Manufacturers (ACM) is analyzing the properties of its new series of Incredibly Collapse-Proof Ceilings (ICPCs). An ICPC consists of n layers of material, each with a different value of collapse resistance (measured as a positive integer)....
D. Clock Breaking
After numerous unfortunate freak fatalities and the lawsuits, settlements, protests, and boycotts that naturally followed, the beleaguered executives at ACME Clock Manufacturers have decided they need to finally fix their disastrous quality control issues....
E. Forever Young
My birthday is coming up. Alas, I am getting old and would like to feel young again. Fortunately, I have come up with an excellent way of feeling younger: if I write my age as a number in an appropriately chosen base b, then it appears to be smaller. For in...
F. Longest Rivers
The Chao Phraya River System is the main river system of Thailand. Its six longest rivers listed by decreasing length are: 1. Tha Chin (765 km) 2. Nan (740 km) 3. Yom (700 km) 4. Ping (658 km) 5. Pa Sak (513 km) 6. Wang (335 km) The Chao Phraya River System...
G. Oil
A large part of the world economy depends on oil, which is why research into new methods for finding and extracting oil is still active. Profits of oil companies depend in part on how efficiently they can drill for oil. The International Crude Petroleum Con...
H. Polygonal Puzzle
During last year’s ACM ICPC World Finals in Marrakesh, one of the judges bought a pretty wooden puzzle depicting a camel and palm trees (see Figure H.1). Unlike traditional jigsaw puzzles, which are usually created by cutting up an existing rectangular pict...
I. Road Times
Ubol Narongdid is the founder of a brash new startup company called Special D-Liver-E. She wants to corner the market on overnight deliveries of organs between hospitals in the Phuket area. For scheduling purposes it is important to have accurate estimates...
J. Spin Doctor
As an employee of the world’s most respected political polling corporation, you must take complex, real- world issues and simplify them down to a few numbers. It isn’t always easy. A big election is coming up and, at the request of Candidate X, you have jus...
K. String Theory
Nested quotations are great not only for writing literature with a complex narrative structure, but also in programming languages. While it may seem necessary to use different quotation marks at different nesting levels for clarity, there is an alternative....
L. Swap Space
You administer a large cluster of computers with hard drives that use various file system types to store data. You recently decided to unify the file systems to the same type. That is quite a challenge since all the drives are currently in use, all of them...
M. What Really Happened on Mars?
Real-time software in the Mars Pathfinder spacecraft suffered from an issue known as priority inversion. One technique to address this issue is to use the Priority Ceiling Protocol. In this problem, you will simulate the execution of multiple tasks accordin...