10330. Sleepy cow sorting (bronze)
Farmer John is attempting to
sort his n cows, conveniently
numbered 1..n, before they head
out to the pastures for breakfast.
Currently, the cows are
standing in a line in the order p1, p2, p3, ..., pn, and Farmer John is standing in front of cow p1. He wants to reorder the cows so that they are in
the order 1, 2, 3, ..., n,
with cow 1 next to Farmer John.
The cows are a bit sleepy
today, so at any point in time the only cow who is paying attention to Farmer
John’s instructions is the cow directly facing Farmer John. In one time step,
he can instruct this cow to move k paces
down the line, for any k in the
range 1..n − 1.
The k cows whom she passes will amble
forward, making room for her to insert herself in the line after them.
For example, suppose that n = 4 and the cows start off in the
following order:
FJ:
4, 3, 2, 1
The only cow paying
attention to FJ is cow 4. If he instructs her to move 2 paces
down the line, the order will subsequently look like this:
FJ:
3, 2, 4, 1
Now the only cow paying
attention to FJ is cow 3, so in the second time step he may give
cow 3 an instruction, and so forth until the cows are sorted.
Farmer John is eager to
complete the sorting, so he can go back to the farmhouse for his own breakfast.
Help him find the minimum number of time steps required to sort the cows.
Input.
The first line contains n (1 ≤ n ≤ 100). The second line contains n
integers p1, p2, p3, ..., pn, indicating the starting order of the cows.
Output. Print a single integer: the minimum number of time steps before the n cows are in sorted order, if Farmer
John acts optimally.
|
Sample input |
Sample output |
|
4 1 2 4 3 |
3 |
sorting
Consider
some starting order of cows that can be sorted with one instruction. To do this,
the first cow should be put in its place. This can only be done if all the cows, from
the second to the last, are already arranged in ascending order. For example, any of
the following sequences can be sorted with a single command:
3 1 2 4 5 6 7
6 1 2 3 4 5 7
In
order for the cows to be sorted with two instructions, it is
necessary that all cows, from the third to the last, are arranged in ascending
order:
6 3 1 2 4 5 7
7 2 1 3 4 5 6
Suppose that k
instructions are sufficient for FJ. In this case, only the first k cows change their positions. This
means that the last n – k cows are
already sorted in increasing order, with respect to each other.
Conversely,
suppose that the last n – k cows are sorted in increasing order. Consider a sequence of
k instructions after which all n cows are sorted
If k = 0,
then the cows are already completely sorted.
If k >
0, then the first
cow can be inserted among the last n − k cows, so that now the last n + 1 − k cows are in increasing order. After repeating this k −
1 more times, the
last n cows are in increasing order. Since
there are only n cows, after k instructions the cows are sorted.
To solve the problem, one must find the maximum i such that
pi > pi+1 < pi+2
< … < pn
The answer will
be the value i + 1. If there is
no such i (the input array pi is already
sorted), then the answer is 0.
Example
Consider n = 7 cows, the last n – k = 7 – 3 = 4 of which are already sorted:
6 2 3 1 4 5 7
This sequence
can be sorted with k = 3 instructions:
·
put in place the cow number 6: 2 3 1 4 5 6 7;
·
put in place the cow number 2: 3 1 2 4 5 6 7;
·
put in place the cow number 3: 1 2 3 4 5 6 7;
Algorithm realization
Read the input data.
scanf("%d", &n);
p.resize(n);
for (i = 0;
i < n; i++)
scanf("%d", &p[i]);
Find the maximum value of i such that pi > pi+1
< pi+2 <
… < pn-1.
res = 0;
for (i = n - 2; i
>= 0; i--)
if (p[i] > p[i + 1])
{
The answer
is the value i + 1.
res = i + 1;
break;
}
Print
the answer.
printf("%d\n", res);