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=3942 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++) {             int numRows = sc.nextInt();             int numCols = sc.nextInt();             int[][] matrix = new int[numRows][numCols];         ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=666&page=show_problem&problem=4027 import java.io.*; import java.util.*; class Main {     public Deque<Character> trails;         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 seq = sc.next();             char start = seq.charAt(0);                ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1734 The solution below used Floyd-Warshall 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));         int numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             int numLocations = sc.nextInt();             int numConnections = sc.nextInt();               ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=324 The solution below used Breadth-First Search (BFS) to solve this problem. import java.io.*; import java.util.*; class Main {     public HashMap<Character, ArrayList<Info>> adjList;         public char bfs(char start, int numPlanets) {         Queue<Info> queue = new ArrayDeque<>();         queue.add(new Info(start, 0, 0));                 HashSet<Character> visited = new HashSet<>();                 double bestValue = 0;         char bestPlanet = 'Z';         while (queue.size() ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=370 The solution below used Floyd-Warshall to solve this problem. If you want to see another solution using Breadth-First Search, click here . import java.io.*; import java.util.*; class Main {     public ArrayList<String> mapIntToString;     public Map<String, Integer> mapStringToInt;         public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = Integer.parseInt(br.readLine());         br.readLine();      ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=370 The solution below used Breadth-First Search (BFS) to solve this problem. For every word that we visit in the BFS method, we check all the other words. If the other word differs only in one character of the current word, we add it in our queue. import java.io.*; import java.util.*; class Main {     public ArrayList<String> words;         public int bfs(String start, String end) {         Queue<Counter> queue = new ArrayDeque<>();         queue.add(new Counter(start, 0));                 HashSet<String> visited = new HashSet<>();                 while (q...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1517 The solution below used Backtracking to solve this problem. import java.io.*; import java.util.*; class Main {     public int s;     public int d;     public int maxSurplus;     public int[] register;         public void rec(int month, int surplus, int lastFive) {         if (month >= 5) {             if (lastFive >= 0) {                 return;             }         }         if (month == 12) {           ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2933 Given a start position, the problem asks us to find the minimum total toll cost for the vehicle to reach the destination city. For this reason, the code below used Dijkstra's algorithm to find the solution. import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Edge>> adjList;     public int citiesServiceRoute;         public int dijkstra(int start, int end) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(start, 0));                 HashSet<Integer> visited = new HashSet<>();             ...

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static int sizeSeqA;     public static int sizeSeqB;     public static int[] seqA;     public static int[] seqB;     public static int[][] memo;             public static int lcs(int indexA, int indexB) {         if (indexA == sizeSeqA || indexB == sizeSeqB) {             return 0;         }                    if (memo[indexA][indexB] != -1) {             return memo[indexA][indexB];         }       ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3649 If you want to see another solution for this problem, click here . This solution used Prim's algorithm to solve this problem. import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Edge>> adjList;     public Queue<Edge> edges;         public void prim(int start, int numCities) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(start, 0, -1));                 HashSet<Integer> visited = new HashSet<>();                 while (queue.size() > 0) {     ...

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...