USACO 2019 January Contest Bronze Division - Sleepy Cow Sorting

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The first observation is that we can solve the problem in at most \(n\) operations, of course the greatest value will arrive at some point at the end.

Actually, we don't even need to move the last value, we can place everything in relation to the last value and this is enough to help us deduce the answer as everything else will have to be placed in between.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int n;

int main()
{
    ifstream cin("sleepy.in");
    ofstream cout("sleepy.out");

    cin >> n;
    vector<int> v(n);

    for(int i = 0; i < n; i++)
        cin >> v[i];

    int px = n-2;
    while(px >= 0 && v[px] <= v[px+1])
        px--;

    cout << px+1 << '\n';

    return 0;
}

with open("sleepy.in", "r") as fin:
    tokens = fin.read().split()
n = int(tokens[0])
v = list(map(int, tokens[1:]))
px = n - 2
while px >= 0 and v[px] <= v[px+1]:
    px -= 1
with open("sleepy.out", "w") as fout:
    fout.write(str(px+1) + "\n")