Je moet \(n\) dagen voor een bedrijf werken. Soms kan je thuis werken en soms wordt je ‘s avonds opgebeld dat je de volgende dag naar het werk moet komen. Dat kan helemaal niet gebeuren, maar ook \(n\) keer – dat weet je niet op voorhand. Je gaat met de trein naar het werk en kan op elke dag kiezen of je een enkel ticket koopt dat alleen op die dag geldig is (stel dat de kost 1 is) of een seizoensticket dat tot het einde van seizoen geldig is. Dat heeft altijd kost \(k > 1\), waarbij \(k\) een geheel getal is.

Als je op voorhand zou weten hoe vaak je opgebeld zal worden, zou het gemakkelijk zijn te beslissen wat je moet doen (dat zou een offline algoritme vereisen, dat alle informatie al heeft). Het feit dat je dat niet weet, vereist een online algoritme. Geef een online algoritme dat elke dag alleen gebaseerd op de al vergaarde informatie één van de volgende beslissingen neemt:

• koop een enkel ticket voor deze dag (kost 1)
• koop een seizoensticket (kost k)
• koop geen ticket (kan alleen als je thuis werkt of al een seizoensticket hebt gekocht)

Het resultaat van dit algoritme moet zijn dat je over heel het seizoen gegarandeerd minder dan 2 keer zo veel voor tickets betaald dan als je de oplossing van het offline algoritme al gekend had.

Implementeer de interface TicketBuyer¹ in een klasse OnlineTicketBuyer.

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.