Given sorted trigger times, count cars with two axles and cars with three axles where gaps under 1000 ms join the same vehicle and gaps over 2000 ms split them.
Medium6Dynamic programmingGreedyNo attempts yetTime limit3sMemory limit512 MBThe local council records traffic flow with a pressure pad laid across the road. The pad records the time whenever the wheels on one axle of a vehicle cross it. The only vehicles on this road are cars with two axles, and a car may or may not tow a trailer with a single axle.
A car without a trailer produces two recorded times, one when the front wheels cross the pad and one when the rear wheels cross it. A car towing a trailer produces one more time for the trailer wheels, three in total. The recordings left by one vehicle are consecutive in time order.
The recordings alone do not fix a single reading. Six recordings could be three cars without trailers, or two cars with trailers. To cut down such ambiguity, assume the following two rules.
Given the recorded times, determine how many cars without trailers and how many cars with trailers crossed the pad.
The first line contains the number of times the pressure pad was triggered, n (1≤n≤300000).
The second line contains the times t1,t2,…,tn (0≤ti<230) in increasing order. The n times are distinct and are given in milliseconds.
If the number of cars of each type is determined, print two lines in the following form. X is the number of cars without trailers and Y is the number of cars with trailers.
Cars without trailers: X
Cars with trailers: Y
If no reading of the times agrees with the two rules, print Impossible. If several readings agree with the rules and they give different numbers of cars, print Ambiguous.