(UVA) Nonstop Travel - Solution

Brute Force was used to solve this problem.

First, all the possible speeds to pass each signal are checked. Those speeds that are common among all the signals are part of the final answer. Finally, the output is processed to be presented.


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

class Main {
    public static void process() throws NumberFormatException, IOException {  
        Scanner sc = new Scanner(System.in);
       
        int numCase = 0;
        int numSignals = sc.nextInt();
        while (numSignals != -1) {
            if (numSignals == 0) {
                System.out.println("Case " + ++numCase + ": 30-60");
            }
            else {
                ArrayList<HashSet<Integer>> time = new ArrayList<HashSet<Integer>>();
                for (int i = 0; i < numSignals; i++) {
                    time.add(new HashSet<Integer>());
                }
               
                // check possible speeds for each signal
                for (int i = 0; i < numSignals; i++) {
                    double location = sc.nextDouble();
                    int lengthG = sc.nextInt();
                    int lengthY = sc.nextInt();
                    int lengthR = sc.nextInt();
                   
                    int canPass = lengthG+lengthY;
                    HashSet<Integer> current = new HashSet<Integer>();
                    for (int j = 30; j <= 60; j++) {
                        int x = (int)(3600*location)/j;
                        int x2 = (int)((3600*location)/j-0.00000001); // precision
                        int moment = x%(lengthG+lengthY+lengthR);
                        if (moment < canPass) {
                            current.add(j);
                        }
                        else if (x2%(lengthG+lengthY+lengthR) < canPass) {
                            current.add(j);
                        }
                       
                    }
                    time.set(i, current);
                }

                // check common speed among the signals
                ArrayList<Integer> speeds = new ArrayList<Integer>();
                for (int i = 30; i <= 60; i++) {
                    int countSignals = 0;
                    for (int j = 0; j < numSignals; j++) {
                        if (time.get(j).contains(i)) {
                            countSignals++;
                        }
                    }
                    if (countSignals == numSignals) {
                        speeds.add(i);
                    }
                }
               
                if (speeds.size() > 0) {
                    boolean noSeq = true;
                    int first = -1;
                    int last = -1;
                    ArrayList<String> seqSpeeds = new ArrayList<String>();
                    // transform output
                    for (int j = 0; j < speeds.size(); j++) {
                        if (noSeq && j+1 < speeds.size() && speeds.get(j+1) == speeds.get(j)+1) {
                            first = j;
                            noSeq = false;
                        }
                        else if (!noSeq && ((j+1 < speeds.size() && speeds.get(j+1) != speeds.get(j)+1) || (j+1 == speeds.size()))) {
                            seqSpeeds.add(speeds.get(first) + "-" + speeds.get(j));
                            noSeq = true;
                        }
                        else if (noSeq && (j+1 < speeds.size() && speeds.get(j+1) != speeds.get(j)+1) || (j+1 == speeds.size())) {
                            seqSpeeds.add(speeds.get(j)+"");
                        }
                    }

                    System.out.print("Case " + ++numCase + ": ");
                    for (int j = 0; j < seqSpeeds.size()-1; j++) {
                        System.out.print(seqSpeeds.get(j) + ", ");
                    }
                    System.out.println(seqSpeeds.get(seqSpeeds.size()-1));
                }
                else {
                    System.out.println("Case " + ++numCase + ": No acceptable speeds.");
                }
            }
                              
            numSignals = sc.nextInt();
        }
              
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}