Cheap Flying
Time limit3sMemory limit1024 MB
Decide when to buy an aircraft for repeated flights without knowing how many flights will come, keeping total cost within twice the offline optimum.
Problem
You are part of the BAPC organization, and you are in charge of flight operations. From time to time, BAPC jury members need to fly from the remote headquarters to the current site of BAPC's operation, which is currently Amsterdam. Luckily, an airline serves the route from the headquarters to Amsterdam. BAPC has a contract with that airline that fixes the price per flight at the same amount. If jury members fly this route often, the costs add up and can become very high. To avoid this, you figured out that you could buy your own aircraft. Once you own an aircraft, you can either fly with it, which costs a fixed price per flight for fuel and the like, or you can still fly with the airline. The problem is that you have no idea what the jury members are doing. They are unpredictable and always do random and very complicated things. They are so random that you cannot decide beforehand what to do. You need to make your decision on the fly, even though this may prevent you from making the cost-optimal decision up front. Still, you do not want to be too loose with your spending. You set yourself the constraint that you spend at most twice as much as you would have if you knew in advance how many flights the jury members would make.