Problemas de Programação

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3649 We want to determine a set of tunnels which has the least cost. Then, we can use a Minimum Spanning Tree to solve this problem. import java.io.*; import java.util.*; class Main {     public ArrayList<Edge> list;     public int[] nodeParent;     public int[] depth;         public int root(int n) {         while (n != nodeParent[n]) {             n = nodeParent[n];         }         return n;     }         public boolean union(int n1, int n2) {         int rootN1 = root(n1);         int ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2931 The solution below just execute a graph traversal following the instructions on the problem statement. import java.io.*; import java.util.*; class Main {     public char[][] matrix;     public char[] instructions;     public String positions = "NLSO";     public int numRows;     public int numCols;     public int countStickers;         public void changePosition(int i, int j, char curr) {         if (matrix[i][j] == '*') {             countStickers++;         }         matrix[i][j] = curr;     }         public boole...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1956 The solution below used Floyd-Warshall to solve this problem. It is necessary to sum the values in every row to achieve the answer. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numCase = 0;         int numMembers = sc.nextInt();         int numPaths = sc.nextInt();         while (numMembers != 0 || numPaths != 0) {             String[] names = n...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=668&page=show_problem&problem=813 The solution below used a mix of Topological Sorting and Backtracking to solve this problem. import java.io.*; import java.util.*; class Main  {     public HashMap<Character, ArrayList<Character>> dependents;     public ArrayList<Character> sequence;     public boolean[] considered;     public int numConsidered;     public int[] degrees;     public ArrayList<Character> zeroDegree;     public int totalLetters;     public TreeSet<String> answer;     public String[] letters;       public void rec() {         if (numConsidered == letters.length) {             Stri...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2760   import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             String s1 = sc.next();             String s2 = sc.next();                         boolean same = true;  ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1190 The solution below used a Greedy approach to solve this problem. More details about this solution can be found in the code below through the comments. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTeams = sc.nextInt();         int numTables = sc.nextInt();         while (numTeams != 0 || numTables != 0) {             Team[] teams = new Team[numTeams];     ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=535 The solution below used Bit Manipulation to solve this problem. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         while (sc.hasNext()) {             int n = sc.nextInt();             int saveN = n;                        int p = 0;             int c...