Problem
Let's consider a circular road with cities, numbered from to . The road connecting them is one-way, as shown in the diagram below.
Along the road, there are a total of vehicles parked in some of the cities. Each city can have none, one, or more vehicles.
We define a move as the movement of a vehicle from the city where it is currently located to the next one on the cycle. A move is legal if a different vehicle moved in the immediately preceding move (if it exists). In other words, it is forbidden for the same vehicle to move two consecutive times.
Write a program to calculate the minimum number of legal moves required to relocate all vehicles to the same city. Your program should also calculate the city where the final meeting of the vehicles will take place.
Input
The input will consist of only two lines. The first line contains two integers, (number of cities) and (number of vehicles), separated by a single space. The second line contains integers, determining in which cities the vehicles are initially located.
Output
The output should consist of a single line containing only two numbers separated by a single space. The first number should be the count of the minimum legal moves required to relocate all vehicles to the same city. The second number should be the city where the vehicles will meet. If there are multiple solutions with the same minimum number of moves, the city of meeting with the smallest number should be printed.
Constraints
In at least % of the test cases, and will not exceed .
In at least % of the test cases, and will not exceed .
Time limit: 2 seconds
Memory limit: 64 MB.
Example of Input - Output
STDIN (carmeet.in)
5 4
2 0 2 2
STDOUT (carmeet.out)
6 3
Explanation of the Example: Three out of the four vehicles are in city , and the fourth one is in city .
The vehicles in the above diagram can meet after legal moves in city . (One sequence of moves leading to this solution is for the vehicle starting from city and a vehicle from city to move alternately.)
Comments