USACO 2019 Jan Bronze

Problem 1. Shell Game

To pass the time, Bessie the cow and her friend Elsie like to play a version of a game they saw at the county fair. To start, Bessie puts three inverted shells on a table and places a small round pebble under one of them (at least she hopes it is a pebble – she found it on the ground in one of the pastures). Bessie then proceeds to swap pairs of shells, while Elsie tries to guess the location of the pebble.

The standard version of the game the cows saw being played at the county fair allowed the player to see the initial location of the pebble, and then required guessing its final location after all the swaps were complete.

However, the cows like to play a version where Elsie does not know the initial location of the pebble, and where she can guess the pebble location after every swap. Bessie, knowing the right answer, gives Elsie a score at the end equal to the number of correct guesses she made.

Given the swaps and the guesses, but not the initial pebble location, please determine the highest possible score Elsie could have earned.

INPUT FORMAT (file shell.in):
The first line of the input file contains an integer N giving the number of swaps (1≤N≤100). Each of the next N lines describes a step of the game and contains three integers a, b, and g, indicating that shells a and b were swapped by Bessie, and then Elsie guessed shell g after the swap was made. All three of these integers are either 1, 2, or 3, and a≠b.
OUTPUT FORMAT (file shell.out):
Please output the maximum number of points Elsie could have earned.
SAMPLE INPUT:


2 1  
2 1  
3 1

SAMPLE OUTPUT:

In this example, Elsie could have earned at most 2 points. If the pebble started under shell 1, then she guesses right exactly once (her final guess). If the pebble started under shell 2, then she guesses right twice (the first two guesses). If the pebble started under shell 3, then she doesn’t make any correct guesses.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
fin = open("shell.in", "r")
fout = open("shell.out", "w")

n = int(fin.readline())
g = []

for i in range(n):
    g.append(list(map(int, fin.readline().split())))

max_count = 0
for x in [1, 2, 3]:
    # print("When x is", x)
    shell = [1, 2, 3]
    temp = 0
    count = 0
    for y in g:
        # print("Switch", shell[y[0]-1], "and", shell[y[1]-1])
        shell[y[0]-1], shell[y[1]-1] = shell[y[1]-1], shell[y[0]-1]
        if shell[y[2] - 1] == x:
            count += 1
        if count > max_count:
            max_count = count
fout.write(str(max_count))

Problem 2. Sleepy Cow Sorting

Sleepy Cow Sorting

Farmer John is attempting to sort his N cows (1≤N≤100), 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 FORMAT (file sleepy.in):
The first line of input contains N.
The second line contains N space-separated integers, p1,p2,p3,…,pN, indicating the starting order of the cows.

OUTPUT FORMAT (file sleepy.out):
A single integer: the number of time steps before the N cows are in sorted order, if Farmer John acts optimally.
SAMPLE INPUT:

4
1 2 4 3

SAMPLE OUTPUT:

Problem credits: Dhruv Rohatgi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> cows;

int main()
{
    ifstream fin ("sleepy.in");
    ofstream fout ("sleepy.out");

    fin >> N;
    cows.resize(N);

    for(int i=0;i<N;i++)
    {
        fin >> cows[i];
    }

    int count = 1;
    for (int i = N - 1; i > 0; i--) {
        if (cows[i] > cows[i - 1]) {
            count++;
        }
        else {
            break;
        }
    }

    fout << N - count << '\n';
}