USACO Silver 2017 February - Why Did the Cow Cross the Road I

Authors: Benjamin Qi, Brad Ma

Edit This Page

Official Analysis (C++)

There are multiple greedy strategies (though all of them involve sorting the animals by time). Here, we follow the approach described by the analysis.

Implementation

Time Complexity: O(Nlog⁡N+Clog⁡C)\mathcal O(N \log N+C\log C)

C++

#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>


using std::cout;
using std::endl;
using std::pair;
using std::vector;

Java

import java.io.*;
import java.util.*;


public class HelpCross {
 	Code Snippet: Cow Class (Click to expand)


	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("helpcross");
		int numChickens = io.nextInt();
		int numCows = io.nextInt();

Python

import heapq


with open("helpcross.in") as read:
	num_chickens, num_cows = [int(i) for i in read.readline().split()]


	chickens = [int(read.readline()) for _ in range(num_chickens)]


	cows = []
	for _ in range(num_cows):
		cows.append(tuple(int(i) for i in read.readline().split()))

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum