[USACO 2017 Bronze 3] Milk Measurement

Question:

Farmer John purchases three cows: Bessie, Elsie, and Mildred, each of whom initially produces 7 gallons of milk per day. Since the milk output of a cow is known to potentially change over time, Farmer John takes periodic measurements over the next 100 days and scribbles them down in a log book. Entries in his log look like this:

35 Bessie -2
14 Mildred +3

The first entry indicates that on day 35, Bessie's milk output was 2 gallons lower than it was when last measured. The next entry indicates that on day 14, Mildred's milk output increased by 3 gallons from when it was last measured. Farmer John has only enough time to make at most one measurement on any given day. Unfortunately, he is a bit disorganized, and doesn't necessarily write down his measurements in chronological order.

To keep his cows motivated, Farmer John proudly displays on the wall of his barn the picture of whichever cow currently has the highest milk output (if several cows tie for the highest milk output, he displays all of their pictures). Please determine the number of days on which Farmer John would have needed to change this display.

Input

The first line of input contains N, the number of measurements Farmer John makes. Each of the next N lines contains one measurement, in the format above, specifying a day (an integer in the range 1..100), the name of a cow, and the change in her milk output since it was last measured (a nonzero integer). Each cow's milk output will always be in the range 0..1000.

4
7 Mildred +3
4 Elsie -1
9 Mildred -1
1 Bessie +2

Output

Please output the number of days (an integer in the range 0..100) on which Farmer John needs to adjust his motivational display.

 

3

 

N = int(input())
mesrmt = []
for i in range(N):
    day,name,milk = input().split()
    mesrmt.append((int(day),name,int(milk)))
mesrmt.sort()

co3 = {"Bessie" : 0, "Elsie" : 1, "Mildred" : 2}
all_milk = [7, 7, 7]
change = 0
before = 7

def cal_max():
    result = 0
    for i in range(3):
        if all_milk[i] == max(all_milk):
            result += (2**i)
            # Bessie 단독 1등 : result = 1
            # Elsie 단독 1등 : result = 2
            # Mildred 단독 1등 : result = 4
            # Bessie, Elsie 공동 1등 : result = 3
            # Bessie, Mildred 공동 1등 : result = 5
            # Elsie, Mildred 공동 1등 : result = 6
            # Bessie, Elsie, Mildred 공동 1등 : result = 7
    return result

for day,name,milk in mesrmt:
    all_milk[co3[name]] += milk
    after = cal_max()

    if before != after:
        change += 1
        before = after

print(change)

Explanation

The code traks changes in milk output of three cows over 100 days and determining how many days Farmer John needs to alter his motivating display to promote the cow with the greatest milk yield. The code creates a dictionary co3 to map cow names to indices and a list all_milk to reflect each cow's current milk output. The basic concept revolves around the method cal_max(), which computes the binary representation of the cow with the maximum milk yield. The main loop iterates through the recorded data, updating the milk output and calculating the current highest output with the cal_max() method. 

The code increases a counter if the display has to be updated . The final result is the total number of days that must be adjusted. This method manages shifting milk production quickly and determines the days when the motivating display must be modified to highlight the leading cow or cows.