PDP-25 (2013) - Camp common - 2 (carmeet)

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem types
Allowed languages
C, C++, Java, Pascal, Python

Problem

Let's consider a circular road with N cities, numbered from 0 to N - 1. The road connecting them is one-way, as shown in the diagram below.

pdp2013campc2-figure-1.svg

Along the road, there are a total of K 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, N (number of cities) and K (number of vehicles), separated by a single space. The second line contains K integers, determining in which cities the K 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

1 \le N \le 10.000
1 \le K \le 10.000
In at least 30% of the test cases, N and K will not exceed 10.
In at least 70% of the test cases, N and K will not exceed 100.
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 2, and the fourth one is in city 0.

pdp-2013-camp-c2-fig-2.svg

The vehicles in the above diagram can meet after 6 legal moves in city 3. (One sequence of moves leading to this solution is for the vehicle starting from city 0 and a vehicle from city 2 to move alternately.)


Comments

There are no comments at the moment.