Het shuttlebedrijf organiseert een wedstrijd: één gouden munt voor iedereen die het vroegste tijdstip kan vinden waarop de bus met het eerste ID-nummer vertrekt en elke bus met het volgende ID-nummer op de volgende minuut vertrekt. (Hiervoor is de eerste regel van je aantekeningen niet langer relevant.)

Stel bijvoorbeeld dat je dezelfde reeks ID-nummers hebt als hiervoor:

7,13,x,x,59,x,31,19

Een x in de busdienst betekent dat er geen beperkingen zijn voor het ID-nummer van de bus die op dat moment moet vertrekken.

Dit betekent dat je zoekt naar het vroegste tijdstip (t genaamd) waarop:

• bus met ID-nummer 7 vertrekt op tijdstip t
• bus met ID-nummer 13 vertrekt één minuut na tijdstip t
• er zijn geen vereisten of beperkingen voor bussen die twee of drie minuten na tijdstip t moeten vertrekken
• bus met ID-nummer 59 vertrekt vier minuten na tijdstip t
• er zijn geen vereisten of beperkingen voor de bus die vijf minuten na tijdstip t moet vertrekken
• bus met ID-nummer 31 vertrekt zes minuten na tijdstip t
• bus met ID-nummer 19 vertrekt zeven minuten na tijdstip t

De enige busritten die er toe doen, zijn die van bussen met de vermelde ID-nummers op hun specifieke offsets vanaf tijdstip t. Die bussen kunnen op andere tijdstippen vertrekken, en bussen met andere ID-nummers kunnen op dezelfde tijdstippen vertrekken. Kijken we bijvoorbeeld naar bovenstaande reeks: omdat de bus met ID-nummer 19 zeven minuten na de bus met ID-nummer 7 moet vertrekken, zal de bus met ID-nummer 7 ook altijd vertrekken met de bus met ID-nummer 19 om zeven minuten na tijdstip t.

In dit voorbeeld is 1068781 het vroegste tijdstip waarop dit gebeurt:

time     bus 7   bus 13  bus 59  bus 31  bus 19
1068773    .       .       .       .       .
1068774    D       .       .       .       .
1068775    .       .       .       .       .
1068776    .       .       .       .       .
1068777    .       .       .       .       .
1068778    .       .       .       .       .
1068779    .       .       .       .       .
1068780    .       .       .       .       .
1068781    D       .       .       .       .
1068782    .       D       .       .       .
1068783    .       .       .       .       .
1068784    .       .       .       .       .
1068785    .       .       D       .       .
1068786    .       .       .       .       .
1068787    .       .       .       D       .
1068788    D       .       .       .       D
1068789    .       .       .       .       .
1068790    .       .       .       .       .
1068791    .       .       .       .       .
1068792    .       .       .       .       .
1068793    .       .       .       .       .
1068794    .       .       .       .       .
1068795    D       D       .       .       .
1068796    .       .       .       .       .
1068797    .       .       .       .       .

In het bovenstaande voorbeeld vertrekt de bus met ID-nummer 7 op tijdstip 1068788 (zeven minuten na tijdstip t). Dat is goed. De enige vereiste op die minuut is dat de bus met ID-nummer 19 dan vertrekt, en dat gebeurt ook.

Hier zijn nog enkele andere voorbeelden:

• het vroegste tijdstip dat overeenkomt met de reeks 17,x,13,19 is 3417
• het vroegste tijdstip dat overeenkomt met de reeks 67,7,59,61 is 754018
• het vroegste tijdstip dat overeenkomt met de reeks 67,x,7,59,61 is 779210
• het vroegste tijdstip dat overeenkomt met de reeks 67,7,x,59,61 is 1261476
• het vroegste tijdstip dat overeenkomt met de reeks 1789,37,47,1889 is 1202161486

Met zoveel bussen in de reeks moet er beslist wel een vroegste tijdstip zijn dat groter is dan 100000000000000!

Opgave

Wat is het vroegste tijstip waarop alle bussen met vermelde ID-nummers vertrekken met offsets die overeenkomen met hun posities in de reeks? Hiervoor ga je als volgt te werk:

• Schrijf een functie departure waaraan een reeks ID-nummers (char*) moet doorgegeven worden van de bussen die volgens het shuttlebedrijf in gebruik zijn. De functie moet het vroegste tijdstip (int) teruggeven waarop alle bussen met vermelde ID-nummers vertrekken met offsets die overeenkomen met hun posities in de reeks

Voorbeeld

> earliest_timestamp("7,13,x,x,59,x,31,19")
1068781
> earliest_timestamp("17,x,13,19")
3417
> earliest_timestamp("67,7,59,61")
754018
> earliest_timestamp("67,x,7,59,61")
779210
> earliest_timestamp("67,7,x,59,61")
1261476
> earliest_timestamp("1789,37,47,1889")
1202161486