USACO Bronze 2016 January - Mowing the Field

Authors: Óscar Garries, Ryan Chou


Official Analysis (Java)

We can simulate Farmer John's movements across his field and update our answer when he comes across the same patch of grass.

Implementation

Time Complexity: O(NS)\mathcal{O}(NS)

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("mowing.in", "r", stdin);
int n;
cin >> n;
vector<pair<char, int>> steps(n);
for (auto &[dir, num_steps] : steps) { cin >> dir >> num_steps; }

Java

import java.io.*;
import java.util.*;
public class Mowing {
Code Snippet: Step Class (Click to expand)
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new FileReader("mowing.in"));
int n = Integer.parseInt(read.readLine());
Step[] steps = new Step[n];

Python

with open("mowing.in") as read:
n = int(read.readline())
steps = []
for _ in range(n):
dir_, num_steps = map(str, read.readline().split())
steps.append((dir_, int(num_steps)))
# FJ's starting position.
curr = (0, 0)
# Make a hashmap, and mark off steps.

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!