USACO Bronze 2016 January - Angry Cows

Author: Qi Wang

Edit This Page

Official Analysis (Java)

Warning!

The solution from the official analysis is incorrect on the following input:

3
3
5
6

It outputs 2, but the correct answer is 3.

Video Solution

By Qi Wang

Implementation

Time Complexity: O(N2)\mathcal{O}(N^2)

C++

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


int N;
vector<int> bales;


int exploded_num(int start, int direction) {
	int radius = 1;
	int prev = start;
	while (true) {

Java

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


public class Angry {
	static int N;
	static int[] bales;


	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("angry");

Python

with open("angry.in") as read:
	bales = sorted([int(read.readline()) for _ in range(int(read.readline()))])




def exploded_num(start: int, direction: int) -> int:
	radius = 1
	prev = start
	while True:
		next_ = prev
		# Get the furthest explosion index without exceeding the current radius

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