#P1693. [USACO19FEB] Sleepy Cow Herding B

[USACO19FEB] Sleepy Cow Herding B

Problem Description

Farmer John’s three award-winning cows, Bessie, Elsie, and Mildred, always get lost and wander to faraway parts of the farm. He needs your help to herd them back together.

The farm’s pasture is roughly a long narrow region—we can think of it as a number line, and cows can occupy any integer position on the number line. These 33 cows are currently at distinct integer positions. Farmer John wants to move them so that they occupy three consecutive positions (for example, positions 66, 77, 88).

Unfortunately, the cows are very sleepy right now, so it is not easy for Farmer John to get them to focus and follow commands to move. At any moment, he can only move a cow that is at an “endpoint” position (the smallest or the largest position among all cows). When he moves a cow, he may command her to go to any unoccupied integer position, as long as at the new position she is no longer an endpoint. You can see that over time, moves like this can make the cows get closer and closer.

Compute the minimum and maximum possible number of moves needed to make the cows gather into consecutive positions.

Input Format

The input contains one line with three space-separated integers, giving the positions of Bessie, Elsie, and Mildred. Each position is an integer in the range 11091\ldots 10^9.

Output Format

The first line of output contains the minimum number of moves Farmer John needs to gather the cows together. The second line contains the maximum number of moves he could take while gathering the cows together.

4 7 9
1
2

Hint

Sample Explanation 1

The minimum number of moves is 11—if Farmer John moves the cow at position 44 to position 88, then the cows will be at consecutive positions 77, 88, 99. The maximum number of moves is 22. For example, the cow at position 99 can be moved to position 66, and then the cow at position 77 can be moved to position 55.

Translated by ChatGPT 5