USACO 2015 December Contest, Bronze Problem 1. Fence Painting

原题下载

USACO2015-DEC-B1

答案

(Analysis by Nick Wu)

In this problem, we have a fence and two sections of the fence have been painted. We need to determine how much of the fence has been painted. We will present two solutions to this problem.

The first solution that we will present relies on the fact that at most 100 units of the fence will be painted. We can loop over each unit of the fence and see if that unit of the fence is inside one of the painted segments, and then count how many such units there are.

The second solution relies on the fact that there are exactly two segments that were painted, but does not depend on how long those segments are. There are two cases to consider here:

Case 1: The two segments do not overlap at all.

Case 2: The two segments do overlap by at least one unit.

First, we need to decide if the two segments overlap. Assume without loss of generality that a≤ca≤c (otherwise we can swap the segments so this is true). If c≥bc≥b, then the two segments do not overlap and the answer is simply the sum of the lengths of the two segments.

Otherwise, if the two segments overlap, then it matters if d>bd>b. If d>bd>b, then the section of fence from aa to dd is painted and the answer is d−ad−a, otherwise the section of fence from aa to bb is painted and the answer is b−ab−a.

Here is my code implementing the first solution:

import java.io.*;
import java.util.*;
public class paint {
	public static void main(String[] args) throws IOException {
		// initialize file I/O
		BufferedReader br = new BufferedReader(new FileReader("paint.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("paint.out")));

		// read in the first line, store a and b
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		// read in the second line, store c and d
		st = new StringTokenizer(br.readLine());
		int c = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());

		int amountPainted = 0;
		for(int i = 0; i < 100; i++) {
			if(i >= a && i+1 <= b) {
				amountPainted++;
			}
			else if(i >= c && i+1 <= d) {
				amountPainted++;
			}
		}
		
		// print the answer!
		pw.println(amountPainted);

		// close output stream
		pw.close();
	}
}

Here is my code implementing the second solution:

import java.io.*;
import java.util.*;
public class paint {
	public static void main(String[] args) throws IOException {
		// initialize file I/O
		BufferedReader br = new BufferedReader(new FileReader("paint.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("paint.out")));

		// read in the first line, store a and b
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		// read in the second line, store c and d
		st = new StringTokenizer(br.readLine());
		int c = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());

		// for convenience, have segment [a, b] come before segment [c, d], so we want a <= c
		// if c < a, then we need to swap the two segments
		if(c < a) {
			// swap a and c
			int temp = a;
			a = c;
			c = temp;
			// then swap b and d
			temp = b;
			b = d;
			d = temp;
		}
		
		int amountPainted = 0;
		// if c >= b, then the two segments do not overlap.
		if(c >= b) {
			amountPainted = (b-a) + (d-c);
		}
		// otherwise, the two segments partially overlap, and we need to check if d > b
		else {
			if(d > b) {
				amountPainted = d - a;
			}
			else {
				amountPainted = b - a;
			}
		}
		
		// print the answer!
		pw.println(amountPainted);

		// close output stream
		pw.close();
	}
}