USACO 2015 December Contest, Bronze Problem 3. Contaminated Milk

原题下载

USACO2015-DEC-B3

答案

(Analysis by Nick Wu)

In this problem we're given a list of the types of milk that each guest drank, when they drank each type, and when/if they got sick. Using this information we want to determine how many people may become sick given that exactly one type of milk is bad and making people sick.

To solve this problem we want to identify which types of milk could be the bad milk. We are explicitly told that a type of milk can be bad if, for every person that got sick, each person drank that type of milk before they got sick. Therefore, we loop over each sick person and ensure that they drank the candidate type of milk prior to getting sick.

Then to find the maximum number of guests who could become sick we want to find the maximum number of people who drank one of these candidate bad milks.

Here is my code documenting the given solution:

import java.io.*;
import java.util.*;
public class badmilk {
	/*
	 * For record i of a person drinking milk, we store data as follows:
	 * personDrink[i]: the person who drank the milk
	 * milkDrink[i]: the type of milk that the person drank
	 * timeDrink[i]: the time the person drank the milk
	 */
	static int[] personDrink;
	static int[] milkDrink;
	static int[] timeDrink;
	
	/*
	 * For record i of a person being sick, we store data as follows:
	 * personSick[i]: the person who got sick
	 * timeSick[i]: the time that person got sick
	 */
	static int[] personSick;
	static int[] timeSick;
	
	public static void main(String[] args) throws IOException {
		// initialize file I/O
		BufferedReader br = new BufferedReader(new FileReader("badmilk.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("badmilk.out")));

		// read in the first line, store n, m, d, and s
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());

		// initialize the arrays about drinking milk
		personDrink = new int[d];
		milkDrink = new int[d];
		timeDrink = new int[d];
		for(int i = 0; i < d; i++) {
			// read in record i of someone drinking milk
			st = new StringTokenizer(br.readLine());
			personDrink[i] = Integer.parseInt(st.nextToken());
			milkDrink[i] = Integer.parseInt(st.nextToken());
			timeDrink[i] = Integer.parseInt(st.nextToken());
		}
		
		// initialize the arrays about people getting sick
		personSick = new int[s];
		timeSick = new int[s];
		for(int i = 0; i < s; i++) {
			// read in record i of someone drinking
			st = new StringTokenizer(br.readLine());
			personSick[i] = Integer.parseInt(st.nextToken());
			timeSick[i] = Integer.parseInt(st.nextToken());
		}
		
		int maxCanGetSick = 0;
		
		for(int i = 1; i <= m; i++) {
			// check if milk type i can be bad
			if(milkTypeCanBeBad(i)) {
				// the milk type can be bad, now count how many people drank that type of milk
				int numDrank = numPeopleDrink(i);
				if(numDrank > maxCanGetSick) {
					// update the maximum number of people that could be sick
					maxCanGetSick = numDrank;
				}
			}
		}
		
		// print the answer!
		pw.println(maxCanGetSick);
		
		// close output stream
		pw.close();
	}
	
	/*
	 * Given a type of milk, this method returns true if and only if
	 * the given milk type could be bad. This is true if and only if
	 * for each person who got sick, this person consumed the given
	 * type of milk before that person got sick.
	 */
	private static boolean milkTypeCanBeBad(int milkType) {
		// loop over all records of people being sick
		for(int i = 0; i < personSick.length; i++) {
			// check for record i of sickness if that person drank that milk before they got sick
			if(!personDrankMilkBefore(personSick[i], milkType, timeSick[i])) {
				// that person did not, this milk type cannot be bad then
				return false;
			}
		}
		// all the records checked out, so return true
		return true;
	}
	
	/*
	 * Given a person, a type of milk, and a time, this method returns
	 * true if and only if the given person drank the given type of milk
	 * before the given time.
	 */
	private static boolean personDrankMilkBefore(int person, int milkType, int time) {
		// loop over all records of drinking
		for(int i = 0; i < personDrink.length; i++) {
			// check if record i of drinking if that person did drink that type of milk before the given time
			if(personDrink[i] == person && milkDrink[i] == milkType && timeDrink[i] < time) {
				// all conditions are satisfised, return true
				return true;
			}
		}
		// none of the records satisfied the conditions, return false
		return false;
	}

	private static int numPeopleDrink(int milkType) {
		// didDrink[i] will be true if and only if person i did drink the given type of milk
		boolean[] didDrink = new boolean[51];
		// loop over all records of drinking
		for(int i = 0; i < personDrink.length; i++) {
			// check if this record corresponds to the given type of milk
			if(milkDrink[i] == milkType) {
				// it does, mark that this person did drink that milk
				didDrink[personDrink[i]] = true;
			}
		}
		// now that we've looped over all records, just count the number of people
		// who drank that milk
		int numPeopleDrink = 0;
		for(int i = 1; i < didDrink.length; i++) {
			if(didDrink[i]) {
				numPeopleDrink++;
			}
		}
		return numPeopleDrink;
	}
	
}