Under construction

Still being built. Things may change

Cheap Flying

Time limit3sMemory limit1024 MB

Summary
Decide when to buy an aircraft for repeated flights without knowing how many flights will come, keeping total cost within twice the offline optimum.
Level

Medium4 of 10

Topics
Greedy, Math
Solved
No attempts yet

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.

Examples2

  1. Example 1

    Input
    5 50 2
    flight
    
    flight
    
    flight
    
    end
    
    Expected output
    
    airline
    
    airline
    
    airline
    
    
  2. Example 2

    Input
    5 8 1
    flight
    
    flight
    
    end
    
    Expected output
    
    buy
    
    self