[Shebang]

These are some old questions I found from last year's CCC, I'll post this year's questions if I can find the package I got from my teacher.

Problem S2: Bridge transport
Problem Description
A train of railway cars attempts to cross a bridge. The length of each car is 10m but their weights
might be different. The bridge is 40m long (thus can hold 4 train cars at one time). The bridge will
crack if the total weight of the cars on it at one time is greater than a certain weight. The cars are
numbered starting at 1, going up to N, and they cross the bridge in that order (i.e., 1 immediately
followed by 2, which is immediately followed by 3, and so on).

What is the largest number T of railway cars such that the train of cars 1...T (in order) can cross
the bridge?

Input Specification
The first line of input is the maximum weight W (1 <= W <= 100000) that the bridge can hold at
any particular time. The second line of input is the number N (1 <= N <= 100000) which is the
number of railway cars that we wish to move across the bridge. On each of the next N lines of
input, there will be a positive integer wi (1 <= i <= N, 1 <= Wi <= 100000) which represents the
weight of the ith railway car in the sequence.

Output Specification
Your output should be a non-negative integer representing the maximum number of railway cars
that can be brought across the bridge in the order specified.

Sample Input 1
100
6
50
30
10
10
40
50

Output for Sample Input 1
5

Explanation of Output for Sample Input 1
The first four railway cars have total weight 50 + 30 + 10 + 10 = 100, which is not greater than
what the bridge can hold. When the first railway car leaves, and the next comes on, we have a total
weight of 30 + 10 + 10 + 40 = 90, which is not greater than what the bridge can hold. The last
four cars would cause the bridge to break, since 10 + 10 + 40 + 50 = 110 which is greater than the
bridge can hold. So, only the first 5 railway cars can be taken across the bridge.

[0xDEAD10CC]

Here's my solution:

Code:

#include <iostream> #include <vector> typedef std::vector<int>::iterator vector_iter_t; int max_railway_cars(std::vector<int> &cars, const unsigned max_weight, const int max_cars) { unsigned current_weight = 0; vector_iter_t it[] = { cars.begin(), cars.begin() }; do { if (std::distance(it[0], it[1]) == max_cars) { current_weight -= *it[0]; it[0]++; } current_weight += *it[1]; } while (++it[1] != cars.end() && current_weight <= max_weight); return std::distance(cars.begin(), it[1]) - (current_weight <= max_weight ? 0 : 1); } int main() { const unsigned max_cars = 4; // 4 cars can cross at a time const unsigned max_weight = 100; // max weight the bridge can withstand std::vector<int> cars { 50, 30, 10, 10, 40, 50 }; std::cout << max_railway_cars(cars, max_weight, max_cars) << std::endl; }

[Shebang]

I forgot to mention that while the question does provide sample inputs, the online grader has a random set of inputs used to confirm that the code functions, which means that you need to support standard input. Here's a solution in Python that received full marks:

Code:

# CCC 2013 S2: Bridge Transport # # This solution is due largely to Nenad Bauk # (also thanks to Victor Wang of Tecumseh Elementary # re: what if the last car makes the bridge collapse? # This is NOT tested in the test data, but is the example given. # This program passed this test :-), as well as the 13 test cases.) # # Generally speaking one wishes to calculate the weight of four cars. # The weights are stored in an array (list in python). # # Nenad's insight is to simplify things by starting the array with 3 # zero weight cars. This way there are no special cases to consider # wrt the first three cars. There are always four cars to add up: # the current one and the 3 previous! # To simplify issues around the last car, I also added a sentinel to # the end, a car with a weight in excess of the max. #input the data file = open("s2.0.in", 'r') W = int(file.readline()) N = int(file.readline()) carWeight = [0,0,0] for i in range(N): carWeight.append(int(file.readline())) carWeight.append (W+1) # calculate the weight of each group of four cars # stopping when the max weight is exceeded. # the senteniel guarantees I'll never fall off the end of the array # and thus no need to check for that. carsAcross = 0 i = 3 totalWeight = carWeight[i-3] + carWeight[i-2] + carWeight[i-1] + carWeight[i] while totalWeight <= W: carsAcross = carsAcross + 1 i = i + 1 totalWeight = carWeight[i-3] + carWeight[i-2] + carWeight[i-1] + carWeight[i] print carsAcross

If I find my Java solution, I'll post it.

[0xDEAD10CC]

I understand that, I've seen others of this format, I just didn't feel it was necessary here since that is irrelevant to the question, and also because I don't know where to grab the input from or what format it is in. I'd assume separated by '\n', and spaces if necessary, as this is what most do.